Comment elle a appris
Wure n’a reçu que les règles. Pas d’ouvertures, pas de parties de maîtres, pas de conseils. Tout ce qu’elle sait vient de milliers de parties jouées contre elle-même, sur le processeur d’un ordinateur portable.
Deux pièces qui s’aident
Un bon joueur d’awalé fait deux choses : il sent qu’un coup est prometteur, puis il vérifie en calculant la suite. Wure fait pareil, avec deux pièces.
Le réseau, c’est l’intuition. On lui donne une position (les 12 cases, les deux scores, le nombre de coups joués) et il rend deux choses : une politique, une probabilité pour chacun des 6 coups, et une valeur, un nombre entre −1 (je perds) et +1 (je gagne). C’est un petit réseau dense à trois couches cachées de 128 neurones : – paramètres, 200 Ko.
La recherche, c’est le calcul. Il s’agit d’un MCTS (Monte Carlo Tree Search) : elle fait pousser un arbre de coups, une simulation à la fois. Chaque simulation descend l’arbre en prenant, à chaque nœud, le coup qui maximise :
Q + c · P · √N ⁄ (1 + n)
Q est la valeur moyenne trouvée jusqu’ici sous ce coup, P l’intuition du réseau pour ce coup, N le nombre de passages par le nœud parent et n ceux par le coup. Au début, P domine : on explore d’abord ce que le réseau trouve prometteur. Plus un coup est visité, plus ce terme d’exploration fond, et c’est Q, le résultat du calcul, qui tranche.
Quand une simulation arrive sur une position encore jamais vue, elle demande au réseau sa politique et sa valeur, puis fait remonter cette valeur jusqu’à la racine en changeant de signe à chaque étage : ce qui est bon pour moi est mauvais pour vous. Le coup finalement joué est le plus visité, pas celui qui a le meilleur Q, car le nombre de visites est un vote plus stable.
Le MCTS d’origine évaluait une position en jouant la suite au hasard jusqu’au bout. Ici, la valeur du réseau remplace ces parties aléatoires. On garde quand même ce MCTS pur comme adversaire de référence, plus bas.
Apprendre en jouant contre soi
La boucle est celle d’AlphaZero, en miniature. Elle a tourné – fois :
- Le réseau du moment joue 400 parties contre lui-même, avec 200 simulations par coup. Pour varier les parties, les 20 premiers coups sont tirés au sort en proportion des visites, et un peu de bruit (Dirichlet) est ajouté aux intuitions à la racine.
- Chaque position jouée devient un exemple : l’entrée, la répartition des visites (la cible de la politique) et le résultat final de la partie, vu du joueur au trait (la cible de la valeur).
- Le réseau s’entraîne sur les exemples des 8 dernières itérations : 1 500 pas de gradient, entropie croisée pour la politique, erreur quadratique pour la valeur.
- Les nouveaux poids remplacent les anciens, et on recommence.
L’idée tient en une phrase : la recherche joue mieux que le réseau seul, donc le réseau apprend à imiter une version de lui-même qui a réfléchi. Au tour suivant, la recherche part d’une meilleure intuition et joue encore mieux. Personne ne lui dit quel coup est bon ; seuls les résultats des parties tranchent.
Les parties sont jouées par un programme Rust (règles, recherche et réseau dans le même binaire, sur 6 fils d’exécution). L’entraînement se fait en PyTorch. Au total : – sur un processeur portable.
Mesurer : l’Elo
Une génération a été gardée toutes les 5 itérations. Chacune a joué contre ses voisines et contre cinq adversaires qui n’apprennent rien :
- le hasard ;
- le glouton, qui prend le plus de graines possible tout de suite ;
- deux alpha-bêta classiques, qui calculent 4 et 8 coups à l’avance en comptant les graines, avec une table de transposition (les positions sont repérées par un hachage de Zobrist) ;
- le MCTS pur, 1 000 simulations par coup, chacune finie au hasard.
Les parties vont par paires : mêmes 4 premiers coups tirés au sort, camps inversés. L’Elo sort d’un modèle de Bradley-Terry ajusté sur tous les résultats, le hasard étant fixé à 0. Un écart de 200 points correspond à environ 76 % de score pour le plus fort.
La courbe monte vite, puis s’aplatit. Entre la génération 0 et la 15, l’Elo gagne près de 950 points : l’essentiel de l’apprentissage tient dans les 23 premières minutes de calcul. Les 85 itérations suivantes n’ajoutent qu’environ 160 points, et une partie de ce gain est dans le bruit de mesure. La génération 100 bat nettement la 20 (26 victoires, 1 nulle, 13 défaites), mais fait jeu égal avec la 90 (17, 6, 17).
Contre les adversaires fixes, la dernière génération gagne 93 parties sur 100 contre l’alpha-bêta qui calcule 8 coups à l’avance, et 97 sur 100 contre le MCTS pur, qui fait pourtant cinq fois plus de simulations qu’elle (1 000 contre 200).
Un détail instructif : la génération 0, guidée par un réseau tiré au hasard, est plus faible que le glouton (216 contre 282) et bien plus faible que le MCTS pur (721). Un réseau qui n’a rien appris guide moins bien la recherche que des parties jouées au hasard jusqu’au bout.
Pourquoi ce plateau ? Sans doute la taille de l’expérience : un réseau de 50 000 paramètres, 200 simulations par coup, des parties contre soi-même qui finissent par se ressembler. Ces pistes n’ont pas été testées ; ce sera la prochaine expérience.
Le réseau seul
Retirons la recherche : on joue directement le coup que le réseau préfère, sans rien calculer. Voici le score de ce réseau nu contre le glouton, génération après génération.
Le réseau seul passe de 15 % contre le glouton à la génération 0 à plus de 80 % dès la génération 10, puis oscille entre 69 et 89 %. Sur 40 parties, ces écarts sont surtout du bruit. Il a donc appris à jouer correctement sans calculer, mais c’est la recherche qui fait la différence face à des adversaires qui calculent.
Les générations s’affrontent
De vraies parties tirées de l’évaluation. Comparez la génération 0, qui ne voit rien venir, à la dernière.
Ce que ce n’est pas
- Ce n’est pas un champion. L’awari, une variante très proche, a été entièrement résolu en 2002 par John Romein et Henri Bal, par analyse rétrograde sur une grappe de machines : avec un jeu parfait, la partie est nulle. Wure en est loin.
- L’Elo est relatif. Il ne vaut que pour ce petit groupe de joueurs. Il ne se compare ni à l’Elo des échecs ni à un niveau humain.
- Les échantillons sont petits. 40 parties par rencontre, 100 pour la dernière génération : comptez quelques dizaines de points d’incertitude sur chaque Elo.
- La barre d’estimation n’est pas une probabilité. C’est la valeur moyenne de l’arbre, ramenée à 0–100 %.
- Une règle est de notre fait. Pour éviter les parties sans fin, tout s’arrête après 300 coups et chacun garde les graines de son côté.
- C’est un petit entraînement. Quelques heures de processeur, un petit réseau. Plus de parties et plus de simulations la rendraient sans doute plus forte.
Sous le capot
Le moteur (règles, hachage de Zobrist, recherche) est écrit en Rust et compilé deux fois : en natif pour l’entraînement, en WebAssembly (57 Ko) pour cette page. Des tests de propriétés jouent des centaines de parties au hasard et vérifient à chaque coup que les 48 graines sont toujours là, que le hachage mis à jour coup par coup égale le hachage recalculé, et que les coups proposés respectent les règles.
Le réseau est exporté en ONNX et tourne dans votre navigateur avec onnxruntime-web. Le temps que cette bibliothèque se charge (environ 3 Mo compressés), les mêmes poids sont calculés par le Rust : les deux donnent les mêmes nombres à 10−7 près, et c’est vérifié à chaque export. Rien ne part sur un serveur : la page est statique et tout se calcule chez vous.