Nombre de positions légales au jeu d'échecs
Débat
Le nombre de positions au jeu d'échecs (Np) a été estimé de diverses manières, peu rigoureuses.
Dans l'article qui suit se trouve calculé le nombre de Gonze Ng.
Ce nombre Ng est un majorant du nombre Np.
En fait Np est dérivé de Npb, le nombre de bits (binary digit) nécessaire à la représentation de toute position légale.
Il s'ensuit que
Valeur de Npb
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
Remarques