Nombre de positions légales au jeu d'échecs

Débat

Le nombre de positions au jeu d'échecs (N_p) a été estimé de diverses manières, peu rigoureuses.

Dans l'article qui suit se trouve calculé le nombre de Gonze N_g (ce nombre, calculé plus loin est environ 6.8 x 10³⁸).

Ce nombre N_g est un majorant du nombre N_p.

$N_{p}<N_{g}$

En fait N_p est dérivé de N_pb, le nombre de bits (binary digits) nécessaire à la représentation de toute position légale.

Il s'ensuit que

$N_{p}=2^{N_{pb}}$

Valeur de N_pb

Imaginons qu'un programme doit établir une table reprenant des positions d'échecs en utilisant un clé aussi compacte que possible.

Ce qui suit est (en langage simili informatique) l'algorithme de construction de la clé.

Cet algorithme est basé sur l'utilisation de code à longueur variable non ambigu, type code de Huffman. Dans un tel code, différents objets sont représentés  par des séquences de bits de longueur variable, mais l'ensemble des codes doit posséder une propriété simple mais vitale (nécessaire au décodage): aucun des codes ne peut constituer une séquence initiale d'un autre code.

Pour l'algorithme qui nous intéresse, les codes suivants seront utilisés pour chacune des 64 cases:

0 : case vide

1... : case occupée

10... : case occupée par un composant blanc

11... : case occupée par un composant noir

101 : pion blanc

111 : pion noir

100... : pièce blanche

110... : pièce noire

10011 : tour blanche

10010 : fou blanc

10001 : cavalier blanc

100001: dame blanche

100000 : roi blanc

11011 : tour noire

11010 : fou noir

11001 : cavalier noir

110001: dame noire

110000 : roi noir

On peut vérifier qu'un tel code vérifie la condition énoncée plus haut.

L'algorithme est une séquence d'opérations faisant appel à une fonction addBit(), qui ajoute un ou plusieurs bits à un paquet de bit utilisé comme clé d'identification de la position.

Si le trait est au noirs: addBit(1) sinon addBit(0)

Si les blancs peuvent encore roquer addBit(1) sinon addBit(0)

Si les noirs peuvent encore roquer addBit(1) sinon addBit(0)

Pour chaque rangée { pour chaque colonne { addBit(code(case[rangée,colonne])) }

Si une prise en passant est impossible addBit(0), sinon addBit(i1,i2,i3)                 # note i1,i2,i3 identifient binairemnent la colonne du pion prenable en passant

Combien de bits seront ainsi remplis?

Pour une position minimale, où ne figurent sur l'échiquier que les deux rois, il faut 78 bits (3 bits pour le trait et les roques, 62 bits pour les case vides, 2x6 bits pour le deux rois, 1 bit pour l'absence de prise en passant.

Pour une position maximale, où toutes les pièces seraient présentes, et ou une prise en passant serait possible, on peut vérifier qu'il faudrait à l'algorithme décrit supra 129 bits.

Cependant il n'a pas été tiré parti dans l'algorithme simpliste précédent du fait que les pions blancs et noirs ne peuvent être présents sur les rangées extrêmes, ce qui implique une réserve de rendement dans l'algorithme. La mise en place de cette amélioration rapporte 16 bits: le troisième bit des codes (bit indiquant s'il s'agit d'un pion ou d'un non-pion) peut être retiré des premières et dernières rangées.

Cette amélioration de l'algorithme (non documentée ici pour ne pas encombrer l'article) descend le nombre de bits nécessaires de 129 à 113. 

On a donc

$78\leq N_{pb}\leq 113$

et donc

$2^{78}\leq N_{p}\leq 2^{113}$

Remarques

L'analyse ci-dessus inclut dans la description d'une position:

• le trait
• les capacités de roque des deux camps
  
• les options de prise en passant

Mais cette analyse ne tient pas compte

1. de la règle des 50 coups sans prise ni mouvement de pions (cette information n'est pas incluse dans la clé - elle représenterait au pire 6 bits additionnels)
2. de la règle des répétitions triples de position (cette information représenterait 2 bits additionnels)
3. de la présence de reines multiples dans un ou dans les deux camp. De ce fait il pourrait y avoir au pire dans chaque camp 7 reines, mais aucun pion (cette situation assez alambiquée résulte de quatre prises de pions, et pousserait la limite de 9 bits, toute prise en passant devenant impossible : delta = 6x6 - 8x4 - 3 ).

On peut discuter le fait que les composants (1) et (2) font partie de la position ou d'une partie, c'est à dire une séquence de positions et de coups. La seconde option est plus légitime en terme de théorie de l'information.

De toute manière, il est tout à fait raisonnable de penser que des modifications générales de l'algorithme de construction de la clé permetraient d'inclure les informations énoncées ci-dessous dans le paquet global de 129 bits. Cela pourrait se faire en prévoyant des variantes dynamiques dans la technique de codage et dans l'algorithme (qui deviendrait sensiblement plus complexe, plus fourchu).

Conclusion

Le nombre de positions légales dans une partie d'échecs est inférieur à 2¹²⁹, soit environ 6.8 x 10³⁸