← Les six écoles

Divination · données et IA de jeu

UTTT

Une IA en C++ pour l'Ultimate Tic-Tac-Toe, écrite en binôme pour battre le moteur de notre professeur. Meilleur résultat : 72 victoires, 17 défaites et 11 nuls sur 100 parties contre MEDIUM_2.

D'où on partait

C'était la première fois que nous écrivions un programme qui décide seul. Nous arrivions avec très peu de connaissances en théorie des jeux et en algorithmes de recherche, apprises en construisant. Vu de là, 72 % contre le moteur moyen est un résultat dont je suis content.

Le jeu

Neuf petites grilles dans une grande. L'endroit où l'on joue dans une petite grille envoie l'adversaire dans la petite grille correspondante. Trois petites grilles alignées gagnent la partie. Chaque coup est deux décisions à la fois : la case qu'on prend, et l'endroit où l'on envoie l'autre.

Le moteur

  • Minimax avec élagage alpha-bêta et approfondissement itératif.
  • Une table de transposition avec hachage de Zobrist.
  • Un tri des coups avec coups tueurs et table d'historique.
  • Une évaluation positionnelle, et un livre d'ouvertures qui se remplit tout seul à partir des parties de tournoi.
  • Environ 1 800 lignes de C++, branchées sur le moteur du professeur par une interface imposée.

Comment il est arrivé à 72 %

La première version gagnait entre 0 et 20 % contre MEDIUM_2, à environ 350 ms par coup. Passer à une profondeur de 14 avec 10 secondes de réflexion et ajouter le livre d'ouvertures l'a mené à 72 % sur 100 parties, avec une profondeur moyenne de 11,3 et 319 coups tirés du livre.

Ce que j'en retiens

  • Des échantillons de 10 parties, c'est du bruit. Seules les séries de 100 nous ont appris quelque chose.
  • Debug et Release jouent comme deux moteurs différents ; toujours mesurer en -O3.
  • Les scores de mat stockés dans la table doivent être corrigés par la distance, sinon le moteur croit n'importe quoi.
  • Un livre d'ouvertures devient faux dès que l'évaluation change.
  • Pas fait : la recherche de quiescence, le multithread, la recherche arborescente Monte-Carlo, qui est ce qui gagne à ce jeu.
L'organisation du moteur, redessinée à partir du diagramme de classes du dépôt.
L'organisation du moteur, redessinée à partir du diagramme de classes du dépôt.
La série de 100 parties derrière les 72 %, tracée à partir du journal conservé dans le dépôt (logs/ai_log_20260503_173054.csv).
La série de 100 parties derrière les 72 %, tracée à partir du journal conservé dans le dépôt (logs/ai_log_20260503_173054.csv).