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.

–parties d’entraînement
–positions apprises
–de calcul, 6 cœurs, sans carte graphique
–paramètres dans le réseau

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.

Génération
intuition du réseau (P)part des visites

Une position de milieu de partie, Sud au trait (en bas). Avec une seule simulation, on ne voit que l’intuition. Plus on calcule, plus la recherche peut la contredire. Comparez la génération 0, dont l’intuition est presque plate, à la dernière.

Apprendre en jouant contre soi

La boucle est celle d’AlphaZero, en miniature. Elle a tourné – fois :

  1. 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.
  2. 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).
  3. 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.
  4. 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.

Elo de chaque génération jouant avec 200 simulations par coup. En pointillés, les adversaires fixes.
Dernière génération, 200 simulations par coup, 100 parties contre chaque adversaire.

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.

Score contre le glouton (40 parties) du coup préféré par le réseau, sans recherche.

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.

Jouer contre elle