Echec ... ou pas

Ces derniers temps, pour tout un tas de raison (dont une santé qui ne fait pas rêver), j'ai essayé de limiter ma participation à Codingame, et en particulier aux challenges de programmation. En effet, ceux-ci imposent un rythme de codage qui ne me permet pas d'être bon, ce qui est un peu frustrant. Et pire encore, ça m'enferme dans un comportement de codeur passionné, qui ne laisse que peu de place à la vie de famille. Donc je participe beaucoup moins.

Néanmoins, depuis quelques mois, un collègue me tanne avec un problème particulier, qui n'est pas un contest, mais un simple puzzle. Enfin, un simple puzzle ... On parle quand même du jeu des rois. En l'occurence, des parties d'échec avec début de partie aléatoire en deux manches gagnantes. J'avais trouvé toute une série d'excuses de qualité : préparer et participer au Snowcamp, faire avancer mon projet open-source de documentation d'architecture, ...

Mais mon collègue est opiniâtre, et plutôt bien classé ...

Au bout d'un moment, j'ai donc craqué et lancé un projet, évidement en Rust, pour tenter d'implémenter un bot de qualité qui joue aux échecs. Et, comme d'habitude, j'ai d'abord cherché une source d'information de qualité. J'ai eu la chance de tomber sur une très belle série d'articles, un peu datés, mais très bien conçus : Chess Programming, écrits par François Dominic Laramée. J'ai donc méthodiquement implémenté

1. Une base de données des mouvements possibles pour chaque pièce sur chaque case de l'échiquier
2. Le code me permettant de trouver les mouvements réalisables sur un échiquier occupé là aussi pour chaque pièce sur la case qu'elle occupe actuellement.
3. Et là j'ai commencé à caler ...

Je vous explique ...

Ou plutôt, je laisse François-Dominic commencer l'explication du MinMax et de l'AphaBeta. Pour résumer, le but de la partie est de permettre à mon bot de capturer le roi (oui, on ne le fait pas, c'est vulgaire) sans lui laisser la possibilité d'y échapper. Comme ça n'est pas immédiatement possible, on considère qu'un bon "proxy" de ce score est d'avoir plus de valeur sur l'échiquier que l'adversaire. Seulement, ça, c'est un peu biaisé, et en plus en début de partie, il faut un autre proxy. On peut par exemple imaginer essayer de gagner les cases près du centre.

Bon, évidement, il y a un bon paquet de positions à évaluer à chaque tour, qui fait qu'un bot ne peut pas faire d'évaluation de tous les coups ... Mais ça, c'est assez classique dans les jeux codingame. En revanche, ce dont je n'ai pas l'habitude, c'est de l'évaluation MinMax, qui à mon sens implique qu'une évaluation inclue mon tour de jeu et celui de l'adversaire.

Tout ça, c'est somme toute assez classique ...

Donc dans ces cas-là, la méthode "simple" est de sélectionner et scorer les différents coups possibles, et de prendre le meilleur. Et j'en suis là.

Sauf que, comme tout développeur "moderne", j'ai créé des tonnes de structures sophistiquées : des Point, des RealMove, des Turn. Et je passe pas mal de temps à faire des .clone(), ce qui ne me satisfait pas (en Java, je ne les verrai pas, parce que Java est bien plus laxiste sur la gestion de la mémoire).

Et, pire encore, j'ai compris un truc : entre deux tours de jeu, il n'y a que tr_s peu de différence : deux pièces ont bougé. Autrement dit, prédire le futur en recalculant à chaque tour les mouvements possibles de toutes les pièces est sacrément efficace. En fait, en l'écrivant, je me rends compte qu'il me faudrait une structure "à la git". C'est-à-dire un arbre des positions possibles qui me permette, quand je passe d'un tour au suivant, de bénéficier directement des calculs effectués au tour précédent.

Autrement dit ... Autrement dit, j'arrive au moment, classique quand je me lance dans un challenge codingame, où je supprime mon code pour le réécrire de zéro (ou à peu près).

J'ai une chance : les règles des échecs sont peut-être complexe (et par rapport aux autres jeux codingame, elles le sont incroyablement), mais au moins elles ne changent pas d'un niveau au suivant. Donc on repart de zéro avec des coups possibles stockés dans des champs de bits (ça fera plaisir à Nicolas), une arborescence de coups qui s'écrase quand on passe au tour suivant, et peut-être une vision plus claire des heuristiques. Souhaitez-moi bonne chance !