Grilles et IA

Ces programmes ont un point commun : une grille, des règles fermées, et très vite l’envie d’écrire quelque chose qui joue à la place du joueur. C’est le même chemin qui mène, plus tard, à OptiChess et au solveur de jeux.

2048. Le jeu complet, avec un menu (nouvelle partie, chargement, options), une sauvegarde, une taille de grille au choix et des tuiles dessinées jusqu’à 131 072. Une seconde version, reprise plus tard, réécrit le cœur pour Numba : chaque coup possible est évalué en terminant la partie au hasard un grand nombre de fois, en parallèle, et l’ordinateur choisit le coup dont la moyenne est la meilleure. Expectimax et Monte-Carlo plus fins sont restés dans la liste des envies.

Puissance 4. La grille est codée en deux entiers, une position et un masque, et l’alignement de quatre se teste par quelques décalages de bits, la même idée que les bitboards des moteurs d’échecs. Autour, une série d’adversaires de force croissante : au hasard, un qui gagne quand il le peut et bloque quand il le doit, un minimax avec élagage alpha-bêta, et un statisticien qui joue cent parties pour chaque coup. Un tournoi de mille parties les départage.

Sudoku. Un solveur par retour sur trace, puis un générateur : remplir une grille au hasard, retirer des chiffres. Six niveaux, du débutant au « diabolique », selon le nombre de cases vidées. Rien ne garantit encore que la solution soit unique ; c’est la première ligne de la liste.

Échecs. Le premier programme d’échecs, en 2019 : un plateau, des pièces qu’on déplace à la souris, la vérification des coups légaux et des échecs, puis un adversaire par minimax sur une évaluation du matériel et de la position des pièces. Il s’est révélé trop lent pour aller loin, et c’est cette lenteur qui a décidé du moteur suivant, écrit en C++.