Un moteur d’échecs minimax 2-ply implémenté avec 84 688 expressions régulières

• Regex Chess est un moteur minimax à 2-ply qui choisit sur l’échiquier un coup légal et « pas complètement mauvais » en exécutant simplement, dans l’ordre, 84 688 substitutions par expressions régulières
• L’état est stocké dans une seule chaîne contenant à la fois pile et variables, et des commandes comme push, pop, la lecture et l’affectation de variables sont traitées via des substitutions par expressions régulières
• Les branchements conditionnels sont simulés en modifiant le marqueur %%, qui représente un état actif, et les substitutions globales permettent une exécution parallèle de type SIMD en traitant plusieurs états d’un coup
• Le moteur génère tous les coups légaux en états parallèles et évalue aussi les réponses de l’adversaire, mais ne pousse pas jusqu’à une recherche profondeur 3 qui vérifierait entièrement la légalité de ces réponses adverses
• Au départ, il lui fallait environ 30 minutes pour répondre à un seul coup, mais la suppression de variables intermédiaires, l’optimisation du matching, des commandes spécialisées et la parallélisation ont ramené l’implémentation finale à 1 à 10 secondes selon la position

---

Structure de base de Regex Chess

• Regex Chess est entièrement composé d’une liste de 84 688 expressions régulières
• La structure d’exécution est simple
  • parcourir la liste des expressions régulières dans l’ordre
  • appliquer chaque motif et sa chaîne de remplacement à la chaîne représentant l’état courant de l’échiquier
  • afficher l’état final à l’écran
• L’entrée n’est pas du PGN, mais un format par coordonnées qui concatène case de départ et case d’arrivée, comme e2e4
• Le code du projet est disponible sur GitHub

Un CPU à base d’expressions régulières

• Au lieu d’écrire directement les règles des échecs en expressions régulières, l’auteur commence par construire un petit ordinateur fonctionnant avec des expressions régulières
• Cet ordinateur utilise un jeu d’instructions avec exécution conditionnelle sans branchement, exécution SIMD, et manipulation de pile et de variables
• L’état courant est représenté par une seule chaîne
  • %% marque le début d’un état d’exécution actif
  • sous #stack: s’empilent les éléments de la pile
  • les variables sont stockées sous la forme #variable: valeur

• Manipulation de la pile et des variables

  • push cherche l’en-tête %%\n#stack:\n et insère une valeur juste en dessous pour la placer au sommet de la pile
  • pop supprime la ligne placée immédiatement sous #stack: pour retirer la valeur au sommet de la pile
  • la lecture d’une variable consiste à chercher #nom_de_variable: dans la chaîne d’état, copier sa valeur puis l’ajouter au sommet de la pile
  • l’affectation de variable gère à la fois le cas où la variable existe déjà et celui où elle n’existe pas encore
    • si elle existe, sa valeur est remplacée par la valeur présente sur la pile
    • sinon, une nouvelle ligne de variable est ajoutée
  • des marqueurs temporaires, comme des accents graves, empêchent qu’une même instruction soit réappliquée dans le mauvais ordre

Exécution conditionnelle sans branchement et limites sur les boucles

• L’exécution conditionnelle est implémentée avec cond(tag) et reactivate(tag)
• Si le sommet de la pile vaut False, le marqueur actif %% devient %tag, ce qui empêche les instructions suivantes de s’appliquer à cet état
• Plus tard, reactivate(tag) transforme %tag en %% pour réactiver cet état
• Cette méthode permet de simuler une exécution conditionnelle sans branchement explicite
• Comme le programme n’est qu’une liste séquentielle d’expressions régulières, il ne peut pas exécuter de boucles directement
  • il n’est donc pas Turing-complet
  • en revanche, les calculs bornés comme la génération du coup suivant aux échecs peuvent être traités en déroulant les boucles

Exécution parallèle via les substitutions globales

• Comme les substitutions par expressions régulières s’appliquent globalement à toute la chaîne, on peut placer plusieurs états d’exécution %% dans une seule chaîne d’état, et une même instruction s’applique alors à plusieurs états simultanément
• Par exemple, si deux piles contiennent chacune deux entiers, exécuter binary_add() réalise les deux additions en même temps
• fork_inactive(tag) duplique l’état actif courant et place la copie dans un état tagué inactif
• fork_bool(variable) divise un état en deux, l’un avec la valeur True, l’autre avec la valeur False
• Cette structure sert, aux échecs, à évaluer simultanément plusieurs positions possibles au lieu de les traiter une par une

Assembleur macro et exécution symbolique

• Le moteur n’est pas écrit uniquement à la main en expressions régulières : il utilise un assembleur macro qui convertit un programme de style Python en petites séquences d’instructions
• Un code de style Python comme fib() est transformé en une liste d’instructions comme push, lookup, binary_add, assign_pop
• Au lieu d’un parseur traditionnel et d’une génération de code classique, l’auteur utilise l’exécution symbolique (symbolic execution)
  • les objets variables ne sont pas de vrais dictionnaires, mais des objets spéciaux qui enregistrent les opérations effectuées
  • a = b + 1 est enregistré sous la forme lookup('b'), push(1), binary_add(), assign_pop('a')
• Les if enregistrent à la fois le chemin vrai et le chemin faux, puis les fusionnent
  • lorsqu’une branche conditionnelle est rencontrée, deux chemins sont créés dans l’arbre d’appels
  • en retraçant plusieurs fois, l’outil choisit la branche la moins visitée pour remplir les deux chemins
  • le point de fusion est converti en instruction reactivate

Génération des coups aux échecs

• Écrire le moteur d’échecs lui-même ressemble à ce qu’on ferait dans un langage classique, mais le point clé est le traitement parallèle de plusieurs états
• La génération des déplacements de pion suit ce flux
  • trouver toutes les positions des pions blancs
  • créer un état parallèle pour chaque pion
  • suspendre l’état principal d’origine et activer les états propres à chaque pion
  • vérifier simultanément, dans tous les états de pion, les candidats pour avancer d’une case, de deux cases et pour les prises en diagonale
  • refusionner ensuite les listes de coups candidats de chaque état
• L’exemple présenté manipule directement une chaîne FEN, mais l’implémentation réelle développe l’échiquier en 64 variables, une par case, pour lire et écrire l’état
• Les pièces glissantes comme le fou, la tour et la dame, ainsi que le roque et la prise en passant, sont aussi implémentés séparément
• Les détails se trouvent dans chess_engine.py

Traitement d’un tour et validation des coups

• Un tour consiste à lire le coup saisi par l’humain, vérifier qu’il est légal, puis générer le coup de réponse de l’ordinateur
• from_pretty_utf8_to_fen() convertit l’affichage Unicode de l’échiquier en notation FEN et extrait les cases de départ et d’arrivée de l’entrée
• La légalité du coup humain n’est pas vérifiée par un code de règles séparé, mais en générant tous les échiquiers légaux suivants puis en les comparant
  • make_move construit l’échiquier résultant du coup saisi
  • compute_legal_boards génère tous les échiquiers légaux possibles depuis la position actuelle
  • fork_on_list sépare chaque échiquier en un état parallèle distinct
  • les états différents du résultat obtenu après application du coup saisi sont supprimés avec destroy_active_thread()
• S’il n’existe aucun coup légal, toute la sortie est remplacée par le texte codé en dur "Illegal Move"
• Pour la réponse de l’ordinateur, le moteur génère les échiquiers de réponse possibles pour les Noirs ainsi que leurs scores, puis ne conserve qu’un seul échiquier avec keep_best_scoring_board(score)

Minimax 2-ply et simplification volontaire

• compute_and_score_legal_boards joue le rôle central dans la recherche minimax de profondeur 2
• Le moteur génère d’abord les coups candidats de l’ordinateur, puis les réponses possibles de l’adversaire, afin de vérifier si le roi peut être capturé
• Comme la validation de l’état d’échec impose de générer aussi les réponses adverses, la structure d’une recherche profondeur 2 est déjà en place
• Chaque position candidate est évaluée selon le score qu’elle obtient face à la meilleure réponse de l’adversaire
• Ce n’est toutefois pas un minimax profondeur 2 complet
  • le moteur ne vérifie pas si un coup de réponse adverse est illégal parce qu’il laisse son propre roi en échec
  • pour le traiter complètement, il faudrait une recherche profondeur 3, avec un coût bien plus élevé
• Les réponses générées par l’ordinateur ne sont pas elles-mêmes illégales, mais dans certains cas il peut prendre en compte des coups que l’adversaire ne pourrait pas réellement jouer et choisir ainsi une réponse plus faible qu’en pratique

Optimisations de performance

• L’implémentation initiale demandait environ 30 minutes pour générer une réponse à un coup humain
• La version finale descend à environ 1 à 10 secondes selon la position, sur la machine de l’auteur
• Ce gain d’environ 100× vient de plusieurs optimisations

• Suppression des variables intermédiaires

  • la lecture d’une variable doit retrouver sa valeur dans toute la chaîne d’état, ce qui a un coût en O(n)
  • lors du fork d’un état d’exécution, les variables sont aussi copiées, ce qui augmente l’usage mémoire
  • supprimer agressivement les variables devenues inutiles et réutiliser leurs noms permet de réduire temps et mémoire
  • l’état interne nécessaire à l’évaluation d’un coup est passé d’environ 10 Go à 300 Mo après optimisation

• Optimisation du matching des expressions régulières

  • dans les expressions régulières de nettoyage des instructions conditionnelles, le simple fait d’inclure le saut de ligne placé avant le motif double à peu près l’efficacité de cette instruction
  • comme les chaînes True et False apparaissent très souvent dans l’état, il faut restreindre les motifs pour retrouver rapidement uniquement la valeur au sommet de la pile
  • de petites différences de motif qui réduisent les correspondances candidates inutiles influencent le temps d’exécution total

• Commandes spécialisées et parallélisation

  • les portions lentes, comme les boucles qui cherchent la position des pièces, sont fusionnées en une commande spécialisée à base d’expression régulière au lieu d’être composées à partir d’instructions existantes
  • pour générer les déplacements de la tour, le moteur ne vérifie pas chaque direction séquentiellement, mais crée plusieurs états parallèles pour les traiter d’un coup
  • l’évaluation des positions se fait elle aussi en créant des états parallèles pour chaque échiquier candidat
  • l’exécution parallèle est particulièrement efficace pour les tâches où la même opération se répète sur de nombreux états, comme le calcul de la valeur des pièces

Autres éléments présents dans le code source

• Le code contient aussi des éléments d’implémentation que l’article ne détaille pas en profondeur
  • génération parallèle des coups pour les pièces glissantes comme le fou, la tour et la dame
  • procédure « cette case est-elle attaquée ? » pour le roque
  • conversion entre un échiquier FEN et la représentation par variables de cases
  • détection des droits au roque en suivant la position du roi et des tours
  • détection et suivi de la prise en passant
  • environ 2000 lignes de tests pour vérifier la justesse du moteur sur plusieurs milliers de parties
• Le texte se conclut en expliquant que ce type de projet sans objectif pratique précis a permis à l’auteur d’apprendre divers sujets d’informatique en dehors de son domaine habituel
• Parmi les projets liés également mentionnés figurent printf-tac-toe, qui joue au morpion avec le printf de C, et un clone de Doom en JavaScript de 13 kB

[GN⁺]

Avis de Hacker News

• C’est le travail de la même personne qui a montré que printf() est Turing-complet et créé un jeu de tir à la première personne en 13 kB de JavaScript
  https://github.com/HexHive/printbf
  https://github.com/carlini/js13k2019-yet-another-doom-clone

  • En lisant la phrase « montré que printf() est Turing-complet, et un jeu de tir à la première personne… », honnêtement je m’attendais à ce qu’elle se termine en disant que le jeu de tir avait lui aussi été implémenté avec printf
  • Le journal de développement de Doom est intéressant parce qu’il regorge de détails : https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
    Le délai pour terminer le concours était d’un mois, mais il semble qu’il ait pu réutiliser du code existant
    Le travail en lui-même devait être assez amusant, et je suis un peu triste de me dire qu’aujourd’hui, avec la famille et le travail, je ne pourrais jamais dégager un mois entier de temps libre pour ce genre de chose
  • Je m’attendais à quelque chose en lisant « un jeu de tir à la première personne en 13 kB de JavaScript », mais j’ai été un peu déçu en apprenant que le rendu graphique utilisait WebGL

• C’est à ce moment-là que j’ai eu l’impression que ce travail passait de délire amusant à quelque chose de totalement hors norme. Le calcul des nombreuses positions possibles se fait entièrement en parallèle, en faisant tourner des expressions régulières sur un ensemble croissant d’états et de variables, autrement dit sur des threads
  « Voici maintenant ma partie préférée du langage que nous avons créé. Grâce à la magie des expressions régulières, et au fait que nous effectuons une substitution globale sur toute la chaîne, nous pouvons exécuter plusieurs threads simultanément ! »
  La conclusion était très bonne aussi. « Qu’attendez-vous comme conclusion pour ce genre de billet de blog ? Il n’y en a pas vraiment. J’aimerais simplement que davantage de gens fassent ce genre de choses complètement inutiles. C’est vraiment amusant, personne ne se soucie du temps qu’il faut pour terminer, personne ne se soucie de savoir si ça marche ou non, et en bonus vous finissez par apprendre plus que vous ne l’auriez voulu sur plusieurs domaines de l’informatique en dehors du vôtre. »
  C’est vraiment un superbe état d’esprit

  • Quand on met de côté toutes les autres inquiétudes, je me demande si moi aussi je pourrais réussir quelque chose comme ça
    Ce qu’on en retire, c’est la puissance de ne pas savoir jusqu’où on peut aller en s’asseyant et en se concentrant sur une seule chose, tout en sachant que l’auteur est clairement une personne très talentueuse, expérimentée et créative

• Il semble y avoir un bug quelque part. La partie ci-dessous se termine par « Illegal move, you lose », alors qu’il ne s’agit pas d’un coup illégal

  1. e2e4, e7e5
  2. d2d4, e5d4
  3. d1d4, a7a5
  4. g1f3, b7b5
  5. b1c3, a5a4
  6. c3b5, a4a3
  7. b5a3, a8a3
  8. b2a3 -->
     Illegal Move
     You Lose.
     Game over.
     FEN de cette partie :
     1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
  • Même si l’on joue a2a3 au premier coup, ou a2a3 au deuxième coup après e2e4, c’est indiqué comme un coup illégal
    Mais les deux sont des coups légaux, donc c’est bien un bug
  • Il suffit aussi de jouer a2a4 au premier coup pour que la même chose se produise

• Je n’ai pas peur de quelqu’un qui joue aux échecs avec 84 688 expressions régulières, mais j’ai peur de quelqu’un qui joue aux échecs avec une seule expression régulière

  • S’il existe une heuristique générale pour linéariser des expressions régulières appliquées séquentiellement, c’est-à-dire une méthode pour fusionner deux expressions régulières arbitraires en une seule, on pourrait sans doute l’appliquer ici
    Au secours, je suis en train de me faire nerd-sniper
    Le problème potentiel qui me vient immédiatement à l’esprit, ce sont les références arrière
    L’expression régulière deviendrait très longue, mais en pratique elle encoderait un moteur d’échecs…

• Quand je vois ce genre de chose, j’ai envie de tirer mon chapeau et d’adresser des remerciements solennels aux véritables héros de l’humanité

• Le bug de déplacement sur la colonne a a été corrigé : https://github.com/carlini/regex-chess/issues/1

• Exemple précédent : des échecs écrits en sed https://news.ycombinator.com/item?id=6261314
  Bien sûr, la version sed utilise les commandes de flux de contrôle de sed et ne cherche probablement qu’un coup à l’avance, donc elle est assez différente de cette version sur ce point

• Ce n’est pas seulement un moteur d’échecs : c’est aussi un ordinateur et un langage assembleur construits uniquement avec des expressions régulières

• D’habitude, on ne perd pas aussi vite en commençant par a2a4 !

  • J’ai aussi rencontré un bug similaire sur la colonne a. Le parcours était e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

• Ceci vaut aussi la comparaison : https://codegolf.stackexchange.com/q/3503/32575

  • Toutes les règles de test de divisibilité sont nécessairement des langages réguliers, donc ce n’est pas si surprenant. Si c’était plus complexe, ce ne serait plus une « règle » exécutable par un humain