Nombre de Shannon : à combien se chiffrent les parties d'échecs possibles ?

On cite souvent le nombre de Shannon pour illustrer la richesse du jeu d'échecs. C'est aussi un bon prétexte 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. Depuis la Belgique, on peut d'ailleurs l'aborder avec les élèves sans rien perdre de sa portée.

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 : d'où sort 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 textes sur la façon de programmer 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 ordinaire, on compte une trentaine de 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 ainsi environ 30 × 30 = 900 possibilités, que Shannon arrondit à 10³.
3. Une partie type s'étend sur une quarantaine de coups (40 coups blancs et 40 coups noirs), jusqu'à ce qu'un joueur abandonne.
4. Le nombre de suites de coups vaut donc à peu près (10³)⁴⁰ = 10¹²⁰.

Shannon ajoute qu'un ordinateur examinant une variante par microseconde mettrait plus de 10⁹⁰ années à calculer son premier coup. Il en tire la conclusion qu'un programme 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) et le nombre de positions (les dispositions des pièces sur l'échiquier). Une seule et même position peut être atteinte par des 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 autrement : on tire au hasard deux millions de positions dans un ensemble dont on sait faire le dénombrement, puis on vérifie lesquelles sont réellement atteignables au cours d'une partie, avec l'aide de Peter Österlund pour l'analyse informatique.

Les tout premiers coups : un décompte précis

En début de partie, le décompte reste exact. 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 (dénombrement de toutes les séquences de coups légaux).

Après seulement deux coups de chaque camp, on dépasse déjà 197 000 suites possibles. Le facteur de multiplication grimpe ensuite, car les pièces se déploient et offrent davantage de choix : c'est ce qui justifie 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 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 est exactement 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 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 pratiquement aucune importance.

Présenter le sujet en classe

Le nombre de Shannon se prête admirablement à l'étude des puissances de 10, notion 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 leur prend.
• Calculer avec les puissances : (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ illustre directement la règle (a^m)ⁿ = a^{m × n}.
• Mettre en regard des ordres de grandeur : diviser 10¹²⁰ par 10⁸⁰ aboutit à 10⁴⁰. Autrement dit, même si chaque atome de l'Univers jouait le rôle d'un ordinateur, chacun aurait encore à examiner 10⁴⁰ parties.
• Discuter les hypothèses : pourquoi retenir 30 coups par position ? pourquoi 40 coups par partie ? Qu'est-ce qui change pour 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é : 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 savoir avec certitude quel résultat (victoire des Blancs, 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 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 interrogé sur la possibilité de résoudre un jour les échecs.

Le nombre de Shannon et d'autres grands nombres liés à l'échiquier

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