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 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 digit) nécessaire à la représentation de toute position légale.

Il s'ensuit que

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

Valeur de N_pb

Si 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}$