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 sert aussi très bien à travailler les puissances de 10, la notation scientifique et les ordres de grandeur, du collège au lycée. Il reste à comprendre son origine, ce qu'il mesure précisément et ce qu'il laisse de côté.

Nombre de Shannon

Évaluation prudente, d'environ 10¹²⁰, du nombre de parties d'échecs envisageables, avancée par le mathématicien et ingénieur américain Claude Shannon dans son texte « 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 signe l'un des tout premiers articles consacrés à la programmation d'un ordinateur pour jouer aux échecs. Afin de montrer qu'une machine ne peut pas se contenter de calculer toutes les suites de coups, il procède à une estimation rapide :

1. Dans une position courante, on dispose d'environ 30 coups légaux. Ce nombre demeure à peu près stable durant une large part de la partie.
2. Un coup blanc suivi d'un coup noir offre donc environ 30 × 30 = 900 possibilités, que Shannon arrondit à 10³.
3. Une partie typique compte environ 40 coups (40 coups blancs et 40 coups noirs), jusqu'à ce qu'un joueur abandonne.
4. Le nombre de suites de coups est donc voisin de (10³)⁴⁰ = 10¹²⁰.

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

Parties et positions : deux nombres distincts

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

Shannon estimait le nombre de positions à l'aide de la formule 64! / (32! × 8!² × 2!⁶), qui dénombre les façons de répartir les 32 pièces de départ sur les 64 cases ; le résultat avoisine 4,6 × 10⁴², qu'il arrondit à « environ 10⁴³ ». L'évaluation moderne de John Tromp, (4,82 ± 0,03) × 10⁴⁴ positions légales, procède autrement : on tire au hasard deux millions de positions parmi un ensemble dont on sait faire le dénombrement, puis l'on vérifie lesquelles sont effectivement atteignables au cours d'une partie, avec l'appui de Peter Österlund pour l'analyse informatique.

Les premiers coups : un décompte exact

Au début de la partie, on peut compter avec exactitude. Les Blancs disposent de 20 coups possibles (16 coups de pions et 4 coups de cavaliers), et il en va de même pour 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 grimpe ensuite, car les pièces sortent et offrent davantage de choix : cela justifie l'hypothèse d'une trentaine de coups par position.

D'où vient 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 côté). On aboutit à 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 démarche 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 fait 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 n'a guère d'importance pratique.

Comment le présenter en classe

Le nombre de Shannon se prête parfaitement à l'étude des 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 qu'il leur faut.
• Calculer avec les puissances : (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ constitue une application directe de la règle (a^m)ⁿ = a^{m × n}.
• Mettre en regard des ordres de grandeur : si l'on divise 10¹²⁰ par 10⁸⁰, on obtient 10⁴⁰. Autrement dit, même en imaginant que chaque atome de l'Univers soit un ordinateur, chacun aurait tout de même 10⁴⁰ parties à examiner.
• 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¹⁸⁰.)

À côté, le nombre de grains de l'échiquier de Sissa, environ 1,8 × 10¹⁹, semble minuscule : confronter les deux constitue un bon exercice. Voir le calcul de l'échiquier de Sissa.

Est-il possible de « percer » le jeu d'échecs jusqu'au bout ?

Résoudre un jeu signifie savoir avec certitude quel résultat (victoire des Blancs, victoire des Noirs ou nulle) découle d'une partie parfaite des deux côtés. Le nombre de Shannon montre qu'on ne peut pas y parvenir 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 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 d'autres très grands nombres qui peuplent l'échiquier

L'échiquier est une véritable usine à 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.