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

Ce nombre revient souvent pour illustrer la richesse du jeu d'échecs. Il convient aussi très bien pour travailler les puissances de 10, l'écriture scientifique et les ordres de grandeur, du collège jusqu'au lycée. Reste à comprendre son origine, ce qu'il mesure précisément et ce qu'il ne mesure pas.

Nombre de Shannon

Estimation prudente, d'environ 10¹²⁰, du nombre de parties d'échecs possibles, avancé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 : d'où provient le calcul ?

Claude Shannon (1916-2001) est reconnu comme le père de la théorie de l'information. En 1950, il publie l'un des tout premiers articles sur la façon de programmer un ordinateur pour jouer aux échecs. Afin de démontrer qu'une machine ne peut pas se contenter de calculer toutes les suites de coups possibles, il procède à une estimation rapide :

1. Dans une position courante, on compte environ 30 coups légaux. Ce chiffre demeure à peu près stable pendant une bonne partie de la rencontre.
2. Un coup blanc suivi d'un coup noir offre donc environ 30 × 30 = 900 possibilités, que Shannon arrondit à 10³.
3. Une partie type s'étend sur 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 d'environ (10³)⁴⁰ = 10¹²⁰.

Shannon note également qu'une machine examinant une variante par microseconde mettrait plus de 10⁹⁰ années pour calculer son premier coup. Il en tire la conclusion 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 nombres distincts

Il faut distinguer le nombre de parties (les suites de coups) du nombre de positions (les configurations des pièces sur l'échiquier). Une seule et même position peut être atteinte au terme 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 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'estimation actuelle de John Tromp, (4,82 ± 0,03) × 10⁴⁴ positions légales, procède différemment : on tire au hasard deux millions de positions dans un ensemble dont le dénombrement est connu, puis on vérifie lesquelles peuvent réellement surgir au cours d'une partie, avec le concours de Peter Österlund pour l'analyse informatique.

Les premiers coups : un décompte exact

Au départ d'une partie, on peut compter avec précision. 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 de départ, en dénombrant toutes les suites de coups autorisés.

Après seulement deux coups de chaque camp, on dépasse déjà 197 000 suites possibles. Le facteur de multiplication grimpe ensuite, puisque les pièces sortent et offrent davantage de choix : c'est ce qui appuie l'hypothèse d'une trentaine de coups par position.

Comment obtient-on l'estimation de 10¹²³ ?

En 1994, le chercheur néerlandais Victor Allis a repris le calcul avec d'autres 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ù un ordre de grandeur de 10¹²³. La démarche reste celle de Shannon, seuls les paramètres diffèrent, ce qui montre à quel point le résultat dépend des hypothèses retenues.

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 produit ce joli chiffre rond. Pour un ordre de grandeur aussi colossal, l'écart ne change rien en pratique.

Une façon de l'expliquer à l'école

Le nombre de Shannon se prête admirablement à l'étude des puissances de 10, inscrite 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 prend.
• Calculer avec les puissances : (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ illustre directement la règle (a^m)ⁿ = a^{m × n}.
• Mettre en parallèle des ordres de grandeur : diviser 10¹²⁰ par 10⁸⁰ donne 10⁴⁰. Même en imaginant que chaque atome de l'Univers soit un ordinateur, chacun aurait encore à traiter 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¹⁸⁰.)

Le nombre de grains de l'échiquier de Sissa, environ 1,8 × 10¹⁹, paraît minuscule en comparaison : mettre les deux en regard constitue un bon exercice. Voir le calcul de l'échiquier de Sissa.

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

Résoudre un jeu, c'est être capable d'affirmer avec certitude quel résultat (victoire des Blancs, victoire des Noirs ou nulle) découle d'une partie parfaite jouée 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 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 être résolus un jour.

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… Vous les retrouverez sur notre page les grands casse-têtes de l'échiquier.