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.
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.
Les générations s’affrontent
De vraies parties tirées de l’évaluation. Regardez la génération 0 donner des graines sans compter, puis la dernière préparer ses prises plusieurs coups à l’avance.
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.