Sommaire
Bonjour tout le monde,
Pour celles et ceux qui n'ont pas lu mon précédent journal, j'écris un moteur d'échecs à partir de zéro, en l'améliorant progressivement, et avec l'objectif de le rendre plus fort que n'importe quel humain.
Depuis le dernier journal, j'ai commencé à coder, et il a désormais les fonctionnalités suivantes :
- Génération des coups pseudo-légaux et vérification des échecs1 (le principe de base d'un moteur classique est de générer tous les coups légaux, puis de les évaluer)
- Interface au protocole UCI, pour l'interopérabilité avec les outils externes (notamment avec cutechess-cli qui permet de jouer des matchs entre moteurs et d'évaluer leur niveau)
- Recherche negamax basique, sans aucune optimisation
- Fonction d'évaluation qui identifie les mats, les pats, et donne la somme du matériel
J'ai également écrit quelques scripts permettant de tester le générateur de coups, et de faire jouer un match entre la version actuelle et une version précédente.
Le code source est disponible ici. Vous verrez que le code est très moche, cela dit il est modularisé, et si vous regardez par exemple engine.rs, il devrait être relativement court et compréhensible.
Les résultats
Le premier résultat, c'est que le moteur respecte toutes les règles des échecs2. Cela peut paraître trivial, mais en fait ce n'est pas si simple et il y a pas mal de bugs possibles :
- Les 6 types de pièces se déplacent différemment
- Les pions capturent différemment qu'ils se déplacent
- La prise en passant dépend de l'état précédent (on ne peut prendre en passant qu'immédiatement après le déplacement du pion adverse)
- Les règles du roque sont relativement compliquées (le roi ne doit pas traverser une case en échec, les cases entre le roi et la tour doivent être libres, le roi et la tour ad hoc ne doivent pas avoir bougé)
Pour ma part je joue suffisamment bien aux échecs pour ne jamais faire de coup illégal, pourtant j'ai eu du mal à bien me remettre en tête les règles. En particulier j'ai eu pas mal de bugs sur le roque :
- Le moteur ne roquait pas si la tour avait bougé, par contre il roquait si la tour avait été capturée
- le moteur vérifiait bien que la case "sautée" par le roi n'était pas en échec, mais ne vérifiait pas que le roi n'était pas en échec sur sa case initiale
- lors du grand roque, il faut vérifier que 3 cases sont vides, alors que coté petit roque ce n'est que deux.
Coté performances, la version actuelle bat ou fait nulle systématiquement contre la version précédente (qui recherche les mats mais, à défaut d'en trouver, joue des coups aléatoires). Elle gagne beaucoup de matériel, mais a beaucoup de mal à progresser dans des situations dites calmes.
Un autre point intéressant (mais pas surprenant), c'est qu'à ce stade aucune notion de stratégie n'émerge. En particulier le moteur ne sait pas développer ses pièces, et ne sait pas amener des pièces supplémentaires à l'attaque.
Ci-dessus, le moteur joue les blancs et a vu le mat en 2 (Dxb8 Fc7 Dxc7#).
Ci-dessus, le moteur joue les blancs et a un avantage matériel écrasant, mais ne sait pas comment progresser. C'est quasiment toujours dans ce type de situation qu'il n'arrive pas à gagner et finit par faire nulle par répétition.
Les parties complètes sont sur cette étude lichess.
Prochaines étapes
La prochaine étape (que je devais initialement faire avant ce journal), c'est d'ajouter la gestion de la pendule et l'approfondissement itératif. Aujourd'hui, le moteur joue avec une profondeur fixe de 4, et on voit deux problèmes, qui, mis bout à bout, amélioreraient beaucoup les performances :
- En fin de partie, le moteur ne va souvent pas à une profondeur suffisante pour trouver les mats
- L'utilisation de temps est très variable en fonction de la position (logique vu qu'elle dépend du nombre de coups à profondeur 4), et le moteur n'utilise quasi aucun temps en fin de partie quand il y a moins de coups légaux
L'optimisation suivante sera sans doute d'ajouter l'élagage alpha-beta (qui consiste à ne pas explorer des branches si un meilleur coup imparable a été déjà trouvé) et un tri des coups basique (pour explorer autant que possible les meilleurs coups en premier et donc avoir un élagage efficace).
Enfin je voudrais déployer le moteur en tant que bot lichess pour que vous puissiez jouer contre lui.
Apparté - SPRT
On m'a demandé dans le journal précédent comment vérifier si une modification du moteur améliore les performances. Pour cela on fait jouer la nouvelle version contre la version précédente jusqu'à ce que le nombre de matchs soit suffisant pour conclure s'il y a une amélioration ou pas. C'est fait avec ce script.
La ligne importante est celle-ci :
-sprt elo0=0 elo1=100 alpha=0.05 beta=0.05
Cela signifie qu'on fait un test SPRT, qui est un test séquentiel (on répète une expérience jusqu'à ce que le test soit concluant).
Le test permet de comparer 2 hypothèses : H0 (avec elo0 - l'ancienne version et la nouvelle version ont le même classement elo, ie. le même niveau) et H1 (avec elo1 - la nouvelle version est plus forte de 100 elo), et alpha et beta le taux de faux positifs et faux négatifs.
Ensuite on exécute le programme et ça nous donne ça :
Score of correcthorse-b0bc211-dirty vs correcthorse-194dc7c: 7 - 0 - 2 [0.889] 9
... correcthorse-b0bc211-dirty playing White: 4 - 0 - 0 [1.000] 4
... correcthorse-b0bc211-dirty playing Black: 3 - 0 - 2 [0.800] 5
... White vs Black: 4 - 3 - 2 [0.556] 9
Elo difference: 361.2 +/- nan, LOS: 99.6 %, DrawRatio: 22.2 %
SPRT: llr 3.12 (106.0%), lbound -2.94, ubound 2.94 - H1 was accepted
Player: correcthorse-b0bc211-dirty
"Draw by 3-fold repetition": 2
"No result": 3
"Win: Black mates": 3
"Win: White mates": 4
Player: correcthorse-194dc7c
"Draw by 3-fold repetition": 2
"Loss: Black mates": 3
"Loss: White mates": 4
"No result": 3
Finished match
La partie la plus importante est la phrase H1 was accepted : l'hypothèse que la nouvelle version est plus forte de 100 elo a été acceptée.
A noter que 9 parties ont été jouées : le test s'est arrêté dès que le résultat a été obtenu, sans jouer le maximum de parties paramétré (100).
-
Les coups pseudo-légaux sont les coups qui respectent les règles, à l'exception de la vérification que le coup ne laisse pas le roi en échec à la fin du tour. La vérification des échecs est relativement lente, donc, sur un moteur optimisé, on ne la fait que sur les coups qu'on choisit d'analyser par la suite. ↩
-
La seul "règle" qu'il ne connaît pas est la nulle par 3 répétitions, mais ça n'a un impact que sur les performances (il répète parfois 3x alors qu'il est gagnant), pas la légalité des coups joués. ↩
# heuristique du milieu
Posté par Nicolas Boulay (site web personnel) . Évalué à 3 (+0/-0).
Je te propose une petite heuristique pour le milieu de partie : jouer pour augmenter les possibilités de jeu (décoincer une pièce, etc..). Il y a longtemps j'avais fait un top4, l'heuristique : "j'ai 5 victoires possibles avec 1 pièces (et 3 cases vides), 2 avec 2, 1 avec 3". Le jeu avait tendance à enfermer le joueur. C'était impressionnant.
Pour les échecs, j'imagine que c'est de sommer les degrés de liberté de chaque pièce. Logiquement, il devrait tenter de contrôler le centre.
"La première sécurité est la liberté"
[^] # Re: heuristique du milieu
Posté par fork_bomb . Évalué à 1 (+0/-0).
Oui, ça a l'air d'être une très bonne heuristique, le principal inconvénient c'est que si c'est implémenté de façon naïve (on appelle le générateur de coups et on compte les coups), ça va être lent, et généralement l'amélioration de la fonction d'évaluation ne compense pas la baisse du nombre de positions explorées.
Pour mon moteur, je n'ai pas encore décidé comment améliorer la fonction d'évaluation. Une option qui me tente bien, c'est de partir directement sur un réseau neuronal et de le faire progresser par auto-apprentissage.
# Déplacements
Posté par Colin Pitrat (site web personnel) . Évalué à 3 (+1/-0). Dernière modification le 05 octobre 2026 à 15:06.
Il y a quelques temps (plusieurs année en fait) j'avais codé un moteur d'échec juste pour le fun (enfin, dans le but d'essayer divers algorithmes d'apprentissage par renforcement dessus). J'avais commencé naïvement, en me basant sur ce que je connaissais des règles (je pensais les connaître complètement en fait, même si en pratique je n'avais quasiment jamais joué).
Mon approche avait donc été de dire que pour chaque pièce, j'avais un ensemble de vecteurs déplacement possible, avec potentiellement une limite sur la distance:
En pratique on peut se contenter de la moitié des directions et utiliser limite=[1,1] pour les pions, limite=[-1,1] pour les cavaliers et le roi et limite=[-8,8] pour les autres.
J'étais assez content de moi, c'était propre, mis à part l'exception pour les pions au premier coup. J'ai ajouté le support de la promotion (un pion qui arrive au bout de l'échiquier devient une dame). Il ne me manquait plus que le roque, mais je ne me souvenais plus des détails. Je vais donc vérifier les regles sûr wikipédia et là je decouvre:
Et les choses liées à la fin de partie (et non aux mouvements) mais qui compliquent pas mal la logique
Et mon beau code est rapidement devenu un peu plus bordelique !
Tout ça pour dire, coder un jeu d'échecs, c'est fun et loin d'être aussi trivial qu'on pourrait le penser si on connaît mal les règles !
# Roque et FRC
Posté par Strash . Évalué à 2 (+0/-0). Dernière modification le 05 octobre 2026 à 15:23.
Envisages-tu que ton moteur soit capable de jouer des parties FRC (ou Chess960) voire même DFRC (ou FRD) ? Pour cela la règle du Roque est plus généralisée (notamment la règle qui ajoute qu'on ne peut roquer qu'une fois par partie). Il serait peut être intéressant de regarder ça pour coder la partie du roque ?
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.