Moteur d’échecs expérimental

Introduction au sujet

Les premiers programmes dit "moteurs d'échecs" voient le jour dans les années 1950, avec le développement des premiers ordinateurs. Le premier programme fut Turochamp, écrit par Alan Turing qui a notamment joué un rôle important durant la Seconde Guerre Mondiale en créant Énigma (que je ne développerai pas ici), mais le principe de moteur d'échecs a commencé à apparaître à la fin du XVIIIeme siècle, même s'il s’agissait d'une personne de petite taille cachée dans une boite qui jouait les coups.

Quelques moteurs d'échecs connus

Depuis Turochamp, Une infinité de moteurs d'échecs ont vu le jour, tous plus ou moins puissants et développés par des informaticiens et des joueurs d'échecs. Nous vous en présentons 3 importants dans le monde des échecs ci-dessous :

Deep Blue

Une reproduction de Deep Blue (Ordinateur IBM), exposé au Musée de l'histoire de l'ordinateur de Mountain View en Californie.(Source : Wikipédia)

Premier moteur d'échecs à battre officiellement un joueur d'échec professionnel (2 victoires, 3 parties nulles et 1 défaite contre Garry Kasparov, champion du monde à ce moment là en 1997)

Stockfish

Moteur d'échecs considéré comme le moteur d'échec conventionnel le plus puissant du monde (Classement Elo de 3793 points, ce qui est un record du monde à cette date)

AlphaZero

Moteur d'échecs à apprentissage, utilisant l'approche généralisée d'AlphaGo Zero Le site Wikipédia d'AlphaGo Zero et donc adapté pour jouer aux échecs et au shogi (échecs japonais), il a battu Stockfish en 2017. Cependant, Stockfish n'avait pas accès à toutes ses fonctionnalités, notamment ses tables de finales.

Création du moteur d'échecs expérimental en Python

Après quelques études sur les moteurs d'échecs, il a fallu commencer à développer le mien.

Ce qui a été réalisé au départ

Au départ du projet, et après quelques expérimentations avec le module Chess utilisable avec Python, j'ai, en premier lieu, récupéré l'échiquier sous forme de tableau Python et ai voulu développé des fonctions qui me permettaient de récupérer la liste des coups pour chaque pièce sur l'échiquier.

Les problèmes rencontrés

En commençant à vouloir créer ces fonctions là, il y avait toujours un problème qui faisait que soit la fonction ne fonctionnait tout simplement pas, soit elle ne me renvoyait pas tous les coups possibles, soit me renvoyait trop de coups (par exemple, le cas ou la pièce n'a pas le droit de passer au dessus d'une autre pièce, sauf le cavalier qui lui en a le droit, a posé énormément de problèmes car de la façon que j'avais codé mes fonctions, et ce, même en essayant de réparer le problème, elles passaient quasiment tout le temps au dessus alors qu'elles ne devaient pas passer au dessus). J'ai donc passé beaucoup de temps à rendre fonctionnelle cette partie du code et n'a pas pu en consacrer sur l'interprétation des coups et les réponses.

Ce qui a du être finalement fait

Ces problèmes m'ayant pris énormément de temps, je n'ai pas pu commencer la partie renvoi des coups et me suis arrêté à la partie détection des coups possibles, et comme Robin, avec qui je réalisais le projet, a décidé d'arrêter le CMI, il a accepté de me donner son code, beaucoup plus avancé que le mien, pour que je puisse finaliser le projet avec un prototype de moteur d'échec fonctionnel. C'est donc le moteur d'échecs de Robin que je vous présenterai ci-dessous.

Le moteur d'échec expérimental final

Comme dit ci-dessus, je présenterai donc celui de Robin pour le fonctionnement et les matchs.

Fonctionnement du moteur d'échecs expérimental

Fonctionnalité principale

Chaque pièce vaut une certaine valeur, le pion est celle qui en a le moins, car c'est le moins important, tandis que le roi est celle qui en a le plus, car c'est la pièce qu'il faut protéger en priorité. L'algorithme créé par Robin permet de faire une liste de coups, du meilleur score au pire.

Ce qui est effectué par le programme à chaque tour :

• On vérifie en fonction de la position d'une pièce qui peut l'attaquer et qui peut le défendre.
• On teste ensuite un mouvement sur la pièce précédemment testée et on voit si le nombre d'attaquants et de défenseurs diffère, ce qui permet de tester si la pièce est sur une case plus sécurisée que précédemment, ce qui lui fait avoir un gros bonus, et inversement si elle est envoyée vers une case plus dangereuse que celle d'avant.
• On regarde également si, sur sa nouvelle case, la pièce est capable d'attaquer d'autres pièces, ce qui lui attribue un bonus dans ce cas-là. On attribue également un bonus plus important s'il s'agit de pièces importantes comme la reine ou la tour.

Fonctionnalités secondaires

• Un bonus est attribué si la case n'est pas dangereuse.

• La pièce récupère le gain de la pièce attaquée si elle en attaque une.

• Les pièces au centre de l'échiquier reçoivent un bonus (cases D4,E4,D5,E5)

• On attribue un petit bonus si le déplacement de la pièce permet de mettre en échec le roi (pas échec et mat)

• On attribue un bonus si la pièce peut obtenir une promotion lors de son mouvement.

• On attribue une pénalité au roi si on le bouge lors des 20 premiers tours (exception lorsqu'il y a échec)

Quelques matchs contres d'autres moteurs d'échecs

Pour ces matchs, j'ai dû composer avec ceux disponibles dans l'application Arena.

Nous ferons donc les matchs avec les moteurs d'échecs suivants :

• AnMon 5.75 : Ce moteur a 2504 points d'Elo.
• Dragon 4.6 (Pas celui de Komodo) : Ce moteur a 2358 d'Elo.
• Spike 1.4 : Ce moteur a 3054 points d'Elo.

Afin de faire des parties équitables, je réaliserais 6 parties, durant lesquelles le moteur sélectionné commencera 3 fois en premier et le moteur expérimental commencera 3 fois en premier, comme lors des matchs officiels entre joueurs professionnels et moteurs d'échecs.

Je donnerai des détails concernant la rapidité des parties, le temps de calcul des moteurs ainsi que les résultats pour chaque moteur.

Ces matchs ne déterminent en aucun cas le classement Elo du moteur expérimental, car il faudrait réaliser des milliers de parties contre beaucoup plus de moteurs d'échecs pour le déterminer.

Quelques parties contre AnMon

Résultats finaux : (Moteur - AnMon) 0 - 6

Remarques de ces matchs : Il y a eu quelques sacrifices de la reine du côté moteur alors qu'il y avait d'autres pièces qui pouvaient prendre l'attaque. Le roi est également parti du côté ennemi alors que ce n'était pas sécurisé du tout.

Quelques parties contre Dragon

Résultats finaux : (Moteur - Dragon) 0 - 6

Remarques de ces matchs : il y a eu moins de sacrifices et moins de problèmes avec le roi que contre AnMon, mais aucune victoire malgré tout.

Quelques parties contre Spike

Résultats finaux : (Moteur - Spike) 0 - 6

Remarques sur les matchs : On remarque les mêmes problèmes que contre AnMon.

Remarques sur les parties

Je n'ai pas eu le temps de peaufiner le moteur dans la limite du possible, on est donc sur un moteur encore assez fragile, notamment dès que les compteurs de score s'affolent, ce qui peut se remarquer dans certaines parties, je présume même que le fait que le Roi qui part vers de "meilleurs horizons" vienne de là.

Chaque partie mettait moins de 5 minutes à se réaliser, et seuls les moteurs de l'application mettaient du temps à réaliser leurs calculs, le moteur expérimental étant très rapide dans ses calculs.

Certaines parties ont pu également être très rapides à cause du fait que le moteur se mette facilement en danger.

Remarques finales

Le moteur expérimental est donc capable de réaliser des coups intéressants qui prennent en compte un ou deux coups d'avance, mais il a du mal à faire les fins de parties (un test de match entre moi-même et le moteur, ou je faisais presque exprès d'exposer mon roi, et il l'a pris qu'après quelques coups.) et se met parfois trop en danger (le roi qui part vers de "meilleurs horizons" du côté de l'ennemi, ou la reine qui se sacrifie alors que d'autres pièces pouvaient prendre sa place)

En résumé : Intéressant à utiliser, mais le doubler d'un second moteur spécialisé dans les fins de parties serait la meilleure chose à faire pour ce moteur à mon avis. Améliorer certains points, notamment sur les sacrifices pour diminuer les risques d'éliminer la reine n'est pas de refus pour ce moteur également.

Remerciements et sources

Je remercie l'Université Savoie Mont Blanc, l'UFR Sciences et Montagne, le Laboratoire LAMA, notre professeur référent de la filière CMI informatique Mr. Hyvernat ainsi que mon référent sur ce projet, Mr. Negro pour m'avoir permis de réaliser ce projet.

• Les informations en rapport avec les moteurs/programmes d'échecs : https://fr.wikipedia.org/wiki/Programme_d%27%C3%A9checs
• Deep Blue : https://fr.wikipedia.org/wiki/Deep_Blue
• StockFish : https://fr.wikipedia.org/wiki/Stockfish_(programme_d%27%C3%A9checs)
• Alphazero : https://fr.wikipedia.org/wiki/AlphaZero
• Module d'échecs Python : https://python-chess.readthedocs.io/en/latest/