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é à 2 (+1/-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.
[^] # Re: heuristique du milieu
Posté par rewind (Mastodon) . Évalué à 5 (+2/-0).
J'avais vu une technique que je trouvais intéressante pour un jeu de Tetris (où l'ordinateur doit dire comment il place la pièce qui descend). L'idée est d'avoir un ensemble de métriques puis d'en faire une somme pondérée. Pour trouver les bonnes pondérations, il y avait une procédure itérative qui tirait des pondérations au hasard, regardait celles qui marchaient correctement et qui restreignait le hasard à la bonne zone au fur et à mesure. C'est de l'auto-apprentissage mais pas par réseau neuronal, plutôt à l'ancienne. À la fin, on voyait ce qui avait du poids dans la décision. Pour les échecs, c'est assez facile de trouver plein de métriques relatives à une position du jeu et donc, ça pourrait assez bien marcher.
[^] # Re: heuristique du milieu
Posté par Nicolas Boulay (site web personnel) . Évalué à 3 (+1/-1).
Une somme pondérée avec un poid trouvé par apprentissage, cela ressemble beaucoup a un neurone.
"La première sécurité est la liberté"
# Déplacements
Posté par Colin Pitrat (site web personnel) . Évalué à 5 (+3/-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 !
[^] # Re: Déplacements
Posté par remico . Évalué à 3 (+2/-0).
Sans repartir de zéro ou pour trouver quelques inspirations il y a pas mal de sources sur le net, beaucoup de moteurs de jeu sont open source.
Il y a quelques exemples de code de jeu d'échecs réduit au maximum sur nanochess.org. Il y a divers langages assembleur, C, Javascript et java.https://nanochess.org/chess.html Il y a aussi dans les links des liens vers d'autres moteurs et ressources sur la programmation de jeu d'échecs, dont le site de µMax ou Fairy-Max avec quelques explications de codage qui est bien suffisant pour battre beaucoup d'humains https://home.hccnet.nl/h.g.muller/max-src2.html
Je joue quelquefois avec celui de nanochess, Toledo javascript celui en javascript et les pièces en GIF dans le navigateur, je n'ai pas remarqué de bugs et il n'est pas si facile à battre. Fairy-max est pas mal non plus.
Pour ce qui est du niveau à atteindre pour qu'il soit plus fort que n'importe quel humain c'est avec le classement elo. Un joueur expérimenté normal fait 1600 elo, Toledo javascript chess fait 12-1400 elo et Fairy Max fait 1900 elo. J'ai été vérifier l'info, du plus fort niveau atteint par un humain ayant jamais joué aux échecs et ce serait Magnus Carlsen avec 2882 elo et pour comparaison le meilleur moteur serait stockfish 19 avec 3650 Elo.
Pour évaluer un moteur il faut le faire jouer avec un ou plusieurs autres dont le niveau est connu avec le logiciel arena par exemple et plus il y a de parties plus le résultat s'affinera. Quelques paramètres peuvent faire changer le score, puissance de la machine hôte et temps de partie.
# Roque et FRC
Posté par Strash . Évalué à 4 (+2/-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 ?
[^] # Re: Roque et FRC
Posté par n_e . Évalué à 1 (+0/-0).
Oui et non. Non parce que à titre personnel je n'y ai jamais joué et ça ne m'intéresse pas (je trouve déjà les échecs normaux suffisamment difficiles). Oui, au sens que j'y ai pensé et que si je change d'avis ça ne sera pas trop compliqué à changer (du moins pour la partie règles).
# Répertoire d'ouvertures ?
Posté par rewind (Mastodon) . Évalué à 4 (+1/-0).
Est-ce que tu envisages à termes d'avoir un répertoire d'ouverture pour le début de jeu ? Ou alors tu penses que ton moteur sera suffisamment fort pour retrouver les bonnes suites de coups ?
[^] # Re: Répertoire d'ouvertures ?
Posté par n_e . Évalué à 2 (+1/-0).
Je compte qu'il devienne suffisamment fort suffisamment tôt pour ne pas avoir besoin de répertoire d'ouvertures. En plus je trouve intéressant de le laisser lui-même trouver les ouvertures et voir ce qu'il découvre.
Aussi, les compétitions d'ordinateurs ont des ouvertures imposées (parce que les ordis les plus forts font toujours nulle en partant de la position initiale - on fait donc des matchs aller-retour à partir d'une position imposée).
[^] # Re: Répertoire d'ouvertures ?
Posté par rewind (Mastodon) . Évalué à 3 (+0/-0).
Rien à voir mais tu n'as pas mis de licence sur ton dépôt. Et puis tes journaux m'ont donné envie de m'y mettre aussi, en C++ mais je m'inspire grandement de ton code (je n'ai pas pris la même représentation pour le plateau cela dit). Donc j'aimerais bien connaître la licence de base !
[^] # Re: Répertoire d'ouvertures ?
Posté par n_e . Évalué à 3 (+2/-0).
J'ai ajouté une licence (GPLv3)
[^] # Re: Répertoire d'ouvertures ?
Posté par rewind (Mastodon) . Évalué à 3 (+0/-0). Dernière modification le 12 octobre 2026 à 16:05.
Merci ! Ça tombe rudement bien, c'était mon choix préféré également !
# Intéressé pour l'affronter
Posté par woprandi . Évalué à 2 (+2/-0).
Une fois qu'il sera prêt je suis disposé à jouer contre lui si tu veux un adversaire correct
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.