Monte Carlo Tree Search (MCTS)

Qu'est ce que MCTS ?

MCTS c'est un algorithme de recherche qui utilise des simulations aléatoires pour estimer quels coups valent la peine d'être explorés. Plutôt que de parcourir tout l'arbre de jeu comme Alpha-Beta, MCTS construit progressivement un arbre en jouant des parties aléatoires et en mémorisant les statistiques de chaque nœud. Plus on lui donne de temps, plus ses estimations sont précises.

C'est notamment grâce à MCTS que les programmes de jeu de Go ont fait un bond énorme, car Alpha-Beta est inutilisable sur ce jeu vu la taille de l'espace d'états.

Les 4 phases

MCTS répète les mêmes 4 étapes en boucle jusqu'à épuisement du temps de calcul :

1. Sélection

On part de la racine et on descend dans l'arbre en choisissant à chaque niveau le nœud enfant avec le meilleur score UCT :

$UCT (i) = \frac{Q _{i}}{N _{i}} + C \cdot \frac{ln N _{parent}}{N _{i}}$

On s'arrête quand on tombe sur un nœud qui n'a pas encore tous ses enfants développés, ou sur un état terminal.

2. Expansion

On ajoute un nouvel enfant au nœud sélectionné, correspondant à un coup qui n'a pas encore été exploré. C'est un état qu'on n'a jamais visité.

3. Simulation (rollout)

Depuis ce nouveau nœud, on joue une partie entièrement aléatoire jusqu'à la fin. Ça donne un résultat $z \in {- 1, 0, + 1}$ selon qu'on a perdu, fait nulle ou gagné.

4. Rétropropagation

On remonte le résultat $z$ le long du chemin du nœud feuille jusqu'à la racine, en mettant à jour les compteurs de chaque nœud traversé :

$N (s) \leftarrow N (s) + 1$ $Q (s, a) \leftarrow Q (s, a) + z$

Ces mises à jour servent à améliorer les scores UCT pour les prochaines itérations.

Comparaison avec Alpha-Beta

Critère	Alpha-Beta	MCTS
Type de recherche	Exhaustive avec élagage	Guidée par statistiques
Évaluation des états	Heuristique explicite requise	Simulations aléatoires
Scalabilité	Limitée ( $O (b^{d /2})$ )	S'améliore avec le temps de calcul
Jeux ciblés	Échecs, Dames	Go, jeux à grand espace d'états

La différence principale c'est qu'Alpha-Beta a besoin d'une bonne fonction d'évaluation pour noter les états intermédiaires. MCTS n'en a pas besoin : il estime la valeur d'un état juste en jouant des parties aléatoires depuis cet état. C'est ce qui lui permet de s'adapter à des jeux comme le Go où écrire une bonne heuristique est très difficile.

RAVE / MC-RAVE

RAVE (Rapid Action Value Estimation) est une amélioration de MCTS qui permet d'apprendre plus vite. L'idée vient de l'hypothèse AMAF (All Moves As First) : si on a joué l'action $a$ à un moment quelconque dans une simulation, on suppose que ce résultat est aussi utile pour estimer la valeur de $a$ depuis l'état courant.

Concrètement, on combine deux estimations :

$Q_{MC} (i)$ : la valeur estimée par les simulations Monte Carlo classiques (lente mais fiable),
$Q_{RAVE} (i)$ : la valeur AMAF estimée sur toutes les simulations où le coup $i$ a été joué (rapide mais biaisée).

La combinaison MC-RAVE est :

$Q_{MC-RAVE} (i) = β \cdot Q_{RAVE} (i) + (1 - β) \cdot Q_{MC} (i)$

$β$ diminue au fur et à mesure que le nœud est visité : au début on fait plus confiance à RAVE (on a peu de données MC), et progressivement on bascule vers l'estimation MC. La formule proposée dans l'article est :

$β = \frac{k}{3 N _{i} + k}$

avec $k$ un hyperparamètre qui contrôle à quelle vitesse on passe de RAVE à MC.

"The RAVE algorithm provides a rapid but biased estimate of action value; the Monte-Carlo algorithm provides a slower but unbiased estimate. MC-RAVE combines both estimates." — Gelly & Silver, Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go, Artificial Intelligence, vol. 175, n°11, 2011.

Pseudocode MCTS complet

import math
import random

class Noeud:
    def __init__(self, etat, parent=None):
        self.etat = etat
        self.parent = parent
        self.enfants = []
        self.N = 0       # nombre de visites
        self.Q = 0.0     # somme des récompenses

    def est_entierement_developpe(self, coups_legaux):
        coups_explores = [e.etat.dernier_coup for e in self.enfants]
        return all(c in coups_explores for c in coups_legaux)

    def score_uct(self, C=1.41):
        if self.N == 0:
            return float('inf')
        return self.Q / self.N + C * math.sqrt(math.log(self.parent.N) / self.N)


def mcts(etat_racine, n_iterations):
    racine = Noeud(etat_racine)

    for _ in range(n_iterations):

        # --- 1. SÉLECTION ---
        noeud = racine
        etat = etat_racine.copie()

        while not etat.est_terminal() and noeud.est_entierement_developpe(etat.coups_legaux()):
            noeud = max(noeud.enfants, key=lambda e: e.score_uct())
            etat.appliquer(noeud.etat.dernier_coup)

        # --- 2. EXPANSION ---
        if not etat.est_terminal():
            coups_explores = [e.etat.dernier_coup for e in noeud.enfants]
            coups_inexplores = [c for c in etat.coups_legaux() if c not in coups_explores]
            coup = random.choice(coups_inexplores)
            etat.appliquer(coup)
            enfant = Noeud(etat.copie(), parent=noeud)
            noeud.enfants.append(enfant)
            noeud = enfant

        # --- 3. SIMULATION (rollout) ---
        etat_sim = etat.copie()
        while not etat_sim.est_terminal():
            coup = random.choice(etat_sim.coups_legaux())
            etat_sim.appliquer(coup)
        z = etat_sim.resultat()  # +1, 0, ou -1

        # --- 4. RÉTROPROPAGATION ---
        while noeud is not None:
            noeud.N += 1
            noeud.Q += z
            noeud = noeud.parent

    # on retourne le coup le plus visité (le plus fiable statistiquement)
    meilleur = max(racine.enfants, key=lambda e: e.N)
    return meilleur.etat.dernier_coup

Référence

Sylvain Gelly, David Silver. Monte-Carlo Tree Search and Rapid Action Value Estimation in Computer Go. Artificial Intelligence, vol. 175, n°11, juillet 2011, pp. 1856–1876.

Keyboard shortcuts

SAE