Nombre de Shannon : combien de parties d'échecs peut-on jouer ?

On cite souvent le nombre de Shannon pour illustrer la richesse du jeu d'échecs. Il constitue aussi un excellent appui pour travailler les puissances de 10, l'écriture scientifique et les ordres de grandeur, du collège au lycée. Encore faut-il savoir d'où il sort, ce qu'il mesure précisément et ce qu'il ne mesure pas.

Nombre de Shannon

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

Le nombre de Shannon : comment obtient-on ce calcul ?

Claude Shannon (1916-2001) est reconnu comme le fondateur de la théorie de l'information. En 1950, il publie l'un des tout premiers travaux sur la programmation d'un ordinateur destiné à jouer aux échecs. Pour démontrer qu'une machine ne peut pas se contenter de calculer toutes les suites de coups, il réalise une estimation rapide :

1. Dans une position courante, on dispose d'une trentaine de coups légaux. Ce chiffre demeure à peu près stable durant une bonne part de la partie.
2. Un coup blanc suivi d'un coup noir offre donc environ 30 × 30 = 900 choix, que Shannon arrondit à 10³.
3. Une partie type s'étend sur environ 40 coups (40 coups blancs et 40 coups noirs) jusqu'à l'abandon ou la fin de la rencontre.
4. Le nombre de suites de coups vaut ainsi approximativement (10³)⁴⁰ = 10¹²⁰.

Shannon remarque qu'une machine examinant une variante par microseconde mettrait plus de 10⁹⁰ années pour calculer son premier coup. Il en déduit qu'un programme d'échecs doit évaluer les positions et sélectionner les variantes à approfondir, à la manière d'un joueur humain.

Parties et positions : deux grandeurs distinctes

Il convient de ne pas confondre le nombre de parties (les suites de coups) et le nombre de positions (les configurations des pièces sur l'échiquier). Une même position peut résulter de millions de parties différentes.

Shannon évaluait le nombre de positions à l'aide de la formule 64! / (32! × 8!² × 2!⁶), qui dénombre les manières de placer les 32 pièces de départ sur les 64 cases ; le résultat avoisine 4,6 × 10⁴², qu'il arrondit à « environ 10⁴³ ». L'estimation contemporaine de John Tromp, (4,82 ± 0,03) × 10⁴⁴ positions légales, repose sur une autre démarche : on tire au hasard deux millions de positions parmi un ensemble que l'on sait dénombrer, puis l'on vérifie lesquelles sont réellement atteignables au cours d'une partie, avec l'aide de Peter Österlund pour l'analyse informatique.

Les premiers coups : un décompte exact

En début de partie, le dénombrement reste exact. Les Blancs disposent de 20 coups possibles (16 coups de pions et 4 coups de cavaliers), de même que les Noirs. On obtient :

Valeurs recalculées par programme à partir de la position initiale (dénombrement 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 croît ensuite, car les pièces se dégagent et disposent de davantage de choix : cela justifie l'hypothèse d'une trentaine de coups par position.

D'où provient l'évaluation de 10¹²³ ?

En 1994, le chercheur néerlandais Victor Allis a repris le calcul en modifiant les hypothèses : environ 35 coups possibles par position, et des parties de 80 demi-coups (40 coups de chaque camp). On obtient 35⁸⁰. Pour l'exprimer en puissance de 10, on recourt au logarithme décimal : 80 × log(35) ≈ 80 × 1,544 ≈ 123,5, d'où l'ordre de grandeur de 10¹²³. La méthode reste celle de Shannon, seuls les paramètres changent, ce qui montre à quel point le résultat dépend des hypothèses retenues.

Avec les paramètres exacts de Shannon, 900⁴⁰ vaut en réalité environ 10¹¹⁸ et non 10¹²⁰ : c'est l'arrondi de 900 à 1 000 qui produit ce joli chiffre rond. Pour un ordre de grandeur aussi colossal, l'écart ne change rien en pratique.

Comment l'expliquer à des élèves

Le nombre de Shannon se prête parfaitement au travail sur 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 demander aux élèves de l'écrire au tableau… et de mesurer le temps que cela leur prend.
• Calculer avec les puissances : (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ applique directement la règle (a^m)ⁿ = a^{m × n}.
• Mettre en regard des ordres de grandeur : diviser 10¹²⁰ par 10⁸⁰ donne 10⁴⁰. Quand bien même chaque atome de l'Univers serait un ordinateur, chacun aurait encore à analyser 10⁴⁰ parties.
• Discuter les hypothèses : pourquoi 30 coups par position ? pourquoi 40 coups par partie ? Qu'est-ce qui change avec une partie de 60 coups ? (Réponse : (10³)⁶⁰ = 10¹⁸⁰.)

Face à lui, le nombre de grains de l'échiquier de Sissa, environ 1,8 × 10¹⁹, paraît minuscule : comparer les deux constitue un bon exercice. Voir le calcul de l'échiquier de Sissa.

Est-il possible de « résoudre » les échecs ?

Résoudre un jeu signifie connaître avec certitude le résultat (victoire des Blancs, des Noirs ou nulle) d'une partie jouée parfaitement des deux côtés. Le nombre de Shannon montre qu'on ne peut y parvenir en explorant toutes les parties. Les ordinateurs ont néanmoins résolu toutes les positions comportant peu de pièces, grâce à des tables de finales. Pour faire le point sur la question, le Palais des Échecs s'est demandé si les échecs pourront un jour être résolus.

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

L'échiquier regorge de grands nombres : 2⁶⁴ − 1 grains de Sissa, plus de 26 000 milliards de parcours fermés du cavalier, 92 solutions au problème des huit dames, 204 carrés… Retrouvez-les sur notre page les grands casse-têtes de l'échiquier.