Chess Multitool

Publié le 2025-12-13 19:48

Labels: C#

Quand j’ai commencé à développer Chess Multitool, je tenais absolument à avoir une IA d’échecs intégrée, qui fonctionne hors ligne et qui soit correcte, pas ridicule, pas imbattable, mais capable de punir les grosses erreurs et de proposer une vraie opposition. En me lançant là-dedans, je suis passé par les classiques : minimax, alpha-beta pruning, une fonction d’évaluation maison, puis plus tard l’iterative deepening. Et au passage, j’ai aussi appris à quel point une implémentation pas assez optimisée peut brider un moteur, même quand l’algorithme théorique est bon.

Comment FONCTIONNE l’IA de Chess Multitool

Au cœur de l’IA, il y a un schéma très simple : j’essaie de simuler une partie où chacun joue le meilleur coup possible. C’est le principe de minimax, vous pourrez en apprendre plus sur l'article dédié. Du point de vue de l’IA, un coup est bon si, après que l’adversaire a joué lui aussi ses meilleures réponses, la position finale reste favorable. On construit donc un arbre de coups possibles sur plusieurs demi-coups (plies), on évalue les positions au bout de cet arbre, puis on remonte les scores.

Évidemment, si on se contente d’un minimax naïf, l’arbre explose très vite. Avec une trentaine de coups légaux en moyenne, une profondeur de 4, on arrive déjà à des centaines de milliers de positions. Sur un téléphone ou une tablette, ce n’est juste pas viable sans optimisation.

C’est là qu’intervient l’élagage alpha-beta (alpha beta pruning). L’idée est de ne pas explorer les branches qui ne pourront de toute façon pas améliorer le coup final. Pendant la recherche, je maintiens deux bornes :

  • alpha : la meilleure valeur garantie pour le camp qui cherche un coup,

  • beta : la meilleure valeur possible pour l’adversaire.

Dès qu’une branche donne un score qui est déjà pire que ce que l’adversaire peut obtenir ailleurs (c’est-à-dire ≥ beta dans un schéma negamax), je coupe cette branche : plus besoin d’explorer le reste, cette ligne ne sera jamais choisie. Avec un bon ordre de coups, alpha-beta permet de réduire drastiquement le nombre de nœuds visités pour la même profondeur.

J’ai aussi ajouté une recherche de quiétude (quiescence). Quand la profondeur nominale est atteinte, je ne m’arrête pas brutalement : je prolonge la recherche uniquement sur les coups tactiques (captures, promotions, échecs) pour éviter l’« effet d’horizon », où l’IA arrête juste avant un échange important et évalue la position de manière trompeuse.

Ma première approche : profondeur fixe + limite de temps

Au début, j’avais conçu le moteur de façon assez simple : je lui passais une profondeur maximale et une limite de temps. Tant que la profondeur n’était pas atteinte et que le temps était encore disponible, l’IA continuait à explorer l’arbre. Si le temps était dépassé, la recherche s’arrêtait et renvoyait le meilleure score/ coup qu’elle avait en cours.

Sur le papier, ça paraissait raisonnable. En pratique, les logs m’ont vite fait redescendre :

  • certains coups dépassaient largement le budget de temps prévu ;

  • le nombre de positions explorées par coup restait relativement faible pour le temps consommé ;

  • et surtout, l’IA jouait parfois des coups complètement absurdes, par exemple des allers-retours avec une tour ou des sacrifices de pièces sans réelle compensation.

Le problème vient du fait que couper brutalement la recherche au milieu d’une profondeur donne un résultat instable. On se retrouve avec un alpha/beta mis à jour de façon partielle, basé sur un arbre incomplètement exploré. Parfois ça tombe bien, parfois ça tombe très mal.

Passage à l’iterative deepening

Pour stabiliser le comportement de l’IA, j’ai fini par abandonner le couple « profondeur fixe + time-out brut » au profit de l’iterative deepening.

Le principe est le suivant : au lieu de lancer d’emblée une recherche à profondeur 3 ou 4, je commence par profondeur 1, puis 2, puis 3, etc. À chaque itération :

  1. Je repars de la position initiale.

  2. J’explore tous les coups jusqu’à la profondeur courante.

  3. Je mémorise le meilleur coup trouvé à cette profondeur terminée.

Tant que le budget temps n’est pas dépassé, j’augmente la profondeur. Si le temps tombe pendant la profondeur 4, je ne jette pas tout : je garde le résultat complet de la profondeur 3, qui lui, a été exploré intégralement.

Ce changement a plusieurs effets positifs :

  • Je suis sûr d’avoir au moins un coup « propre », basé sur une profondeur entièrement calculée.

  • Je peux utiliser les résultats d’une profondeur pour réordonner les coups à la racine à la profondeur suivante, en essayant d’explorer d’abord ceux qui semblaient prometteurs. Ça améliore beaucoup l’efficacité d’alpha-beta.

  • Le comportement de l’IA devient plus régulier : elle arrête rarement son calcul dans un état incohérent.

C’est aussi ce qui m’a amené à simplifier les niveaux de difficulté. Au lieu d’avoir plusieurs niveaux basés sur la profondeur, je suis passé à un niveau unique d’IA, avec un temps de réflexion fixe d’environ 3 secondes par coup. C’est l’iterative deepening qui gère, à l’intérieur de ce budget, jusqu’où la recherche peut aller.

Là où ça coince : performances et copies d’état

Même avec le bon algorithme, la réalité se joue dans les détails d’implémentation. Les moteurs d’échecs très rapides utilisent souvent des représentations très compactes (bitboards, tables de transposition, make/unmake ultra optimisés, etc.). De mon côté, dans Chess Multitool, j’ai fait des choix plus simples, pensés pour rester lisibles.

Concrètement, aujourd’hui, pour explorer un coup :

  • je crée souvent une nouvelle instance de GameState avec un Copy() ;

  • j’applique le coup sur cette copie ;

  • je regénère les coups légaux à partir de ce nouvel état pour continuer la recherche ou pour évaluer la mobilité dans la fonction d’évaluation.

C’est pratique, propre, moins risqué en termes de bugs, mais c’est aussi très coûteux. Chaque nœud de l’arbre déclenche des allocations, du travail pour le GC, des boucles qui parcourent tout le plateau, et parfois des régénérations complètes de la liste des coups.

Résultat : même avec 3 secondes par coup et alpha-beta correctement implémenté, le nombre de positions effectivement évaluées reste limité. On le voit dans les journaux : les nœuds explorés par coup ne sont pas ridicules, mais pas non plus au niveau d’un moteur très optimisé. Et mécaniquement, une IA qui ne peut pas regarder très loin reste vulnérable à certains sacrifices ou à des manœuvres un peu profondes.

Ce que j’aimerais encore améliorer

Il y a deux grandes directions dans lesquelles j’aimerais pousser cette IA.

La première concerne la fonction d’évaluation. Elle est déjà un peu plus sophistiquée qu’un simple « somme du matériel » : je prends en compte du positionnel (centralisation, structure de pions, activité du roi en finale…), mais au prix d’un coût non négligeable, notamment si je recalcule la mobilité en régénérant des coups depuis Evaluate. À terme, l’idée serait de garder une évaluation plutôt simple mais moins gourmande, par exemple en limitant la mobilité à quelques pièces clés, ou en réutilisant des informations déjà calculées lors de la génération des coups.

La seconde direction est probablement la plus structurante : éliminer la copie systématique de GameState pendant la recherche. L’approche classique des moteurs sérieux consiste à garder un seul état mutable, à appliquer des coups avec MakeMove, puis à les annuler avec UnmakeMove (ou en remontant une pile d’historique). Ça demande une gestion plus fine de l’état interne, mais en contrepartie, le coût par nœud chute drastiquement. C’est très probablement le plus gros levier pour permettre à Chess Multitool d’explorer beaucoup plus de positions dans le même temps, sans changer d’algorithme.

Conclusion

L’IA de Chess Multitool repose donc sur une base assez classique : minimax/negamax, alpha-beta pruning, quiescence, le tout orchestré par de l’iterative deepening avec une limite de temps plutôt qu’une profondeur figée. L’évolution la plus importante a été ce passage de la profondeur fixe avec time-out brutal à une approche itérative plus stable, qui garantit toujours de disposer d’un résultat cohérent à la dernière profondeur complétée.

Ce n’est pas un moteur de tournoi, et ce n’est pas l’objectif. Mais c’est une IA offline, intégrée à l’app, capable de proposer une vraie opposition, d’exploiter les erreurs flagrantes et d’accompagner un joueur humain dans ses parties d’entraînement.

La suite logique, ce sera de continuer à travailler « sous le capot » : alléger la fonction d’évaluation, réduire le coût des états intermédiaires, et pourquoi pas un jour migrer vers un système sans copies de GameState pour la recherche. L’algorithme est là ; maintenant, le travail consiste à le mettre au régime pour qu’il puisse calculer plus, plus vite, sans perdre la lisibilité du code qui, pour moi, reste importante dans un projet comme Chess Multitool.

Retour à la liste