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

De Lillois Fractale Wiki
(Redirigé depuis BAD)
Aller à la navigation Aller à la recherche

Débat

Le nombre de positions légales au jeu d'échecs (Np) a été estimé de diverses manières.

Par légale, on entend "conforme aux règles", et donc résultant de coups majoritairement très faibles, voire étranges, par rapport au but du jeu.

Dans l'article sont déterminés:

  • un majorant large de Np (Ng = 4.5 x 1043).
  • un minorant de Np (6.8 x 1038)
  • un majorant de Np (4.4 x 1040)
  • un ordre de grandeur très probable de Np (1039)

Ces nombres sont tous dérivés de Ngb, le nombre de bits (binary digits) nécessaire à la représentation de toute position légale (théorie de l'information), et de Ng, le nombre de combinaisons possibles de Ngb bits.

Cet article n'est pas le seul rédigé au sujet des échecs. D'autres sont accessibles à partir de la page générale Echecs.

Valeur de Ngb

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 de construction de la clé binaire est une séquence d'opérations faisant appel à une fonction addBit(), qui ajoute un ou plusieurs bits à un paquet de bits 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 80 bits (1 bit pour le trait, 4 bits pour les autorisations de roque, 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 où une prise en passant serait possible, on peut vérifier qu'il faudrait à l'algorithme décrit plus haut 161 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 de 1 à 16 bits, suivant le nombre de pièces restées sur leur rangée de départ: 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 évidente de l'algorithme (non documentée ici pour ne pas encombrer l'article) descend le nombre de bits nécessaires de 161 à 145.  D'autres améliorations tirant parti de l'élimination de positions impossibles (non-légales) pourraient encore être incluses, mais leur bénéfice est probablement mineur.

Mais en pratique on a donc

et donc

Cette valeur à droite de l'inégalité (2161, soit ?? x 10??) est donc un majorant (large) de Np.

Remarques

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

  1. le trait
  2. les capacités de roque des deux camps
  3. 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, ce qui alourdirait le nombre de bits inclus dans le codage. 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 repousserait la limite de 21 bits, toute prise en passant devenant impossible : delta = 2x(6x6 - 8x3) - 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 réponse 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é permettraient d'inclure les informations énoncées ci-dessous, et au moins les dames multiples dans le paquet global de 145 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).

Démarche probabiliste

Pour continuer le raisonnement, il faut passer par une approche probabiliste.

Le codage sur 145 bits offre Ng = 2145 combinaisons possibles.

Ces positions sont toutes distinctes.

La question posée à présent est la suivante. Parmi ces combinaisons lesquelles correspondent à une position valide ?

La validité d'une position est une question délicate, discutée plus bas.

Déjà les points suivants peuvent être énoncés:

  • l'écrasante majorité des positions générées est incompatible avec les possibilités de roque, ce qui rend les 4 bits de roque superflus en terme d'information. Ceci ramène les bits utiles à 141.
  • l'écrasante majorité des positions générées est incompatible avec une prise en passant, ce qui rends les 4 bits de prise en passant superflus en terme d'information. Ceci ramène les bits utiles à 137.
  • le nombre de combinaisons à explorer serait donc de l'ordre de 2137

La probabilité de validation d'une position Pv est difficile à prévoir, mais nous pouvons estimer qu'elle est certainement entre 2-8 et 2-2 (ceci se base sur des explorations algorithmiques et des tests préliminaires).

En conséquence, il apparaît que

2129 < Np < 2135

Soit approximativement

6.8 x 1038 < Np < 4.4 x 1040

Validation d'un position

Un algorithme intéressant permettrait de resserrer considérablement l'intervalle dans lequel se trouve enfermé Np.

Cet algorithme consisterait à générer aléatoirement des clés de 137 bits, et à fabriquer les positions correspondantes, dont on testerait la validité. Une répétion suffisante fournirait un estimateur très précis de Pv, et donc une estimation très précise de Np.

Cette méthode donnerait donc une réponse optimale à la question de l'évaluation de Np, mais elle requiert une procédure assez complexe: celle qui teste la validité d'un position. Cette question semble simple au premier abord, mais elle est en réalité d'une affreuse complexité, parce que le nombre de cas et de variables à traiter est considérable.

Une position avec le joueur non au trait mis en échec est-elle valide? Simple. Non.

Une position avec deux fous blancs sur cases blanches est-elle valide? Première réponse : non. Réponse correcte: oui, dans la mesure ou un fou peut être le résultat d'une promotion.

Une position avec 10 cavaliers dans le même camp est-elle valide? Oui, elle peut l'être, si 8 pions ont été promus en cavaliers. Etc...

Conclusion

Le nombre exact de positions légales possibles dans une partie d'échecs est proche en grandeur de 1039, et il est compris entre 6.8 x 1038 et  4.4 x 1040.

Une fourchette bien plus étroite serait obtenue, si une fonction de validation de position efficace était disponible.