Monte Carlo Tree Search : l'algorithme derrière AlphaGo

Les quatre étapes

1. Sélection

Parcourez l'arbre depuis la racine en choisissant les enfants via UCB1 :

UCB1 = win_rate + C * sqrt(ln(parent_visits) / node_visits)

C est la constante d'exploration (typiquement √2).

2. Expansion

Si le nœud n'est pas terminal, ajoutez un ou plusieurs nœuds enfants.

3. Simulation (rollout)

Jouez des coups aléatoires jusqu'à la fin de la partie. Retournez victoire/défaite/nul.

4. Rétropropagation

Mettez à jour les compteurs de victoires et de visites jusqu'à la racine.

Implémentation pour 2048

class MCTSNode:
    def __init__(self, state, parent=None, action=None):
        self.state = state
        self.parent = parent
        self.action = action
        self.children = []
        self.wins = 0
        self.visits = 0
    
    @property
    def ucb1(self):
        if self.visits == 0: return float('inf')
        return self.wins/self.visits + 1.414*np.sqrt(np.log(self.parent.visits)/self.visits)