Entraîneur aux échecs

Bonjour la communauté,

Je suis développeur web depuis plusieurs années maintenant et bien que plutôt orienté back, il m’arrive de toucher au front avec JavaScript. Je me suis récemment remis à faire quelques parties d’échecs et ça m’a donné l’envie de faire une IA pour me combattre. Des projets de jeux d’échecs ce n’est pas ce qui manque, donc on peut dire que ce qui m’a motivé c’est plus le fait de m’amuser à développer que le résultat final.

Le projet est dans un état fini, puisque les règles sont opérationnelles, et on peut jouer entre humains, contre une IA random ou contre une IA MinMax voire même faire jouer des IA entre elles.

Tester

Vous pouvez directement tester le jeu en ligne :

chess trainer online

Ou vous pouvez télécharger le projet github, vous pourrez ainsi choisir quels agents vont s’affronter :

chess trainer’s github

Algorithme MinMax

Rien de fabuleux à cet algorithme puisqu’il est bien connu et documenté sur la toile. Il calcule quel est le meilleur coup à jouer en simulant tous les coups possible. Il fait son choix en partant du principe que l’adversaire fera toujours le meilleur choix.

La principale limite de cet algorithme c’est qu’il est très gourmand. Plus on simule de profondeurs plus on va augmenter exponentiellement le nombre de calculs. Ainsi, pour un ordinateur portable ou un smartphone, je paramètre à 2 le nombre de profondeurs, ce qui veut dire qu’il calcule les coups pour le tour actuel + 2 tours dans le futur. Donc si je suis le joueur blanc, il calcule mon meilleur coup actuel, puis pour chacun de ces coups le meilleur suivant du joueur noir, puis pour chacun de ces coups, le meilleur coup du joueur blanc du tour suivant. Avec un bon processeur, ça reste viable de mettre 3 profondeurs (testé avec un Processeur Ryzen 5 2600).

A venir

Alors là ça dépend, l’état actuel du projet était mon objectif. Donc à priori le projet est fini. Ceci dit, si d’autres personnes ont réalisé des projets similaires et ont des conseils en terme d’optimisation ou de scoring, je reste preneur. Je pourrais mettre en place une IA de type supervisé, mais pour que ce soit pertinent, il faut une grande base de données d’exemples de parties. Quitte à faire une IA plus poussée j’aurai préféré quelque chose de non supervisé.

Voilà

mais pour que ce soit pertinent, il faut une grande base de données d’exemples de parties.

Si 670 000 000 suffisent, ça existe

Sinon, bravo pour avoir réalisé ton projet !

J’ai testé le projet en ligne, penses-tu pouvoir optimiser sa rapidité de réaction ?

Super comme projet !

Merci pour vos retours

Hum, si tu as des sugestions …

Si 670 000 000 suffisent, ça existe Sinon, bravo pour avoir réalisé ton projet !

En effet !

Une base de donnée d’ouvertures ? J’ai été étonné par 1. e4 b6.

Dans le même genre, il existe des tables pour jouer parfaitement quand il n’y a plus que quelques pièces sur l’échiquier.

Mais pour la rapidité en elle-même, pour pouvoir avoir plus de profondeur, pourquoi ne pas abandonner l’idée des sacrifices pour l’instant ? C’est à dire que si le score au tour 1 est trop mauvais, bah on ne regarde même pas le tour 2, et ainsi de suite.

Effectivement, pour le rendre plus dangereux sans augmenter les itérations, des tables de coups à jouer c’est sans doute le meilleur choix.

Pour le fait d’éviter des sacrifices, ce serait dommage peut-être de perdre en qualité de jeu. Je ne sais pas, je manque de pratique pour juger de la pertinence.

En tout cas ça donne de quoi réfléchir.

Salut !

Pour améliorer le minmax, tu peux élaguer les branches qui te semblent trop mauvaises (alpha beta pruning). Forcément il faut faire attention, parce que tu peux perdre de vue des gambits comme ça, mais heuristiquement ça te donne une solution pas trop éloignée de l’optimal. Mais en même temps, un simple minmax peut aussi passer à côté d’un gambit si l’avantage ne se révèle que tardivement. Ou alors, implémenter un score qui prenne en compte l’avantage positionnel.

Un autre algorithme dont tu peux t’inspirer est celui de Stockfish : c’est celui utilisé sur Lichess, mais bon j’imagine que l’algo est pas mal compliqué donc il faudra trouver des articles d’explications.

Je ne pensais pas recevoir tant d’idées. Un autre algorithme à découvrir ça me plaît bien.

Sinon j’ai regardé au niveau des coups possibles et j’avais fait une erreur qui faisait qu’il cherchait à réaliser des coups qui étaient ensuite refusés par les règles du jeu. En réglant ça j’ai gagné entre 20 et 30% d’itérations. C’est plutôt une bonne nouvelle.=

Salut,

Je ne sais pas ce que tu déjà implémenté ou pas, mais tu peux avoir une amélioration importante en intégrant plus de facteurs au calcul du scoring d’une position comme la structure des pions, si le roi a roqué ou pas, la mobilité des pièces, etc… La difficulté étant de scorer correctement ces facteurs suivant l’avancée de la partie.

Ceci combiné à l’alpha-beta pruning te permettra de mieux discriminer les positions entre elles et donc d’en examiner moins. En revanche, le calcul du scoring prendra plus de temps donc il y a un équilibre optimal à trouver et le temps d’évaluation d’une position et le nombre de positions testées.

L’alpha-beta pruning peut également être implémenté de manière itérative en terme de profondeur de réflexion, c’est-à-dire qu’on commence par une recherche en profondeur 1, puis 2, etc… car le résultat de la recherche pour la profondeur précédente permet d’élaguer plus efficacement la suivante.

Les programmes très forts utilisent également les bitmaps pour générer les coups valides plus rapidement (c’est d’autant plus performant sur des architectures 64 bits).

En évolution future tu pourrais également ajouter un agent en mode console capable de jouer contre une autre IA en utilisant un protocole de communication standardisé comme Winboard ou UCI.

Tout ceci n’étant nullement exhaustif et issu pour ma part d’une expérience assez lointaine dans le développement d’IA (2009–2010)

Salut frmvega,

J’ai mis du temps à te répondre, les points que tu as soulevé necissitait réflexion.

Mes facteurs de scoring sont peu travaillés, je ne score même pas la promotion c’est dire. Effectivement il y a un axe de progression certain ici. Par contre, je ne vois pas l’intérêt de scorer le fait que le roi ait roqué ou pas ?

Concernang l’alpha pruning je n’arrive pas a voir comment l implémenter ici mais il est possible que j’ai implémenté une version personnalisée du min max. En effet, je cumule l évaluation du coup actuel avec le meilleur score descendant. Pas sûr que ce soit compatible avec l’alpha pruning.

En évolution future tu pourrais également ajouter un agent en mode console capable de jouer contre une autre IA en utilisant un protocole de communication standardisé comme Winboard ou UCI.

J’avais pensé à faire un agent qui utilise une api pour permettre de jouer en reseau mais après on s’éloigne un peu de la raison qui m’a poussé a faire ce projet qui était de coder une ia.

Entre temps j’ai optimisé mon programme et le resultat est convainquant, au tout début, sur mon ordi portable, le premier coup prenait 5 secondes pour une profondeur de 2 alors qu’il en prend 2 désormais. J’explore actuellement les workers javascript pour passer par des threads.

Salut obedient,

Par contre, je ne vois pas l’intérêt de scorer le fait que le roi ait roqué ou pas ?

J’avais vu sur des forums que certains moteurs l’intégrait dans l’évaluation du niveau de protection du roi ("king safety"). Mais en revérifiant il semble en effet qu’une minorité évalue cela (la protection du roi étant par contre un facteur important mais pas facile à scorer).

Concernang l’alpha pruning je n’arrive pas a voir comment l implémenter ici mais il est possible que j’ai implémenté une version personnalisée du min max. En effet, je cumule l évaluation du coup actuel avec le meilleur score descendant. Pas sûr que ce soit compatible avec l’alpha pruning.

L’alpha-beta pruning fait l’évaluation complète des positions à la profondeur terminale seulement (feuilles de l’arbre). D’après ce que je comprends tu cumulerais plutôt les évaluations faites à chaque niveau, dans ce cas cela remettrait en question ton algo.

Sinon j’avais testé entre temps ton programme en ligne et il était parfaitement fonctionnel :).

Par contre en ce moment je n’arrive pas à démarrer la partie, peut-être que tu es en train de travailler dessus.

L’alpha-beta pruning fait l’évaluation complète des positions à la profondeur terminale seulement (feuilles de l’arbre). D’après ce que je comprends tu cumulerais plutôt les évaluations faites à chaque niveau, dans ce cas cela remettrait en question ton algo.

Faut que je me plonge plus dedans, je suis sans doute passé à côté de quelque chose. J’ai lu par ailleurs, que l’alpha pruning pouvait passer à côté de certains coups plutôt évident dans certains cas. Mais je vais tester je verrais bien par empirisme.

Sinon j’avais testé entre temps ton programme en ligne et il était parfaitement fonctionnel :). Par contre en ce moment je n’arrive pas à démarrer la partie, peut-être que tu es en train de travailler dessus.

Oui effectivement j’avais uploadé une version buguée.

La nouvelle version utilise les web workers. Pour ceux qui ont des processeurs multi-core, le résultat est sympa. Avec un Processeur Ryzen 5 2600, une profondeur de 3 prenait plus de 40 secondes à être traitée (premier tour) c’est désormais un peu plus de 10 secondes avec les web workers.

J’ai pu mettre en place l’alpha beta pruning et ça c’est cool. Pour qu’il soit efficace et qu’il ne fasse passe pas à côté de coups importants, j’ai du fixer le seuil assez haut. Il arrive que sur certains tours je gagne 20 à 30%, c’est pas folichon mais c’est déjà bien. Melepe m’avait proposé de regarder Stockfish qui est un programme open source qui implémente l’alpha beta pruning tardif de manière agressive de ce que j’en ai pu lire. Mais pour le coup je vais laisser le programme en l’état, j’ai beaucoup appris et c’était très fun.

Il est temps d’aller sur d’autres projets.

Salut,

Je ne sais pas de quel seuil tu parles, mais l’alpha-beta pruning est strictement équivalent à l’algorithme minimax en termes de résultats. Le principe de l’algorithme est d’éviter d’explorer des nœuds dont on est sûr qu’ils ne contribuent pas au résultat. Si tu obtiens des résultats différents, soit l’implémentation est incorrecte, soit il ne s’agit pas d’un élagage alpha-beta.

Il existe aussi d’autres algorithmes beaucoup plus efficaces, comme MTD. Et comme l’a fait remarqué fromvega, il est possible d’utiliser des bitboards pour calculer l’ensemble des déplacements possibles. C’est bienplus compliqué à implémenter (tu peux trouver des infos ici : https://www.chessprogramming.org/Bitboards), mais l’impact sur les performances est énorme.

Je ne sais pas de quel seuil tu parles

Donc tu n’as jamais implémenté d’alpha-beta pruning pour un jeu d’échec.

J’ai effectué mon TIPE il y a quelques années précisément sur ce sujet, donc si, j’ai déjà implémenté cet algorithme. Je ne comprends d’ailleurs pas vraiment l’agressivité de ton message, je souhaitais simplement t’aider en signalant cette erreur.

Pour citer Wikipédia (le gras est de moi),

L’algorithme n’a que deux paramètres (en plus de la profondeur), $\alpha$ et $\beta$, qui sont normalement fixés à $\pm \infty$ au début de l’exploration.

Une explication possible est que tu implémentes une méthode nommée aspiration search sur la page anglaise de Wikipédia, qui consiste à donner des valeurs finies à $\alpha$ et/ou $\beta$ au début pour élaguer de plus grandes parties de l’arbre (c’est peut-être le seuil dont tu parlais). Si c’est ce que tu fais, tu risques en effet de passer à côté de certains coups, bien qu’il est possible de détecter quand le résultat est faux pour relancer l’algorithme avec de nouvelles valeurs (c’est plus ou moins le principe de l’algorithme MTD).

Mais je maintiens que l’élagage alpha-bêta, sans améliorations heuristiques, est équivalent au minimax.

Salut Kaladin,

J’ai effectué mon TIPE il y a quelques années précisément sur ce sujet, donc si, j’ai déjà implémenté cet algorithme.

Sur un minmax de jeu d’échecs ? Je ne le crois pas.

Je ne comprends d’ailleurs pas vraiment l’agressivité de ton message, je souhaitais simplement t’aider en signalant cette erreur.

Il n y a pas d’agressivité dans mon message par contre il est vrai que j’ai expédié ma réponse précisément parce que tu parles d’un sujet que tu ne semble pas comprendre.

Mais je maintiens que l’élagage alpha-bêta, sans améliorations heuristiques, est équivalent au minimax.

L’élagage alpha-bêta sans améliorations heuristiques n’a aucun intérêt sur un jeu d’échec. Or Stockfish implémente bel et bien l’alpha beta pruning … tu vois ou je veux en venir ?

Tout ce que tu dis est vrai pour un jeu de morpion mais dans le cas d’un jeu d’échecs ça ne marche pas.

Sur un minmax de jeu d’échecs ? Je ne le crois pas.

Libre à toi de croire ce que tu veux. Je peux t’envoyer le code si tu insistes.

Il n y a pas d’agressivité dans mon message par contre il est vrai que j’ai expédié ma réponse précisément parce que tu parles d’un sujet que tu ne semble pas comprendre.

Je ne serais pas intervenu sur ce sujet si je ne comprenais pas de quoi je parle. Il y a moins de deux semaines, tu présentes ici une version basique du minimax et demandes de l’aide pour l’améliorer, et aujourd’hui tu es expert en la question ?

J’ai regardé ton code sur Github, et comme je le craignais tu n’implémentes pas un élagage alpha-bêta. Tu crées ici deux variables maxPrunesThreshold et minPrunesThreshold, qui devraient correspondre aux paramètres $\alpha$ et $\beta$ de l’algorithme. Sauf que ces variables sont censées être mises à jour pendant le parcours de l’arbre, ce que tu ne fais pas. Regarde le pseudo-code de l’algorithme sur Wikipédia par exemple, il contient les lignes

if maximizingPlayer then
   ...
   α := max(α, value)
   ...
else
   ...
   β := min(β, value)
   ...

En fait, ce que tu fais reviens juste à arrêter l’exploration lorsqu’on tombe sur une valeur extrême, ce qui entraine évidemment un résultat faux.

Je vais essayer de t’expliquer le principe de l’élagage alpha-bêta sur un exemple :

Imaginons que le joueur cherchant à maximiser son score ait deux choix. Il va falloir évaluer ces deux choix, leur associer des scores $v1$ et $v2$, et choisir le meilleur.
On commence par évaluer le premier, en parcourant ses sous-noeuds, en évaluant la valeur des feuilles à la profondeur choisie… et on lui associe par exemple une valeur $v1=10$.
Ensuite, on évalue le second choix. On se déplace dans le sous-arbre correspondant, et c’est maintenant à l’adversaire de jouer. Il va chercher à minimiser le score obtenu. Mettons qu’il puisse jouer trois coups différents. On commence par évaluer le premier, comme d’habitude en explorant son sous-arbre, et on lui associe par exemple le score $5$.
Puisque la valeur de $v2$ sera le minimum de tous les scores obtenus dans le sous-arbre, $v2\le 5$. Mais $v1=10$, donc $v1>v2$, et on sait ainsi que quoi qu’il arrive, le meilleur coup sera le premier. Il n’est donc pas nécessaire d’évaluer les deux autres coups de l’adversaire. On évite ainsi d’explorer de grandes parties de l’arbre, sans affecter le résultat final.

Tu peux aussi regarder les schémas sur Wikipédia, ils illustrent bien le principe.

L’élagage alpha-bêta sans améliorations heuristiques n’a aucun intérêt sur un jeu d’échec.

Ce n’est pas tout à fait vrai. L’élagage alpha-bêta seul est déjà meilleur que minimax. Pour info, mon implémentation de l’élagage tournait 2 à 3 fois plus vite que minimax à la profondeur que j’avais choisie. Mais il existe en effet des algorithmes beaucoup plus performant. Pour comparaison, l’algorithme MTD m’a permis d’augmenter la profondeur d’exploration de 2 ou 3 demi-coups, sans changer le temps d’exécution.

Ensuite, l’utilisation d’heuristiques n’implique pas forcément que l’algorithme n’est plus équivalent au minimax. Par exemple, une technique très utilisée est d’estimer quels seront les meilleurs coups, pour les évaluer en premier et espérer ainsi un élagage plus important.

Or Stockfish implémente bel et bien l’alpha beta pruning … tu vois ou je veux en venir ?

Je n’ai jamais prétendu que Stockfish n’utilisait pas l’élagage alpha-bêta, ni même qu’il était équivalent à un minimax. Il ne l’est d’ailleurs certainement pas, mais pas pour les raisons que tu avances.

Si tu regardes ce commentaire dans le code de Stockfish, tu te rends compte que la méthode utilisée est l'aspiration search que je décrivais dans mon post précédent. Lorsque le résultat obtenu est incorrect (c’est-à-dire hors de la fenêtre de recherche), la fenêtre est élargie, jusqu’à obtenir un résultat qui tombe dedans. Cette portion du code renvoie donc le même résultat qu’un minimax. Mais ce n’est certainement pas le cas pour les autres techniques utilisées.

Tout ce que tu dis est vrai pour un jeu de morpion mais dans le cas d’un jeu d’échecs ça ne marche pas.

Il serait complètement inutile de vouloir implémenter un élagage alpha-bêta pour un jeu de morpion, alors qu’il est possible de parcourir la totalité de l’arbre de jeu quasi-instantanément (il ne contient que quelques milliers de nœuds).

Il y a moins de deux semaines, tu présentes ici une version basique du minimax et demandes de l’aide pour l’améliorer, et aujourd’hui tu es expert en la question ?

Tu aimes bien les propos extrêmes, deux sur un même sujet ça fait beaucoup.

Je vais essayer de t’expliquer le principe de l’élagage alpha-bêta sur un exemple : …

Après lecture tu m’as mis le doute. J’ai donc cherché, fait des tests et je suis aussi tombé sur l’article suivant que j’ai trouvé particulièrement bien fait :

https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/

Et c’est avec joie que j’ai découvert que tu avais raison.

Donc merci pour ton insistance.