MCTS : des étapes dans le développement d'un programme
Jean Méhat, université de Paris 8, 2016

Quelques programmes d'illustration qui utilisent les MCTS pour Tic Tac Toe (TTT). J'en profite pour faire une piqure de rappel sur ce qui me semble la bonne manière de développer un joueur (damier, coup, generation de coups + evaluation, le reste).

Étape 1 : représenter le damier — ttt1.c

Comme je programme en C, je définis une structure damier. Pour TTT, il suffit clairement de représenter les cases ; će n'est pas absolument nécessaire de noter qui doit jouer (on peut le retrouver en comptant les pions) mais la suite sera un peu plus simple comme ça.

Pour valider ça, une fonction qui sert à imprimer le damier. (En fait elle renvoie une chaine de caractère qui contient la description du damier : ça aussi permet en général de simplifier les affaires). Quelques tests sommaires pour vérifier que ça fonctionne.

Étape 2 : lire un damier — ttt2.c

J'écris aussi sec une fonction symétrique qui lit un damier. C'est toujours plus difficile de lire que d'écrire parce qu'on doit vérifier que les entrées sont présentes et valides. La fonction de lecture et la fonction d'écriture sont symétriques. Je peux/dois vérifier qu'avec le programme, qui lit puis qui écrit il écrit bien ce qu'il a lu : a.out < damier | a.out | cmp damier -

Étape 3 : les coups : les représenter, les lire, les écrire — ttt3.c

Je procède maintenant de la même manière pour les coups : d'abord la structure qui sert à les représenter ; la fonction qui les écrit, puis celle qui les lit.

Pour valider cette structure (et celle du damier) : les deux fonctions qui servent à appliquer un coup à un damier (jouer) et à retirer un coup d'un damier.

Pour TTT, un coup se représente simplement avec la case à marquer et la valeur avec laquelle marquer. Pour d'autres jeux, ça peut être plus compliqué. Aux Échecs, il ne suffit pas de la case de départ et de la case d'arrivée : le cas échéant, il faut aussi noter la pièce capturée pour pouvoir la remettre en place quand on déjoue. Aux Dames, il faut aussi noter la pièce capturée (sinon on ne sait pas s'il faut remettre un pion ou une dame quand on dé-joue) ; a cause des rafles, les coups sont de longueurs variables aux dames.

On peut maitenant lire des coups et les reprendre ; les conditions de test sont raisonnables.

Étape 4 : générer les coups possibles, arbitrer la partie — ttt4.c

Il ne manque que deux choses pour avoir un programme qui peut jouer : un générateur de coups et un arbitre qui reconnaisse quand la partie est terminée. Je les ajoute.

À TTT, c'est pratique d'avoir une seule fonction qui reconnait quand une partie est terminée et qui décide de qui est le gagnant. Ce n'est pas toujours le cas. À certains jeux, on détecte facilement quand la partie est terminée et plus difficilement qui est le gagnant ; c'est pratique dans ce cas d'avoir deux fonctions séparées.

Avec ces éléments, on a un joueur complet (dans la fonction main, à la fin du fichier). Il ne joue pas très bien mais (1) il permet de valider un peu plus solidement le code qu'on a écrit (c'est plus supportable de faire quelques partie contre lui que de rentrer des coups dénués de sens dans le programme précédent) (2) il pourra servir d'adversaire aux autres programmes qui jouent et par là de les valider (d'autant plus qu'il joue parfois des coups surprenants),

J'ai déja écrit plusieurs programes qui jouent à TTT alors je sais où je vais mais il ne m'a fallu que deux heures environ pour arriver à ce point : ce n'était pas compliqué.

Étape 5 : une bibliothèque et un fichier à inclure — ttt5.c tttlib.c ttt.h

Maintenant que j'ai les éléments pour construire un joueur, il est temps de nettoyer le code. Je définis un fichier à inclure et je regroupe les fonctions dans une sorte de bibliothèque. Le code est exactement le même que celui de ttt4.c, organisé en fichiers séparés.

Parce qu'il y a peu de chances que j'utilise une des fonctions sans utiliser les autres, ça n'a pas grand sens d'utiliser une vraie bibliothèque : en guise de bibliothue, je met toutes les fonctions dans un seul fichier : c'est beaucoup plus maniable à mon avis que de mettre chaque fonction dans son fichier, à la C++.

De même, je n'utilise qu'un seul fichier .h ; de ce fait, je n'ai pas besoin de réfléchir à l'ordre dans lequel je dois inclure les choses. Du coup, pas besoin non plus de se protéger contre les inclusions multiples avec un #ifndef TTT_H ...

Normalement, j'aurais fait tout ça en éditant un seul fichier. J'ai choisi de conserver les fichiers intermédiaires pour que vous puissiez suivre l'évolution du programme.

Étape 6 : un joueur parfait — ttt6.c

À TTT, c'est facile d'explorer tout l'arbre en un temps raisonnable. J'écris donc un joueur parfait qui pourra servir de joueur de référence. Ce sont les deux fonctions minAB et maxAB. Je leur fais explorer tout l'arbre du jeu et je constate que ça va vite. Mais vite jusqu'à quel point ?

Pour obtenir des temps mesurables, je répète l'exploration jusqu'à avoir un temps supérieur à une seconde (en passant le nombre d'explorations sur la ligne de commande) ; je constate alors qu'il faut quelque chose comme 8 secondes pour effectuer 10 0000 explorations ; ça fait dans les 1250 explorations par secondes ; un peu moins d'une milliseconde pour tout explorer.

Avec un jeu plus compliqué, j'aurais sans doute fait la même chose avec une fonction d'évaluation sommaire et une exploration à profondeur limitée. J'aurais aussi testé l'exploration complète d'une fin de partie (ce qui peut se faire juste en modifiant le fichier dans lequel le programme lit le damier de départ).

Étape 7 : joueur humain contre le joueur parfait — ttt7.c, ab.c

En combinant le main() du joueur aléatoire (étape 4) et l'alpha-béta de l'étape 6, on produit facilement un programme qui permet de jouer contre le joueur parfait. J'ai sorti la recherche alpha-béta du programme principal pour l'avoir dans un fichier séparé que j'ai nommé ab.c.

Étape 8 : Monte-Carlo — ttt8.c

On ajoute un joueur Monte-Carlo : pour chaque coup possible, il effectue des playouts qui commencent par ce coup puis choisit le coup pour lequel les playouts ont donné le meilleur résultat.

Sur ma machine, le joueur effectue environ 2 millions de playouts par seconde depuis la position de départ. Cela veut dire que 1600 playouts prennent autant de temps qu'une exploration complète.

Étape 9 : joueur humain contre MC — ttt9.c mc.c

J'extrais ce qui a trait à Monte-Carlo et je le met dans un fichier à part, mc.c. Je reprend le squelette du programme de jeu contre le joueur aléatoire et après quelques modifications on peut jouer contre le joueur Monte-Carlo. On controle le nombre de playouts du joueur avec un argument sur la ligne de commande.

Constater qu'avec peu de playouts, le joueur est vraiment facile à battre ; qu'avec plus de playouts, c'est vraiment difficile de le battre.

Constater qu'on n'a rien mis comme connaissance du jeu en dehors de la règle elle-même.

Étape A : MC contre AB — tttA.c

On fait jouer le joueur Monte-Carlo contre le joueur parfait fondé sur alpha-béta, en faisant varier le nombre de playouts du joueur MC. C'est ce que fait la fonction match.

Comme il s'agit d'avoir une évaluation (statistique) de la valeur du joueur MC, on joue plusieurs matchs, histoire de réduire le rôle de la chance dans le résultat final.

Puisque l'adversaire joue parfaitement, un score > à 0 indiquera un bug dans le joueur alpha-béta (il a perdu au moins une partie). Un score de 0 signifie probablement que le joueur MC a joué parfaitement lui aussi. S'il joue vraiment très mal, il perd toutes ses parties et le score sera de -200.

Avec l'entrée Arun de la makefile, je fais jouer des matchs en variant le nombre de playouts du joueur MC entre 10 et 1000. C'est le nombre de playouts joué chaque fois qu'il doit choisir un coup. Le résultat est une courbe dans le fichier A.png

Le nombre de victoires du joueur Monte-Carlo contre le joueur parfait, en fonction du nombre de playouts utilisés à chaque coup

On peut aussi regarder avec quels nombres de playouts on n'a pas eu un jeu parfait avec « grep -v ' score 0$' A.data ». Ça donne quelque chose comme

   	   ...
	   420 playouts: score -2
	   440 playouts: score -1
	   460 playouts: score -2
	   490 playouts: score -1
	   530 playouts: score -1
	   540 playouts: score -1
	   690 playouts: score -1
      
Le joueur MC perd moins de 10% de ses parties avec plus de 120 playouts. Il en perd moins de 1% avec plus de 330 playouts. Il joue parfaitement à partir de 700 playouts. [Ces nombres sont des ordres de grandeur ; avec l'aléatoire, la valeur précise peut changer d'une expérience à l'autre.]

Étape B : UCT — tttB.c ttt_uct.h uct.c

L'étape suivante est de combiner les explorations au hasard avec la construction d'un arbre : c'est UCT.

Comme il faut de nouveaux types de données (pour représenter l'arbre avec ses noeuds et ses liens emtre les noeuds), j'ai un nouveau fichier à inclure ttt_uct.h. Pour que les choses restent simples, il n'y a toujours qu'un seul fichier à inclure. Ce fichier se charge d'include ttt.h.

On commence par descendre dans la partie de l'arbre déja construite (c'est le début de la fonction descendre), en choisissant une branche (avec la fonction choisir.

Quand toutes les enfants d'un noeud ont été explorée au moins une fois, la fonction choisir fait un compromis entre l'exploitation (choisir la branche qui donne la meilleure moyenne) et l'exploration (choisir une branche qu'on ne connait pas bien) en comparant les scores UCT des branches (dans la fonction scoreUCT, au début du fichier).

Cette formule

      moyenne + C x racine carrée(log(nbre total d'essais) /
      	      	                  nombre d'essais du coup)
      
est celle de UCB1 : un résultat de théorie de la décision pour lequel on (pas moi !) prouve qu'il s'agit d'une stratégie optimale.

Le bon coté : à mesure qu'on approfondit la recherche d'un coup, le log(nombre total d'essais) augmente lentement (à cause du log) et le nombre d'essais du coup augmente linéairement pour le coup choisi. Donc la prime à l'exploration du coup diminue alors que celles des autres augmentent (lentement à cause du log). A terme, on est certain que UCT va choisir le même coup que Minimax (sauf en cas d'égalité bien sur). Cependant il faut un nombre infini d'explorations pour en être certain.

Quand la descente tombe sur un lien qui ne pointe pas sur un noeud, c'est qu'on est au bout de la partie construite de l'arbre. On rajoute un noeud et on lance un playout (avec uct_playout).

Finalement on met à jour la statistique du lien avec le résultat du playout (c'est la fin de la fonction descendre).

Ces étapes correspondent à la présentation classique des MCTS en quatre étapes :

Dans la boucle de descente, on peut appeller une fonction qui imprime le contenu de la racine après chaque descente. Pour chaque coup possible, on voit le numéro du noeud pointé, son score moyen et le nombre de tentatives. C'est du code que j'ai rajouté pour la mise au point mais il permet de suivre un peu la manière dont les choses se passent à mesure des explorations UCT. Pour le moment, le code est inactivé (par un #ifdef NOTDEF).

Pour obtenir ce programme UCT, il m'a fallu pas mal de mise au point. Notamment, je n'étais pas clair sur la façon de traiter les résultats de X et de O dans la fonction choisir. J'ai utilisé les fonctions d'impression (prnode, prtree, prnode2) pour identifier les problèmes. Ça a été intéressant de pouvoir jouer à partir d'une autre position que celle de départ, juste en changeant le contenu du fichier damier.txt : en partant d'un damier presque rempli, l'arbre est suffisamment petit pour qu'on puisse suivre l'algorithme à la main quand on a identifié un problème.

Étape C : UCT contre AB — tttC.c

Comme avec Monte-Carlo, on fait jouer le joueur UCT contre le joueur Alpha-béta en faisant varier le nombre de descentes.

Le nombre de victoires du joueur UCT contre le joueur parfait, en fonction du nombre de descentes/playouts à chaque coup.

Les résultats sous forme textuelle sont les suivants :

      $ grep -v ' score 0$' C.data 
		10 descentes: score -129
		20 descentes: score -61
		30 descentes: score -42
		40 descentes: score -19
		50 descentes: score -17
		60 descentes: score -15
		70 descentes: score -3
		80 descentes: score -4
		90 descentes: score -1
		100 descentes: score -2
		120 descentes: score -2
		130 descentes: score -2
		140 descentes: score -1
		160 descentes: score -2
		180 descentes: score -1
		200 descentes: score -2
		280 descentes: score -2
		310 descentes: score -2
		320 descentes: score -1
		410 descentes: score -1
		590 descentes: score -1
		690 descentes: score -1
		770 descentes: score -1
		800 descentes: score -1
		870 descentes: score -1
		960 descentes: score -1
      

Les résultats me semblent vraiment curieux : c'est à partir de 40 descentes que UCT perd moins de 10% de ses parties. C'est à partir de 90 descentes qu'il n'en perd que 1% au plus (une ou deux parties sur 200). Il y a donc une sérieuse amélioration par rapport à MC (pour lequel ces valeurs étaient 120 et 330). Cependant, UCT continue à jouer de façon sub-optimale jusqu'à 960 descentes alors que pour le joueur MC, ce nombre était de 700.

Je soupçonne un bug dans mon code mais comment le trouver ?

Étape D : mettre UCT au point — tttD.c uct_debug.c

Pas facile de trouver un bug quand il se produit une fois sur 200 seulement, J'ai donc écrit un programme pour répéter l'exploration jusqu'au moment où le bug se produit. À ce moment, on dumpe tout pour analyse. C'est le rôle des fichiers tttD.c et de uct_debug.c.

Un problème : le courage m'a manqué pour analyser tout ça. Je pense qu'il faut dessiner l'arbre ; on a une bonne approximation de l'historique des créations de noeuds par leur numéro. Ça devrait permettre de repérer l'anomalie qui conduit UCT à choisir le mauvais coup.

En exercice pour le lecteur ? [Il y a un dump de problème dans Ddump.txt ; il ne trouve pas le bon coup après 10 000 descentes.]

Je n'ai pas caché cette mésaventure pour plusieurs raisons :

Étape E : RAVE — tttE.c rave.c

Un problème avec UCT, c'est qu'il faut commencer par explorer tous les liens au moins une fois pour avoir des statistiques (sinon le score UCT contient une division par 0 dans les noeuds pas explorés) ; qu'il faut les avoir explorés plusieurs fois pour avoir des statisques fiables.

Il existe une méthode pour obtenir rapidement une approximation des statistiques : c'est RAVE. On suppose qu'un coup qui sera bon dans la suite de la partie sera bon aussi tout de suite : dans un playout, depuis le noeud i on joue le d'abord le coup ci puis d'autres coups tirés au hasard ci,1, ci,2 etc. jusqu'à la fin du playout. UCT utilise le résultat du playout pour qualifier seulement ci alors que RAVE va l'utiliser aussi pour qualifier tous les ci,j qui sont légaux dans le noeud i : il qualifie tous les coups légaux du noeud i qui ont été utilisé dans la suite du playout.

On se retrouve donc avec des noeuds où les coups sont qualifiés deux fois : une fois avec UCT et une fois avec RAVE. L'évaluation RAVE donne une approximation rapidement ; UCT est plus fiable au bout de quelques temps. On combine ça en faisant varier le poids des deux évaluations en fonction du nombre de mesures. Quand le nombre est faible, c'est surtout RAVE qui est utilisé ; quand il devient important, c'est surtout UCT.

Ça s'exprime usuellement avec une constante K qu'on appelle la constante d'équivalence. Elle indique quand les évaluations UCT et RAVE auront la même importance. On la combine avec N le nombre de mesures dans la formule :

	beta = sqrt(K / (3 * N + K))
      
Quand N vaut 0, beta vaut 1. À mesure que N grandit, beta devient de plus en plus petit, jusqu'à tendre vers 0. On combine le score UCT U et le score RAVE R avec (1 - beta) U + beta R
Le nombre de victoire du joueur RAVE contre le joueur parfait en fonction du nombre de playouts

Les trois courbes précédentes sur la même figure pour faciliter leur comparaison :

Le nombre de victoire des trois joueurs contre le joueur parfait en fonction du nombre de playouts
Commenter.

Ensuite il y a le programme qui joue à Othello développé sur le même modèle, dans ex2.