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 paque 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 blancs 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 129 bits.

On a donc

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

et donc

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

Remarques

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

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

Mais cette analyse ne tient pas compte

• de la règle des 50 coups dans prise ni mouvement de pions (cette information n'est pas incluse dans la clé - elle représenterait au pire 6 bits additionnels)
• de la règle des répétitions triples de position (cette information représenterait 2 bits additionnels)
• de la présence de reines multiples dans un ou dans les deux camps

Il est cependant 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 peut se faire en prévoyant des variantes dynamiques dans l'ensemble des codes 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³⁸