Nombre de Shannon : combien de parties d'échecs sont possibles ?

Le nombre de Shannon est souvent cité pour illustrer la richesse du jeu d'échecs. Il est aussi un excellent support pour travailler les puissances de 10, la notation scientifique et les ordres de grandeur, du collège au lycée. Encore faut-il savoir d'où il vient, ce qu'il mesure exactement, et ce qu'il ne mesure pas.

Nombre de Shannon

Estimation prudente, environ 10¹²⁰, du nombre de parties d'échecs possibles, proposée par le mathématicien et ingénieur américain Claude Shannon dans l'article « Programming a Computer for Playing Chess », publié en 1950 dans la revue Philosophical Magazine.

Le nombre de Shannon : d'où vient le calcul ?

Claude Shannon (1916-2001) est connu comme le fondateur de la théorie de l'information. En 1950, il publie l'un des premiers articles sur la programmation d'un ordinateur pour jouer aux échecs. Pour montrer qu'une machine ne peut pas simplement calculer toutes les suites de coups, il fait une estimation rapide :

1. Dans une position typique, il y a environ 30 coups légaux. Ce nombre reste à peu près constant pendant une grande partie de la partie.
2. Un coup blanc suivi d'un coup noir donne donc environ 30 × 30 = 900 possibilités, que Shannon arrondit à 10³.
3. Une partie typique dure environ 40 coups (40 coups blancs et 40 coups noirs) jusqu'à l'abandon d'un joueur.
4. Le nombre de suites de coups vaut donc environ (10³)⁴⁰ = 10¹²⁰.

Shannon ajoute qu'une machine qui examinerait une variante par microseconde mettrait plus de 10⁹⁰ ans à calculer son premier coup. Il en conclut qu'un programme d'échecs doit évaluer les positions et choisir les variantes à explorer, comme le fait un joueur humain.

Parties et positions : deux nombres différents

Il ne faut pas confondre le nombre de parties (des suites de coups) et le nombre de positions (des dispositions des pièces sur l'échiquier). Une même position peut être atteinte par des millions de parties différentes.

Shannon estimait le nombre de positions par la formule 64! / (32! × 8!² × 2!⁶), qui compte les façons de disposer les 32 pièces de départ sur les 64 cases ; le résultat vaut environ 4,6 × 10⁴², qu'il arrondit à « environ 10⁴³ ». L'estimation moderne de John Tromp, (4,82 ± 0,03) × 10⁴⁴ positions légales, est obtenue autrement : en tirant au hasard deux millions de positions parmi un ensemble que l'on sait dénombrer, puis en vérifiant lesquelles sont réellement atteignables dans une partie, avec l'aide de Peter Österlund pour l'analyse informatique.

Les premiers coups : un compte exact

Au début de la partie, on peut compter exactement. Les Blancs ont 20 coups possibles (16 coups de pions et 4 coups de cavaliers). Les Noirs aussi. On obtient :

Valeurs recalculées par programme à partir de la position initiale (comptage de toutes les suites de coups légaux).

Après seulement deux coups de chaque camp, on dépasse déjà 197 000 suites possibles. Le facteur multiplicatif augmente ensuite, car les pièces sortent et ont plus de choix : c'est ce qui justifie l'hypothèse d'une trentaine de coups par position.

D'où vient l'estimation de 10¹²³ ?

En 1994, le chercheur néerlandais Victor Allis a refait le calcul avec des hypothèses différentes : environ 35 coups possibles par position, et des parties de 80 demi-coups (40 coups de chaque camp). On obtient 35⁸⁰. Pour l'écrire en puissance de 10, on utilise le logarithme décimal : 80 × log(35) ≈ 80 × 1,544 ≈ 123,5. D'où l'ordre de grandeur de 10¹²³. La méthode est exactement celle de Shannon, seuls les paramètres changent, ce qui montre combien le résultat dépend des hypothèses.

Avec les paramètres exacts de Shannon, 900⁴⁰ vaut d'ailleurs environ 10¹¹⁸ et non 10¹²⁰ : c'est l'arrondi de 900 à 1 000 qui donne le joli chiffre rond. Pour un ordre de grandeur aussi gigantesque, la différence n'a aucune importance pratique.

Comment l'expliquer en classe

Le nombre de Shannon est idéal pour travailler les puissances de 10, au programme de 4^e. Quelques pistes :

• Écrire le nombre : 10¹²⁰ s'écrit avec un 1 suivi de 120 zéros. On peut le faire écrire au tableau… et mesurer le temps nécessaire.
• Calculer avec les puissances : (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ est une application directe de la règle (a^m)ⁿ = a^{m × n}.
• Comparer des ordres de grandeur : 10¹²⁰ divisé par 10⁸⁰ donne 10⁴⁰. Même si chaque atome de l'Univers était un ordinateur, chacun devrait encore traiter 10⁴⁰ parties.
• Discuter les hypothèses : pourquoi 30 coups par position ? pourquoi 40 coups par partie ? Que change une partie de 60 coups ? (Réponse : (10³)⁶⁰ = 10¹⁸⁰.)

Le nombre de grains de l'échiquier de Sissa, environ 1,8 × 10¹⁹, paraît minuscule à côté : la comparaison des deux est un bon exercice. Voir le calcul de l'échiquier de Sissa.

Peut-on « résoudre » les échecs ?

Résoudre un jeu, c'est savoir avec certitude quel résultat (victoire des Blancs, des Noirs ou nulle) donne une partie parfaite des deux côtés. Le nombre de Shannon montre qu'on ne peut pas le faire en explorant toutes les parties. Les ordinateurs ont toutefois résolu toutes les positions comportant peu de pièces, grâce à des tables de finales. Pour savoir où en est la question, le Palais des Échecs s'est demandé si les échecs pourront être résolus un jour.

Le nombre de Shannon et les autres grands nombres de l'échiquier

L'échiquier est une petite usine à grands nombres : 2⁶⁴ − 1 grains de Sissa, plus de 26 000 milliards de parcours fermés du cavalier, 92 solutions aux huit dames, 204 carrés… Retrouvez-les sur notre page les grands casse-têtes de l'échiquier.