- Un moteur d’échecs léger fonctionnant dans environ 2 KB, capable de jouer une partie complète dans un ensemble de règles limité
- Il intègre des algorithmes clés comme un plateau mailbox de 120 cases, la recherche Negamax et l’élagage alpha-bêta
- Il utilise une évaluation basée uniquement sur la valeur des pièces (material-only eval) et un ordre des coups privilégiant les captures (move ordering)
- Le roque, la prise en passant, la promotion, la répétition et la règle des 50 coups sont non implémentés
- Il atteint un niveau d’environ 1170 à 1200 Elo et se distingue comme un exemple de moteur d’échecs implémenté en moins de 2 KB de code
Aperçu du projet
- Sameshi est un moteur d’échecs minimaliste prenant en charge un ensemble de règles limité, dont la taille totale du code n’est que d’environ 1,95 KB
- Le fichier principal est
sameshi.h, et une version plus lisible est incluse dans readable/sameshi.h
- Le dépôt GitHub fournit également
main.c, Makefile, .gitignore, etc.
- Une vidéo de démonstration est disponible sur YouTube, ce qui permet de voir le moteur en fonctionnement réel
Structure principale (core)
- Le moteur se compose des six éléments principaux suivants
- Structure de plateau mailbox de 120 cases
- Algorithme de recherche Negamax
- Élagage alpha-bêta
- Évaluation basée uniquement sur la valeur des pièces (material-only evaluation)
- Ordre des coups privilégiant les captures (move ordering)
- Validation complète des coups légaux, incluant échec, mat et pat
- Les fonctionnalités non implémentées indiquées explicitement sont le roque, la prise en passant, la promotion, la répétition et la règle des 50 coups
Performances (strength)
- Son niveau est estimé à environ 1170 Elo, avec un intervalle de confiance à 95 % de 1110 à 1225 Elo
- La mesure est basée sur les résultats de 240 parties contre Stockfish (niveau 1320 à 1600)
- Les tests ont été réalisés avec une profondeur fixe de 5, un maximum de 60 demi-coups et des règles limitées
Caractéristiques techniques
- La taille totale du code est inférieure à 2 KB, avec 98,6 % en C et 1,4 % en Makefile
- Le projet pousse au maximum la compacité et l’efficacité algorithmique pour implémenter la logique des échecs avec un minimum de code
- Il est classé dans les thèmes chess-engine, chess et demoscene
État du dépôt
- Le dépôt GitHub compte 143 étoiles et 5 forks
- Les sections Issues, Pull requests, Projects et Security sont toutes vides
- La description du dépôt est résumée ainsi : « a ~1200 Elo chess engine that fits within 2KB »
1 commentaires
Avis sur Hacker News
Projet vraiment sympa. C’est bien qu’il y ait la gestion du pat, mais je me demande combien d’espace il faudrait pour implémenter toutes les règles.
Comme l’auteur le mentionne, s’il manque le roque, la prise en passant, la promotion, la répétition et la règle des 50 coups, j’ai du mal à appeler ça des échecs modernes.
Pour un petit moteur, on peut peut-être laisser de côté la répétition et la règle des 50 coups, mais le roque, la prise en passant et la promotion me semblent indispensables.
En 1980, Video Chess prenait en charge l’ensemble des règles dans 4KB.
Du coup, je me demande quel est aujourd’hui le plus petit moteur compatible UCI. Faire un moteur ultra-compact avec règles complètes qui le surpasserait serait un objectif amusant.
Pour référence, le Fidelity CC3 que j’utilisais au début des années 1980 gérait aussi le roque et la prise en passant.
La version JavaScript de 2KB inclut le roque, la prise en passant, la promotion, la recherche et même une GUI.
La version assembleur de 326 octets n’inclut pas les règles spéciales.
Il n’existe pas de version compatible UCI, mais cela semble plus simple à implémenter qu’une GUI. Certains forks de la version JS ont peut-être ajouté cette fonctionnalité.
Beau projet. En réutilisant le frontend de GNU Chess, on pourrait peut-être réduire le nombre de lignes de code et n’implémenter que le backend.
Côté bug report, j’ai repéré un problème : un pion ne devrait pas pouvoir avancer de deux cases après avoir déjà avancé d’une case, pourtant
b6b4est autorisé.L’outil le plus couramment utilisé par les développeurs de moteurs d’échecs pour estimer l’ELO est cutechess. En interne, il utilise SPRT.
Il existe aussi Ordo, mais je ne l’ai pas utilisé moi-même.
Je me demande s’il est possible d’atteindre 1 ELO par octet. On peut sans doute faire plus petit, mais au prix d’un moteur moins intelligent.
Ça ressemble davantage à un programme qui permet de déplacer des pièces d’échecs qu’à un vrai jeu d’échecs, puisqu’il manque le roque, la prise en passant, la promotion, la répétition et la règle des 50 coups.
On voit parfois des gens dire qu’ils ont implémenté les échecs dans un espace minuscule, alors qu’en réalité ils omettent souvent des règles importantes.
Si vous cherchez de vrais moteurs petits mais puissants, je recommande asmFish en assembleur x86 (environ 130KiB), OliThink avec ses quelque 1000 lignes, ainsi que Xiphos, qui obtient de très bonnes performances avec du code C simple.
Il y a aussi eu des moteurs de 4KB dans le TCEC, mais je pense que leurs affirmations méritent un astérisque (*).
Toledo est une famille de programmes d’échecs petits mais assez puissants.
J’ai moi aussi récemment implémenté un moteur d’échecs avec toutes les règles en environ 400 lignes de code lisible.
Je l’ai d’abord écrit en Java, puis je l’ai porté vers mon propre langage, Bau.
Il inclut même une interface terminal, et l’ELO est encore en cours de mesure, mais je n’ai pas réussi à le battre.
L’implémentation du roque a été particulièrement délicate, mais le défi en lui-même était très plaisant.
Voir le code des échecs en langage Bau.
Je me demande comment les parties où Stockfish voulait roquer ont été gérées. Comme le roque est un coup très fréquent, j’ai l’impression qu’il est difficile d’évaluer la force du moteur sans cette fonctionnalité.
Ainsi, toutes les parties se sont jouées dans la même « variante d’échecs sans roque ».
Cette évaluation ne portait donc pas sur l’ensemble des échecs, mais sur cette variante restreinte.
Vraiment génial ! J’ai ajouté ce projet à HN Arcade.
Lien HN Arcade