Comparer des méthodes d'IA est plus difficile qu'il n'y paraît : il faut un jeu rapide, un juge incontestable, et des règles du jeu identiques pour tout le monde. Voici comment c'est fait, et les pièges rencontrés en route.
Une grille de 7 colonnes sur 6 lignes tient sur 49 bits. On la range donc dans deux entiers : masque dit où sont les pions, joueur dit lesquels appartiennent à celui qui doit jouer. On réserve un bit de garde en haut de chaque colonne, ce qui porte à 7 le nombre de bits par colonne et empêche une colonne de « déborder » sur sa voisine.
Jouer un coup tient alors en trois lignes, sans aucune boucle :
m = (masque + (1 << (c * 7))) & colonne(c) # la case libre la plus basse
joueur ^= masque # au tour de l'adversaire
masque |= mLe joueur ^= masque mérite un instant d'attention : comme joueur désigne toujours « les pions de celui qui doit jouer », changer de camp revient à inverser l'appartenance de tous les pions. Détecter un alignement de 4 se fait de la même façon, par décalages :
def aligne4(p):
for s in (1, 7, 6, 8): # vertical, horizontal, deux diagonales
m = p & (p >> s)
if m & (m >> 2 * s):
return True
return FalseLe même moteur existe deux fois : en Python pour entraîner (env.py) et en JavaScript pour jouer dans votre navigateur (env.js). En JavaScript, les nombres ordinaires n'ont pas d'opérateurs binaires au-delà de 32 bits : on utilise donc des BigInt. Un test automatique rejoue 40 suites de coups des deux côtés et vérifie que tout concorde, coup par coup : même grille, même gagnant, mêmes coups légaux.
Le Puissance 4 est résolu depuis 1988 : en jeu parfait, le premier joueur gagne en jouant au centre. On peut donc faire mieux que compter les victoires, et noter chaque décision contre la vérité.
Le solveur (solveur.c, en C) explore l'arbre complet avec les techniques classiques : élagage alpha-bêta, recherche par dichotomie sur le score à fenêtre nulle, table de transposition de 8 millions d'entrées, tri des coups par nombre de menaces créées, et abandon immédiat des coups qui offrent la victoire à l'adversaire. Il est écrit d'après la méthode décrite par Pascal Pons, dont le code n'a pas été repris, sa licence étant incompatible avec ce projet.
Comment être sûr que le juge a raison ? Deux contrôles. D'abord, sur 25 positions à 32 pions, ses scores sont comparés colonne par colonne à ceux d'une recherche exhaustive écrite en Python, lente mais évidemment correcte. Ensuite, sur le plateau vide, il renvoie -2 -1 0 1 0 -1 -2 après 9,9 milliards de positions examinées et 18 minutes de calcul : ce sont exactement les valeurs publiées pour le jeu résolu.
Le coût explose quand la grille est vide. Mesuré sur cette machine : instantané à partir de 16 pions, environ 0,1 seconde vers 10 à 12 pions, mais déjà 1,9 seconde à 8 pions. Les positions d'évaluation partent donc de 10 pions, sans quoi le juge coûterait plus cher que tout le reste.
L'alpha-bêta explore les coups sur quelques demi-coups et note les positions obtenues avec une table écrite à la main : chaque case vaut le nombre d'alignements de 4 qui la traversent, ce qui donne naturellement plus de valeur au centre. Les menaces immédiates sont comptées à part.
Le MCTS ne sait rien du jeu. Depuis la position courante, il joue des centaines de parties au hasard jusqu'au bout et retient le coup qui a le mieux réussi, en équilibrant exploration et exploitation par la formule UCT.
TD(lambda) apprend à noter une position en jouant contre lui-même. L'idée tient en une phrase : la note d'une position doit ressembler à la note de la position suivante. On corrige donc l'écart entre les deux, et on propage la correction aux positions récentes grâce à des « traces d'éligibilité ». C'est la méthode qui a donné TD-Gammon, le joueur de backgammon de niveau mondial de 1992.
NEAT, la méthode des autres jeux du site, fait évoluer une population de réseaux : les meilleurs se reproduisent avec des mutations qui peuvent ajouter des neurones et des connexions. Aucun gradient n'est calculé.
AlphaZero-lite combine les deux mondes. Un réseau propose les coups prometteurs et note la position ; une recherche arborescente guidée par ce réseau joue la partie ; et le résultat de la recherche sert ensuite d'exemple pour entraîner le réseau. Chacun tire l'autre vers le haut. C'est la version miniature du programme qui a battu les meilleurs joueurs de go.
C'est la partie la plus délicate, et la plus facile à rater.
Le classement Elo vient d'un ajustement de Bradley-Terry sur tous les duels, et non d'une suite de matchs : chaque joueur rencontre tous les autres, et l'on cherche les forces qui expliquent le mieux l'ensemble des résultats.
Les réseaux entraînés sont petits, et le navigateur doit décider exactement comme Python. Plutôt que d'embarquer une bibliothèque d'inférence, les poids sont exportés en JSON et recalculés en quelques lignes de JavaScript (reseau.js). Pour NEAT, dont la forme du réseau est quelconque, on reproduit à l'identique le calcul de neat-python.
Un test automatique compare les deux côtés sur des observations fixes. Il a d'ailleurs révélé une erreur de raisonnement : l'écart observé ne venait pas de la précision des calculs, mais de l'arrondi des poids à six décimales au moment de l'export. Le test compare donc Python et JavaScript à partir du même modèle exporté, et vérifie séparément que cet arrondi ne change jamais le coup choisi.
| Problème | Symptôme | Cause et correction |
|---|---|---|
| MCTS battu par le hasard | 0 victoire sur 20 contre un joueur aléatoire | La valeur d'un coup est comptée du point de vue de l'adversaire, puisque c'est lui qui joue ensuite. Il fallait la minimiser, pas la maximiser. |
| Test de parité en échec | Écart de 1,007 × 10⁻⁶, juste au-dessus du seuil | Ce n'était pas la précision des nombres, mais l'arrondi des poids à l'export. On compare désormais au modèle réimporté. |
| Trois profondeurs, un seul score | Résultats identiques au dixième près pour trois réglages différents | Fausse alerte, vérifiée : les coups choisis diffèrent bien sur 12 positions sur 60. L'égalité des totaux venait du trop petit nombre de positions, porté à 200. |
| Un juge trop lent | Près de 2 secondes par position en début de partie | Le coût explose quand la grille est vide : les positions d'évaluation commencent à 10 pions. |
Une seule commande refait l'ensemble : entraînements, mesures contre le solveur, tournoi, courbes et poids exportés.
.venv-shinobi/bin/python arena/scripts/bench_connect4.py --budget 300000 --graines 5
.venv-shinobi/bin/python arena/scripts/bench_connect4.py --rapide # version courte
.venv-shinobi/bin/python -m pytest arena/games/connect4 -q # les tests