Moteur d’échecs mini-max implémenté avec des expressions régulières
(nicholas.carlini.com)Moteur d'échecs mini-max à deux niveaux
-
Échecs et expressions régulières : L’auteur a créé un programme jouant aux échecs en n’utilisant que des expressions régulières. Ce programme prend un échiquier en entrée et est composé de 84 688 expressions régulières permettant de jouer des coups valides.
-
Conception d’un CPU à base d’expressions régulières : L’auteur conçoit un mécanisme d’exécution sans branchement et un jeu d’instructions SIMD (Single Instruction, Multiple Data) avec des expressions régulières. Cela permet d’écrire un programme capable de jouer aux échecs.
-
Structure de données : L’état actuel de l’ordinateur est représenté par une chaîne unique contenant la « pile » du programme et toutes les variables. Chaque instruction manipule les variables de la pile ou effectue des lectures/écritures sur une variable donnée.
-
Opérations de pile de base :
- Instruction push : ajoute une valeur au sommet de la pile.
- Instruction pop : supprime l’élément du sommet de la pile.
-
Instruction variable <-> pile :
- Lecture de variable : charge le contenu d’une variable au sommet de la pile.
- Affectation de variable : assigne une valeur à une variable, en la mettant à jour si elle existe déjà ou en créant une nouvelle.
-
Conditions : Les structures conditionnelles pilotent le flux du programme. Selon la condition, elles activent ou désactivent certaines parties du programme.
-
Impossibilité des boucles : Les expressions régulières seules ne permettent pas d’implémenter de boucles, donc tous les calculs répétés doivent être déroulés au préalable.
-
Exécution multi-threadée : Grâce à la substitution globale des expressions régulières, il est possible d’exécuter plusieurs threads en parallèle.
-
Écriture du moteur d’échecs : Le moteur d’échecs est écrit de manière similaire à d’autres langages de programmation et fonctionne rapidement grâce au traitement parallèle.
-
Déroulement des tours :
- Lecture du coup du joueur : lit le coup saisi puis vérifie sa validité.
- Génération de la réponse de l’ordinateur : génère toutes les réponses possibles et choisit le meilleur coup.
-
Recherche mini-max : un mini-max à profondeur 2 permet de choisir le meilleur coup. Ce processus est réalisé de manière efficace grâce au traitement parallèle.
Ce projet montre une implémentation du moteur d’échecs via une utilisation originale des expressions régulières, mettant en évidence leur puissance ainsi qu’une conception d’ordinateur créative.
1 commentaires
Commentaires de Hacker News
Ce développeur est celui qui a prouvé que
printf()est turing-complet et qui a écrit un jeu de tir à la première personne en JavaScript de 13kB.printf()Ce projet montre qu'il est remarquable de calculer en parallèle plusieurs positions possibles.
Je n'ai rien de particulier à ajouter à la conclusion de l'article de blog, mais j'aimerais que davantage de gens essaient ce type de projet "inutile".
Dans le jeu d'échecs, un bug « coup illégal, défaite » est apparu.
Je crains davantage quelqu'un qui joue aux échecs avec une seule expression régulière qu'une personne qui en utilise 84 688.
Je voudrais rendre hommage à ce type de projet.
Le bug lié au déplacement de la colonne a a été corrigé.
Ce projet n'est pas seulement un moteur d'échecs, mais aussi un ordinateur et un langage assembleur construits uniquement avec des expressions régulières.
Il y avait déjà eu un projet d'échecs écrit en
sed.sedutilisait des instructions de contrôle de flux et ne recherchait que 1 ply.Lorsqu'on commence par
a2a4, on ne se retrouve pas en échec si vite.Essayer quelque chose sans objectif clairement « productif » peut conduire à découvrir de nouvelles approches et à favoriser l'innovation.
Je suis en train d'essayer d'innover et d'être productif