Aucune position d’échecs atteignable ne permet plus de 218 coups

• Il n’existe aucune position permettant plus de coups que la position d’échecs à 218 coups publiée en 1964 par Nenad Petrović
• Comme il est irréaliste d’explorer toutes les positions, la limite a été démontrée grâce à des techniques d’optimisation mathématique et de modélisation informatique
• La suppression des pièces inutiles, l’autorisation d’un placement partiel des pièces et la simplification du roque ont permis de réduire efficacement l’espace de recherche
• Au final, l’outil d’optimisation Gurobi a confirmé que 218 coups constitue le maximum, tout en vérifiant aussi d’autres records comme 144 coups (sans promotions)
• Cette recherche permet aux développeurs de moteurs d’échecs et d’outils de compression de lever l’incertitude autour de la limite maximale du nombre de coups

---

Introduction : la controverse autour de la position d’échecs à 218 coups

Depuis que le grand maître de composition échiquéenne Nenad Petrović a publié en 1964 une position à 218 coups, les tentatives pour battre ce record se sont multipliées. L’auteur, en tant qu’informaticien, a voulu clore définitivement la question en analysant les positions au moyen de l’informatique. Il existe environ 4,8 × 10^44 positions d’échecs atteignables, mais une exploration d’une telle ampleur est impossible en pratique.

L’introduction de l’optimisation mathématique

Réduction des pièces et combinaisons inutiles

• Les cas où des pièces noires supplémentaires augmentent réellement le nombre de coups sont limités
  • par exemple lorsqu’elles peuvent être capturées par un pion blanc, ou lorsqu’elles permettent d’éviter une situation d’échec sur le roi adverse
• La plupart des pièces noires peuvent être retirées sans affecter le nombre maximal de coups
• Tant que le nombre de pièces autorisé le permet, il est possible de remplacer les pièces noires par des pièces plus faibles ou d’ajuster leur placement sous certaines contraintes (comme les clouages)
• Pour les pièces blanches, la situation est inverse : les remplacer toutes par des pièces fortes comme des dames peut produire une position illégale, ce qui impose des ajustements plus fins

Situations d’échec et limites sur le nombre de coups

• Une position où le roi noir est en échec n’est pas légale, il n’est donc pas nécessaire de l’examiner
• Lorsque le roi blanc est en échec, ses mouvements sont fortement limités (120 coups au maximum), ce qui rend impossible d’atteindre 218 coups
• Il est donc possible de restreindre la recherche aux seules positions sans échec

Placement partiel des pièces et modélisation mathématique

Pour réduire la complexité combinatoire, l’étude adopte un modèle assoupli avec placement partiel (fractional) des pièces, mouvements partiels et certaines règles d’échecs relâchées.

• Par exemple, une pièce peut être à 27,3 % sur e4 et à 72,7 % sur une autre case
• Cette approche a été implémentée sous forme de programmation linéaire en nombres entiers (ILP, Integer Linear Programming) avec des outils d’optimisation modernes comme Gurobi
• Au départ, les limites de mémoire et de temps ont posé problème (épuisement mémoire après environ 55 000 secondes)
• Pour simplifier davantage l’espace de recherche, des mesures supplémentaires ont été appliquées : simplification du roque, ignorance des échecs, ignorance des clouages, simplification des conditions de prise en passant, etc.

Optimisation et conclusion

Au final, le modèle a été amélioré, notamment par l’introduction de contraintes auxiliaires bloquant l’exploration de combinaisons inutiles, puis l’optimisation a été menée à son terme avec Gurobi.

• La borne supérieure a été progressivement resserrée de 305 coups à 271,67 coups, puis à 218 coups
• Il a été confirmé que seules 12 positions représentatives permettant 218 coups sont atteignables
• Il a été démontré que ces positions sont légales et atteignables sans difficulté au moyen de proof games

En outre, l’étude a aussi vérifié un maximum de 144 coups sans promotion, un maximum de 288 coups dans des positions illégales, ainsi qu’un record de 271 coups dans des positions légales mais inatteignables.

Résultats et portée

• Grâce à ces résultats, les développeurs de moteurs d’échecs et les chercheurs en algorithmes de compression peuvent être certains qu’une limite de 256 coups suffit pour la conception mémoire et d’autres aspects techniques
• Il est désormais démontré mathématiquement qu’aucune position atteignable par une suite légale de coups ne permet plus de 218 coups

Résumé de la FAQ

• Une partie d’échecs peut durer plus de 218 coups, mais cette étude traite du nombre maximal de choix possibles à un tour donné
• Si certaines positions semblent inatteignables, il est indiqué qu’il peut exister plusieurs chemins, par exemple lorsque le coup précédent se termine par une capture
• La méthode applique une technique d’oracle mathématique capable d’éliminer rapidement les combinaisons absolument impossibles dans un espace combinatoire gigantesque
• Le code utilisé ainsi que la validité mathématique des preuves produites sont aussi publiés, afin de garantir la fiabilité des résultats

Travaux futurs et pistes de recherche supplémentaires

Cette technique pourrait être appliquée à divers autres problèmes échiquéens, comme le plus grand nombre de captures, le plus grand nombre de pat, le plus grand nombre d’échecs, le plus grand nombre de mats, ou encore le plus grand nombre de mats en 2 coups. Dans certains cas, des algorithmes d’optimisation créatifs distincts pourraient toutefois être nécessaires.

Conclusion

• 218 coups constitue le nombre officiel maximal de coups possibles en un tour dans une position d’échecs
• D’un point de vue pratique, les logiciels d’échecs et les chercheurs peuvent concevoir leurs structures autour de 218 (ou 256)
• Le code associé et les résultats de l’optimisation sont publiés sur GitHub

Référence

• Liens vers la position à 218 coups de Nenad Petrović, les proof games et positions comme celle de Jenő Bán à 144 coups (sans promotion)
• Explications détaillées et code disponibles dans le dépôt GitHub

[GN⁺]

Commentaires Hacker News

• Ils ne le disent pas explicitement, mais ici cela veut dire « dans cette position, le joueur dispose de 218 coups légaux possibles »
  • Je suis étonné de voir que je lisais cet article de travers depuis le début, merci. J’avais compris « le nombre maximal de coups nécessaires pour atteindre une position aux échecs est de 218 ». Je me demandais donc pourquoi cet article n’avait absolument aucun sens.
  • Moi, je comprenais ça comme « combien de coups faut-il dans une partie pour atteindre cette position ? »
  • Oui, c’est vraiment étrange que l’article n’utilise jamais l’expression « coups possibles ». Le mot-clé, c’est « possibles ». L’article dit sans cesse quelque chose comme « avoir des coups », mais c’est une tournure peu familière pour le grand public. (C’est peut-être plus courant dans le jargon des échecs.)
  • Merci. J’étais confus à propos de cet article ; je pensais qu’il parlait de la position qui nécessitait le plus grand nombre de coups à atteindre.
• Je veux absolument saluer Lichess. C’est un service fantastique, avec du contenu gratuit, et on y trouve gratuitement des fonctions que Chess.com fait payer. Il y a aussi énormément de variantes.
  Le niveau de jeu sur des variantes comme le 960 ou le Crazyhouse y est bien supérieur à celui de Chess.com.
  • C’est gratuit, offre les mêmes fonctions qu’un serveur commercial, c’est open source et pensé pour les développeurs. Il n’y a pas de publicité (même pas pour les comptes gratuits), et l’organisation est transparente, sous droit français.
    C’est littéralement absurdement bien. Si vous le pouvez, je recommande de faire un don.
• Dans https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow, l’auteur explique qu’il a d’abord supprimé certaines règles complexes, avec l’intention de les réintroduire si nécessaire (si la solution obtenue violait ces règles).
  Ce qui est intéressant, c’est que les solveurs MILP prennent déjà en charge ce type de traitement. Le terme technique est row generation, qu’on emploie généralement quand on écrit le problème sous forme matricielle, avec les lignes comme contraintes et les colonnes comme variables.
  Ajouter de nouvelles lignes de façon dynamique revient à n’introduire des contraintes que lorsqu’elles sont violées.
  Cette approche est surtout utilisée pour résoudre le problème du voyageur de commerce (Traveling Salesman Problem).
  (À noter que Wikipédia a un article sur Column generation, mais pas sur le row generation.)
  • Bonjour, je suis l’auteur de l’article sur Lichess.
    Le fait d’assouplir ou d’omettre certaines règles des échecs a aussi eu un effet sur le choix des variables. Avant d’entrer dans la modélisation mathématique, j’ai essayé des choses comme les lazy constraints, mais sans gain de performance significatif. Par exemple, le simple fait de ne pas tenir compte de l’éventualité que le roi blanc soit en échec a permis de nombreuses simplifications.
  • En général, on appelle plutôt ça des lazy constraints (explication ici).
  • Je me demande vraiment si un solveur MILP peut terminer sur un espace de recherche aussi gigantesque ; mon intuition serait plutôt que non.
• Question honnête par curiosité : si le solveur de programmation entière de Gurobi n’a pas trouvé de meilleure solution que 218, est-ce que cela garantit qu’il n’en existe pas de meilleure ? Et est-ce équivalent à une preuve mathématique ?
  (En supposant, pour la discussion, que Gurobi n’a pas de bug et qu’il n’y en a pas non plus dans la définition du problème ni dans l’implémentation de l’auteur.)
  Je me demande si Gurobi pourrait être coincé dans un optimum local, ou s’il a réellement prouvé qu’il s’agit de l’optimum global.
  • Gurobi ne fournit pas seulement la meilleure solution entière trouvée jusque-là, mais aussi une borne sur la meilleure solution possible. Cette borne s’appuie sur diverses techniques, comme la relaxation linéaire du problème, les plans de coupe, etc. Donc, si le solveur n’a pas de bug, c’est bien l’optimum.
  • L’auteur ici !
    Si Gurobi et mon code fonctionnent comme prévu, et si je n’ai commis aucune erreur logique dans la simplification du modèle d’échecs, alors mon résultat prouve bien que « parmi les positions d’échecs atteignables depuis la position initiale par une suite légale de coups, le nombre maximal de coups légaux possibles a pour borne supérieure et inférieure 218 ». Autrement dit, Gurobi a démontré sur l’ensemble de l’espace de recherche qu’« il n’existe rien de meilleur ».
  • Je ne sais pas précisément comment Gurobi a été appliqué ici, mais en général ce genre de solveur d’optimisation combinatoire construit un arbre de preuve montrant que, pour toute affectation des variables, aucune meilleure solution ne peut exister. Dans les cas simples, on peut même inspecter cet arbre directement et suivre le raisonnement par contradiction. Dans le cas de cet article, on peut s’attendre à ce que l’arbre de preuve soit gigantesque. Mais si on le veut vraiment, on peut l’examiner.
  • En théorie, ce n’est pas une preuve ; en pratique, c’est pratiquement l’équivalent d’une preuve.

• Il n’existe aucune position d’échecs atteignable avec plus de 218 coups
  Formuler cela comme « il n’existe aucune position avec plus de 218 coups légaux disponibles » serait bien plus clair.

Vérifier environ 8.7x10^45 positions d’échecs atteignables ?
Ce chiffre est en fait une surestimation.
https://github.com/tromp/ChessPositionRanking estime de manière plus précise le nombre de positions d’échecs légales à environ 4.8x10^44.

• Cette estimation, ce n’est pas juste un facteur 20 d’écart ? À cette échelle, ça ne me semble pas énorme.
• L’un parle de positions « légales », l’autre de « l’espace total du problème ».
  Du point de vue du calcul, l’espace total du problème est plus important, parce qu’il faut tous les « calculer » avant même de déterminer s’ils sont légaux ou non. Il n’existe pas de méthode simple pour itérer uniquement sur les positions légales.
• Bonjour à tous,
  un proche m’a signalé que mon article était discuté ici.
  Désolé d’avoir choisi un titre peu clair ; j’espère qu’il est maintenant plus clair. Merci pour les retours et pour les mots chaleureux.
  Si vous avez des questions sur des preuves de faits similaires aux échecs, je peux aussi y répondre ^^
  Merci
  Tobi
  • Donc, pour être sûr : cela signifie qu’aucune position de l’échiquier ne permet plus de 218 coups possibles ? C’est bien cela ?
• Quel est le nombre minimal de bits nécessaire pour représenter un échiquier atteignable ?
  Mise à jour : l’article dit qu’il y a environ 8.7x10^45 positions d’échecs atteignables, et https://github.com/lechmazur/ChessCounter utilise ce nombre comme borne supérieure.
  (Cela correspond à environ 153 bits.)
  • Si c’est plutôt de l’ordre de 4.8x10^44, alors log2(4.8x10^44) donne 149 bits.
    Mais pour décoder efficacement, il faut 153 bits, en prenant le plafond du log2 du nombre recommandé par le projet ChessPositionRanking (8726713169886222032347729969256422370854716254). ChessCounter ne fournit pas de code de décodage efficace.
  • Les rois peuvent aller sur n’importe laquelle des 64 cases.
    C’est aussi le cas des tours / dames / cavaliers, mais comme ils peuvent avoir été capturés, il faut en tout 65 états pour chacun de ces 5 types de pièces.
    Les fous, eux, ne peuvent aller que sur la moitié des cases, donc 33 états chacun.
    Les pions peuvent être promus de 4 façons, capturés, et selon le cas avoir environ 20 à 30 positions possibles ; au total, cela fait grosso modo 290 états par pion.
    Avec cette méthode, il faut environ 112 bits pour représenter l’état du plateau pour une couleur, soit 224 bits au total pour les deux camps après arrondi.
    L’en passant et les restrictions de roque n’exigent pas de bits supplémentaires après arrondi, puisqu’il suffit d’ajouter quelques états à certaines pièces.
    C’est probablement la représentation la plus compacte possible pour un encodage de plateau à longueur fixe.
    Avec une représentation creuse (sparse), comme les deux rois sont toujours présents, on peut représenter les pièces encore en vie avec un nombre décimal à n chiffres et leurs positions avec n+2 nombres sur 64 bits, plus un peu d’information supplémentaire pour le roque, l’en passant, etc. Si environ la moitié des pièces ont disparu, cela demande en moyenne autour de 180 bits pour représenter l’état du plateau.
    L’historique des coups demande aussi environ 10 bits par coup (une paire noir/blanc, un ply valant 5 bits), donc on peut remonter à environ 18 coups. C’est un peu plus court que le milieu de la durée moyenne d’une partie d’échecs.
    Pour compresser davantage, il faudrait apparemment mettre en œuvre un dictionnaire gigantesque.
  • Le type de pièce et sa couleur peuvent être codés sur 4 bits.
    Donc si on encode tout l’échiquier en longueur fixe, cela fait 64*4=256 bits = 32 octets.
    Ou bien, avec une représentation à longueur variable ne stockant que les pièces, on utilise 6 bits pour l’index de chacune des 64 cases, soit nombre_de_pièces*10 bits.
    Par exemple, la position initiale fait 32*10=320 bits = 40 octets.
  • La valeur « restricted » à 8.7e45 dans ce GitHub limite certains schémas de promotion de pions.
    La valeur « general » à 5.68e50 est la véritable borne supérieure, avec toutes les promotions possibles autorisées.
• Le pion noir en b2 réduit fortement le nombre de coups possibles des autres pièces.
  Ce pion n’a qu’un seul coup possible (prendre le cavalier à côté). S’il n’était pas là, quatre dames blanches et le cavalier pourraient aller en b2. Mais en réalité, ces coups ne peuvent pas exister, car le roi noir est déjà échec et mat.
  Il est tentant de déplacer la dame en e5 ailleurs afin d’éviter un mat immédiat tout en libérant davantage la case b2.
  P.-S. : ce pion semble devoir rester en vie à cet endroit pour éviter le pat.
  • Le pion noir en b2 ne peut pas bouger dans une position où c’est aux blancs de jouer.
    Et si c’était au tour des noirs, il ne pourrait pas non plus bouger, car le roi est cloué par la dame blanche en e5. Sans ce clouage, il pourrait avoir 4 coups possibles. La sous-promotion serait aussi possible.
  • Moi aussi, l’expression « les pièces noires sont inutiles » m’a perturbé. J’ai pensé qu’on pourrait transformer une des deux dames qui se font face en dame noire, pour qu’elles puissent se prendre l’une l’autre… puis j’ai fini par comprendre que « seule une couleur peut jouer ».
  • L’auteur ici.
    La position est aux blancs. Même si le pion b2 n’était pas cloué au roi par la dame blanche, le pion noir ne pourrait pas bouger.
    Le pion b2 est indispensable pour protéger le roi noir contre l’échec. Sinon, la position elle-même ne serait pas légale.
    J’ai vraiment tout vérifié avec beaucoup d’attention, donc vous pouvez être tranquilles : il a été impossible de construire une position dépassant 218 coups pour les blancs. Mais je suis surpris et reconnaissant de voir autant d’intérêt pour mon article, haha ^^
  • C’est aux blancs de jouer. Si c’était aux blancs alors que les noirs sont en échec, la position ne serait pas légale et donc inatteignable. Il n’y aurait aucun moyen de l’obtenir légalement au tour précédent des noirs.
    On pourrait croire qu’en remplaçant un des pions noirs par un cavalier blanc on augmenterait le nombre de coups, mais les deux cavaliers sont déjà présents, et tous les pions ont déjà été promus, donc ce n’est pas possible. (Et si l’on changeait les deux pions, il deviendrait impossible pour les noirs d’atteindre cette position au tour précédent.)
• Je suis perdu. Mais après le modèle à 271, je me demande quels changements ont permis d’obtenir la solution optimale. L’article dit seulement « avec ce modèle amélioré... »
  • L’auteur ici !
    Tu as lu l’article en entier ?
    Ce n’est pas 271, mais 271.666... :) Ce chiffre provient du modèle où toutes les décisions (0 ou 1) sont relaxées en valeurs continues (0.0 à 1.0 et entre les deux). Autrement dit, on peut supposer qu’une pièce existe à hauteur de 0,23. La possibilité d’un coup peut aussi être traitée comme une probabilité, par exemple 0,843.
    Ce genre de « magie noire » permet d’accélérer énormément les calculs et peut produire un nombre de coups supérieur à ce qui est réellement possible.
    On s’en sert donc pour éliminer rapidement des sous-espaces partiels potentiellement mauvais. Sans ce type de technique, il serait impossible d’explorer exhaustivement l’espace de recherche complet.
• Est-ce que je rate quelque chose, ou bien la position montrée au début n’est-elle pas en fait inatteignable ? C’est aux blancs de jouer, les pions noirs sont dans leur position de départ, et le roi n’a même pas de case vide adjacente ; il semble enfermé par les pièces et les pions, donc cette position paraît impossible à atteindre.
  • Il y a ici une preuve que cette position est bien atteignable : https://lichess.org/study/PLtuv3v5/zWPNxbSA
    Au passage, je pense que vous vous trompez en croyant que les pions noirs sont dans leur position de départ. En réalité, le pion noir a avancé jusqu’au côté opposé du plateau (dans le camp blanc).
  • Le pion noir est dans le camp blanc (aux 1er et 2e rangs).