Journal Ecrire un moteur d'échecs surhumain - Partie 1

Posté par  .
Étiquettes :
16
27
sept.
2026

Sommaire

Bonjour Nal,

Je me suis dit qu'il serait intéressant d'écrire un moteur d'échecs capable de battre n'importe quel humain. Pourquoi ?

  • le résultat est impressionnant
  • c'est difficile mais réalisable
  • et surtout, c'est instructif

A ce stade, je n'ai pas commencé à coder le moteur cible (mais j'ai codé un prototype). Je vais vous parler de mes choix et vous donner un peu de contexte sur les moteurs d'échecs.

Les types de moteurs d'échecs

Aujourd'hui il existe deux types de moteur d'échecs : les moteurs "classiques", dont le plus connu et le plus performant est Stockfish, et les moteurs dans la lignée d'AlphaZero, qui est connu pour avoir atteint un niveau surhumain par auto-apprentissage (en jouant contre soi-même), et qui est un descendant de AlphaGo, qui a été le premier logiciel de Go à battre les meilleurs joueurs mondiaux.

Dans les deux cas, le principe de base des moteurs est qu'on leur donne une position en entrée, et ils retournent le meilleur coup en sortie. Le fonctionnement réel est évidemment plus complexe, avec notamment les calculs réalisés pour les coups précédents d'une même partie réutilisés, la gestion du temps, etc.

Les moteurs classiques utilisent une recherche de type minimax, associée à une fonction d'évaluation qui donne un score à chaque position rencontrée au cours de la recherche.

Les moteurs de type AlphaZero utilisent une recherche MCTS (Monte Carlo Tree Search), qui explore par échantillonnage, en se basant sur les probabilités retournées par la fonction d'évaluation, qui est un réseau neuronal qui retourne la probabilité que chaque coup possible soit le meilleur.

Mon choix de moteur

Je vais partir sur un moteur classique. Simplement parce que c'est ce que je préfère, mais aussi parce que ça se prête également mieux à commencer par quelque chose de basique et l'améliorer au fur et à mesure.

A noter que les moteurs classiques ne sont pas anciens ou obsolètes : Stockfish est actuellement le moteur le plus puissant, il est possible d'utiliser des réseaux neuronaux ou de faire de l'auto-apprentissage.

Mes choix techniques

Je vais écrire le moteur en Rust. Initialement, je voulais l'écrire en JavaScript sur Node.js car c'est le langage que j'utilise le plus, et j'aime bien montrer qu'il est rapide. Cependant je ne vais pas partir sur Node.js pour plusieurs raisons :

  • Bien que ce soit possible d'obtenir un moteur final performant (Stockfish transpilé en JavaScript a des performances "correctes"), les premières versions naïves du moteur seront lentes, ce qui va être problématique pour faire des parties en cadences très rapides (qui sont nécessaires pour tester les améliorations du moteur)

  • La technique performante pour faire des opérations sur l'échiquier est d'utiliser des bitmaps de 64bits (on a de la chance, un échiquier fait 64 cases), et JavaScript ne gère presque pas les entiers de 64bits

  • L'optimiseur des dernières versions de V8 est très agressif, ce qui rend le profilage d'une fonction optimisée quasi-impossible (la fonction principale et celles qu'elle appelle sont optimisés en une seule grosse fonction, et on ne voit que ça dans les profils)

Quant à Rust vs C++ ou autre, ce n'est qu'une question de préférence.

L'optimisation et la détection de bugs d'un moteur d'échecs

Commençons par la détection de bugs : l'approche "comme pour un programme classique" ne marche pas, car sauf pour les bugs les plus grossiers, l'impact d'un bug va juste être une légère baisse de niveau. Par exemple, si la matrice indiquant les meilleures positions des pions est à l'envers, les pions seront parfois moins bien placés, mais pas forcément vu qu'une recherche plus profonde pourra trouver la bonne position car la bonne position a des avantages tactiques.

La détection de bugs se traite donc de la même façon que l'optimisation : on fait une modification, on regarde si la modification augmente le niveau de jeu, et si c'est le cas on la merge.

Les prochaines étapes

Les prochaines étapes sont la conséquence du paragraphe précédent : avant de faire quoi que ce soit de compliqué, il faut pouvoir évaluer l'effet d'une modification, ce qui concrètement se fait avec un outil comme cutechess-cli, qui parle au moteur avec le protocole UCI.

Les prochaines étapes seront donc le strict nécessaire pour obtenir un moteur qui joue des coups légaux et peut être utilisé avec cutechess-cli :

  • générateur de coups (à partir d'une position on génère tous les coups légaux)

  • recherche negamax basique

  • fonction d'évaluation basique (par exemple somme de la valeur des pièces)

  • approfondissement itératif basique et gestion de la pendule

  • protocole UCI

Ensuite on pourra commencer les optimisations, a priori les plus basiques et importantes sont :

  • ajouter des notions positionnelles basiques à la fonction d'évaluation (bon positionnement des pièces, etc.)

  • alpha-beta pruning (on ne calcule pas les branches qui sont forcément meilleures pour l'adversaire ou pires pour nous que celles déjà calculées)

  • classement des coups (on calcule d'abord les coups qu'on anticipe être les meillleurs, ce qui permet à l'algorithme alpha-beta de retirer un maximum de branche)

  • quiescence search (si on arrête la recherche au milieu d'un échange, alors qu'on a capturé une pièce mais on n'a pas été recapturés, l'évaluation va dire qu'on a une pièce de plus. L'algo. en question continue la recherche jusqu'à ce que la position soit stable)

  • # la suite

    Posté par  . Évalué à 5 (+3/-0).

    Après ce beau menu, on a hâte de lire la suite de l’aventure. Et du code !

  • # Stockfish est les deux

    Posté par  . Évalué à 5 (+3/-0).

    Stockfish est un peu hybride entre les deux, un mix entre calcul traditionnel et petit réseau de neurones

    • [^] # Re: Stockfish est les deux

      Posté par  . Évalué à 4 (+3/-0).

      Stockfish est un peu hybride entre les deux, un mix entre calcul traditionnel et petit réseau de neurones

      Les deux utilisent un réseau de neurones mais pas avec les mêmes objectifs.

      Stockfish l'utilise pour évaluer les positions et complète avec une variante de recherche minmax (negamax) pour trouver les meilleurs coups à jouer.

      Alpha Zero l'utilise pour trouver directement les bons coups intéressants à explorer et complète avec du Monte Carlo pour les sélectionner.

      • [^] # Re: Stockfish est les deux

        Posté par  . Évalué à 5 (+2/-0).

        L'état de l'art change vite, mais la clé de tout c'est bien l'évaluation des positions sans minimax qui donne un avantage à Stockfish. Le réseau de neurones permet à Stockfish d'évaluer les branches de l'arbre et de ne parcourir que celles qui sont prometteuses, donc justement de ne pas faire du minimax dans les branches pour les évaluer.

        Du point de vue algorithmique, c'est vrai que ça ressemble à un algo classique (qui évaluerait les position en comptant les pièces par exemple), mais quand tu comprends ce qu'il fait, tu te rends compte que le réseau permet de remplacer l'exploration des branches, donc justement de ne pas faire de minimax.

        Étrangement, il semble que le plus gros défi pour les programmes d'échecs n'est pas de battre les humains (ça c'est piece of cake), mais de proposer des adversaires intéressants. Même avec un réglage du niveau, les ordinateurs ne proposent pas du tout le même type d'opposition qu'un humain, et je pense que c'est à tous les niveaux. J'imagine qu'entrainer un modèle sur des bases de parties humaines pourrait permettre d'améliorer ça.

        • [^] # Re: Stockfish est les deux

          Posté par  (Mastodon) . Évalué à 4 (+1/-0).

          C'est plutôt le contraire qui est en train de se passer : les humains s'adaptent aux programmes d'échecs. Les programmes d'échecs ont beaucoup modifié la manière dont les joueurs s'entraînent, notamment parce qu'ils permettent d'explorer des ouvertures originales de manière simple (le programme donne la séquence des «meilleurs coups») ou qu'ils permettent de comprendre des situations complexes en milieu de jeu par analyse à posteriori. Plus besoin d'avoir un grand maître sous la main pour progresser, Stockfish suffit ! (bon, en vrai, ça reste difficile les échecs, même avec Stockfish sous la main).

          • [^] # Re: Stockfish est les deux

            Posté par  . Évalué à 3 (+1/-0).

            Plus besoin d'avoir un grand maître sous la main pour progresser, Stockfish suffit !

            Pas du tout, les dernières années n'ont pas apporté grand chose, hormis qu'il est encore plus fort. Ça donne le meilleur coup sans aucune explication. Parfois même il est tellement fort que même du point de vue grand maître c'est pas simple à comprendre

            • [^] # Re: Stockfish est les deux

              Posté par  . Évalué à 6 (+5/-0).

              Je n'ai effectivement pas en tête d'amélioration "utile" datant disons de ces cinq dernières années, par contre si on compare à il y a 20 ans c'est la révolution.

              Par exemple en ce moment je suis en train d'apprendre une nouvelle ouverture, et je le fais uniquement avec une base de parties et Stockfish. Il y a 20 ans j'aurais dû acheter un livre, qui n'aurait peut-être pas existé ou traité les lignes qui m'intéressent, et qui aurait été probablement faux.

              Quant aux explications des coups joués, effectivement c'est quelque chose qui n'existe pas vraiment (si ce n'est la fonctionnalité de chess.com qui a un gros manque de pertinence), mais il y a pas mal de techniques pour comprendre un coup de l'ordi :

              • faire passer le tour plusieurs fois à l'adversaire et regarder comment l'ordi progresse en l'absence de défense

              • jouer des coups logiques contre l'ordi et regarder comment il punit

              • jouer la même suite de coups après le coup de l'ordi et le coup qui nous semble logique, et comparer

              Il faut aussi ne pas hésiter à rejeter un coup de l'ordi s'il ne parait pas approprié (par ex. il propose souvent un mauvais coup positionnel mais qui marche grâce à des complications tactiques incompréhensibles, alors qu'un coup logique est OK)

              • [^] # Re: Stockfish est les deux

                Posté par  . Évalué à 2 (+0/-0). Dernière modification le 28 septembre 2026 à 13:11.

                Oui la logique atteint vite sa limite aux échecs. C'est très concret.
                Même a haut niveau, stockfish aide énormément pour les préparations d'ouverture mais parfois il y a des ratés. Des positions jugées bonne par stockfish sont en fait très difficile a jouer même par des grands maîtres et sont donc mauvaise en pratique

                • [^] # Re: Stockfish est les deux

                  Posté par  . Évalué à 6 (+3/-0).

                  En fait, le meilleur coup de l'ordinateur n'est pas forcément le meilleur coup pour un humain, parce que l'humain est faillible et qu'on ne peut exclure la possibilité de faire une erreur, surtout si la position est complexe et que la ligne qui permet le gain est longue et unique. Ça ne sert à rien de connaitre la meilleure ligne si on ne connait pas la réfutation des lignes secondaires.

                  Ceci dit, savoir qu'une ligne est bonne change quand même largement la donne : il suffit de "chercher" la solution. C'est très différent que de devoir évaluer si la ligne est mauvaise ou non, surtout si elle a l'air mauvaise.

                  Bizarrement, on aurait pu penser que l'utilisation massive des ordinateurs allait tuer les échecs, alors que c'est plutôt le contraire : on voit beaucoup de préparation sur des ouvertures nouvelles, dont le but n'est pas forcément de jouer la meilleure suite de coups, mais plutôt une suite pas trop mauvaise mais surtout inattendue. Ça n'aurait aucune chance de marcher contre un ordinateur, mais contre un humain, l'avantage est immédiat, puisque quand on jour une nouvelle ligne on joue contre un humain, et pas contre un ordi.

                • [^] # Re: Stockfish est les deux

                  Posté par  (site web personnel) . Évalué à 4 (+4/-0).

                  Et l'inverse est vrai aussi. J'ai mes meilleurs résultats en tournoi avec des variantes jugées mauvaise par la machine… Sûrement parce que, par conséquent elle sont peu étudiées par les humains… (Comme le gambit de l'aile dans la sicilienne 1. e4 c5 2. Cf3 Cc6 3.b4 ?!)

        • [^] # Re: Stockfish est les deux

          Posté par  . Évalué à 4 (+3/-0).

          Stockfish est purement un moteur classique, même s'il utilise aujourd'hui un réseau neuronal pour évaluer les positions : il explore énormément de branches avec un algorithme minimax, et évalue les positions rapidement avec une fonction d'évaluation rapide et rudimentaire (comparé aux descendants d'AlphaZero, pas à deepblue). Les optimisations très pointues pour limiter le nombre de branches explorées et donc augmenter la profondeur sont également typiques des architectures classiques, et on les retrouve que le moteur utilise une évaluation NNUE (par réseau neuronal) ou HCE (écrite à la main).

          Je pense que ce qui illustre le mieux la différence entre archi classique et archi "type AlphaZero", est que stockfish explore des millions de noeuds par seconde, alors que le moteur Maia (basé sur LeelaChess0) joue à un niveau correct (jusqu'à 1900 ELO) en utilisant juste la fonction d'évaluation et sans faire de recherche.

  • # Moi aussi!

    Posté par  (site web personnel) . Évalué à 2 (+1/-0).

    C'est amusant. On a eu la même idée. Malgrès mon niveau débutant en programmation, j'en ai conçu un en C++ cet été: https://lichess.org/@/onsenfish (oui. Je n'ai jamais libéré le code. Quelle honte!). Mon objectif était de faire un bot le plus rapide possible sur un seul thread.
    Dans sa dernière version, il jouait de façon médiocre en profondeur 3.

    Ce comentaire est sous license CC0: faites en ce que vous voulez tant que vous ne m'atribuez pas de fausses paroles.

  • # perft avant cutechess

    Posté par  . Évalué à 2 (+6/-1).

    Pour le générateur de coups, cutechess ne dira presque rien tant que les coups illégaux ne sortent pas. Le test qui compte à ce stade, c'est perft : le nombre de feuilles à une profondeur fixe, comparé aux valeurs connues. Depuis la position initiale, 20 à profondeur 1, 400 à profondeur 2. Une attaque de cavalier en moins et le compteur diverge tout de suite. L'éval et la recherche, ça se mesure au match.

    • [^] # Re: perft avant cutechess

      Posté par  . Évalué à 2 (+1/-0).

      Tout à fait ! Je ne l'ai pas précisé dans le journal, mais effectivement ça fera partie de la première étape de m'assurer qu'il n'y a pas de bugs dans le générateur de coups.

  • # Ce que tu me dis pas...

    Posté par  (Mastodon) . Évalué à 5 (+2/-0).

    …et qui me semble essentiel, c'est comment tu mesuresde façon impartiale que le niveau de jeu a augmenté ou pas par rapport au commit précédent? En le faisant jouer contre lui-mēme plein de fois?

    • [^] # Re: Ce que tu me dis pas...

      Posté par  (site web personnel) . Évalué à 4 (+2/-0).

      Je me suis posé la même question ! Si la batterie de test repose sur la mesure de qualité de jeu, il faut bien que cette dernière soit objective, et je me demande comment on atteint cet objectif objectif :-)

    • [^] # Re: Ce que tu me dis pas...

      Posté par  . Évalué à 3 (+2/-0).

      c'est comment tu mesuresde façon impartiale que le niveau de jeu a augmenté ou pas par rapport au commit précédent

      Effectivement, en faisant jouer l'ordi contre lui-même, idéalement en cadences rapides pour que ça ne prenne pas trop de temps. Et en utilisant un test statistique pertinent pour ne pas valider une modification qui aurait gagné davantage de matchs par hasard (en l'occurence la plupart des outils comme cutechess-cli utilisent SPRT).

  • # Au siècle dernier

    Posté par  . Évalué à 5 (+3/-0). Dernière modification le 28 septembre 2026 à 21:50.

    Je me suis intéressé (avec d'autres) à faire tourner un serveur d'échecs (gnuchess) sur une des stations SPARC de l'école ou j'étais pour que l'on puisse se détendre entre deux projets (tout le monde n'était pas fan de dynablaster et de xfrisk). A titre perso, je jouais principalement en blitz (5+0) à l'époque, depuis je préfère le (3+2) (dédicace pour Domi).

    Le code de gnuchess était assez pédagogique, et assez paramétrable pour pouvoir faire tourner la bête et lancer plusieurs parties depuis les différentes stations de l'école sans vraiment entamer les ressources du serveur. Donc grosso modo, on prenait des raclées contre la machine mais comme on pouvait analyser les parties à posteriori, donc on apprenait pas mal et on pouvait s'affronter entres joueurs. On avait un très bon joueur dans la promo qui nous montrait comment essayer de battre la machine mais un jour un T800 est apparu dans la salle et …

    Bien sur, notre envie d'apprendre nous a aussi pousser à "freiner" un peu le serveur, il y a plein de techniques mais je ne voudrais pas que ce commentaires soit supprimé … disons qu'avec une balle dans chaque genou, le serveur d'échecs devenait battable en blitz, même par votre serviteur.

    L'analyse du code de gnuchess de l'époque permettait de faire un peu d'archéologie dans les différentes méthodes d'évaluations utilisées et aussi ce qui m'avait fasciné, c'est la gestion des finales roi pion qui était écrit en FORTRAN vintage par un individu un peu taquin. Si tu veux recoder un programme d'échecs en RUST, je t'engage à commencer par les finales roi pion, et quand tu auras tout compris, tu feras le reste facilement.

    De nos jours, on a lichess.org, stockfish et aussi des échiquiers connectés reliés à des IAs qui font bouger les pièces (ce qui énerve la chatte). Mais on ne sait pas détecter les tricheurs.

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.