94
descente de l'arbre
Recherche arborescente Monte-Carlo
partie aleatoire
mise ajour
des noeuds
de l'arbre
FIGURE 5.1 - Les différentes étapes de l ' algorithme UCT.
La quatrième étape est de remonter dans l ' arbre le résultat de la partie aléatoire.
L' algorithme 3 donne un implémentati on possible d' UCT.
Exercice : É crire une classe Noeud qui permet de faire des parties aléatoires commençant par un descente de 1' arbre UCT. Puis écrire un algorithme qui choisit un coup au Go
en utilisant UCT.
5.6 UCT avec transpositions
Au Go, ainsi que dans de nombreux autres jeux, les transpositions sont fréquentes. II
est utile de les détecter pour améliorer le niveau de 1 ' algorithme.
Exercice : Ajouter la reconnaissance des transpositions à l ' algorithme UCT.
5.7 RAVE
II existe une heuristique qui permet de disposer d'une estimation rapide de la valeur
des coups lorsque peu de simulations ont été effectuées à un noeud. On effectue pour
cela à chaque noeud de nouvelles statistiques sur chaque coup possible. On mettra à jour
la valeur moyenne RAVE d' un coup avec le résultat d' une partie aléatoire quand cette