Recherche arborescente Monte-Carlo

L'algorithme MCTS est un algorithme qui explore l'arbre des possibles. La racine est la configuration initiale du jeu. Chaque nœud est une configuration et ses enfants sont les configurations suivantes. MCTS conserve en mémoire un arbre qui correspond aux nœuds déjà explorés de l'arbre des possibles. Une feuille de cet arbre (un nœud n'ayant pas d'enfants) est soit une configuration finale (i.e. on sait si un des joueurs a gagné, ou s'il y a match nul), soit un nœud dont aucun enfant n'a encore été exploré. Dans chaque nœud, on stocke deux nombres : le nombre de simulations gagnantes, et le nombre total de simulations. Chaque étape est composée de quatre phases[5].

• Sélection. Depuis la racine, on sélectionne successivement des enfants jusqu'à atteindre une feuille. Dans cette phase, le choix des enfants est guidé par un compromis entre exploitation (aller vers un enfant qui a été prouvé comme prometteur) et exploration (aller visiter un autre enfant, qui a l'air moins prometteur mais qui pourrait l'être davantage). Dans l'exemple donné dans la figure, on choisit la feuille de gauche (de profondeur 3).
• Expansion: si cette feuille n'est pas finale, créer un enfant (ou plusieurs) en utilisant les règles du jeu et choisir l'un des enfants. Sur l'exemple, on ajoute cet enfant, marqué 0/0.
• Simulation: simuler une exécution d'une partie au hasard depuis cet enfant, jusqu'à atteindre une configuration finale.
• Rétropropagation (Backpropagation): utiliser le résultat de la partie au hasard et mettre à jour les informations sur la branche en partant du nœud enfant vers la racine. Sur l'exemple, la partie était perdante pour blanc. On incrémente donc uniquement le nombre de simulations totales sur la branche pour les nœuds blancs et on incrémente le nombre de simulations gagnées et le nombre de simulations totales pour les noirs sur la branche : 0/0 devient 0/1, 3/3 devient 4/4, 5/6 devient 5/7, 7/10 devient 8/11, et 12/21 devient 12/22. Si la partie avait été gagnante :0/0 serait devenu 1/1, 3/3 serait devenu 3/4, 5/6 serait devenu 6/7, 7/10 serait devenu 7/11, et 12/21 serait devenu 13/22.

Étapes d'un MCTS.

La difficulté principale est dans la phase de sélection. Il faut choisir un enfant et maintenir un compromis entre l'exploitation des choix qui ont l'air prometteurs et l'exploration des nœuds à partir desquels peu de simulations ont été réalisées. La première formule pour ce compromis entre exploitation et exploration, qui s'appelle UCT (Upper Confidence Bound 1 applied to Trees) était introduit par Levente Kocsis (en) et Csaba Szepesvári (en)[6]. UCT est basée sur la formule UCB1 de Auer, Cesa-Bianchi et Fischer[7] et l'algorithme AMS (Adaptive Multi-stage Sampling) a été appliqué à la décision multi-étage par Chang, Fu, Hu, et Marcus[8]. Kocsis et Szepesvári recommandent de choisir le successeur i, en chaque nœud de l'arbre, pour lequel l'expression ${\displaystyle {\frac {w}{n}}+c{\sqrt {\frac {\ln N}{n}}}}$ a la valeur maximale. Dans cette formule :

• w est le nombre de parties gagnées marqué dans le successeur i
• n est le nombre de fois où le successeur i a été visité
• N est le nombre de fois où le nœud, père de i, a été visité
• c est le paramètre d'exploration — en théorie égal à ${\displaystyle {\sqrt {2}}}$, en pratique, choisi expérimentalement.

La première partie de la formule, ${\displaystyle {\frac {w}{n}}}$ correspond à l'exploitation ; la fraction est grande pour les successeurs qui ont eu beaucoup de succès jusque là. La seconde partie correspond à l'exploration ; elle est grande pour des successeurs qui n'ont été impliqués que dans peu de simulations.

Les implémentations plus modernes de MCTS sont basées sur une variante de UCT, cf. les travaux de Chang et al.[8] - [9] (2005) à Operations Research (en).

• Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton, « A Survey of Monte Carlo Tree Search Methods », IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, n^o 1,‎ mars 2012 (lire en ligne)

• Rémi Coulom, « Le jeu de go et la révolution de Monte Carlo », 28 avril 2009