Monte Carlo Tree Search (MCTS)
La recherche arborescente Monte-Carlo (MCTS) choisit des actions en développant un arbre de recherche à partir de simulations, en privilégiant les coups prometteurs. Elle est utilisée dans AlphaGo et en robotique.
La recherche arborescente Monte-Carlo (MCTS) est un algorithme de planification qui choisit l'action suivante en développant un arbre de futurs possibles à partir de nombreuses simulations, et consacre davantage de son budget aux coups les plus prometteurs. Il nécessite seulement un moyen de générer des coups et des résultats valides, comme les règles d'un jeu ou un simulateur, sans fonction d'évaluation écrite à la main. C'est aussi un algorithme anytime : quel que soit le moment où on l'arrête, il renvoie le meilleur coup trouvé jusque-là, et davantage de temps améliore la réponse. Rémi Coulom a nommé la méthode en 2006, année où Levente Kocsis et Csaba Szepesvári ont publié UCT, la règle de sélection devenue sa forme standard. En quelques années, MCTS a transformé le jeu de Go sur ordinateur, avant d'alimenter AlphaGo et AlphaZero ; il sert aujourd'hui à planifier le comportement de robots et de véhicules ainsi qu'à explorer des étapes de raisonnement dans les grands modèles de langage (LLMs).
Fonctionnement de MCTS#
La recherche conserve un arbre dont la racine correspond à la position actuelle et dont les nœuds enregistrent le nombre de visites et le nombre de visites ayant abouti à une victoire. Chaque itération comporte quatre phases :
- Sélection : En partant de la racine, descendre dans les nœuds entièrement explorés en choisissant l'enfant ayant le meilleur score UCT, qui équilibre les taux de victoire élevés et les coups rarement essayés.
- Expansion : Au premier nœud où il reste un coup non essayé, ajouter ce coup comme nouvel enfant.
- Simulation : Jouer depuis le nouvel enfant jusqu'à la fin de la partie, classiquement avec des coups aléatoires, pour obtenir un résultat.
- Rétropropagation : Remonter le chemin et mettre à jour le nombre de visites et le total de victoires de chaque nœud à partir du résultat.
À l'épuisement du budget, l'algorithme joue le fils de la racine le plus visité, un choix plus stable que celui ayant la meilleure moyenne.
Équilibrer exploration et exploitation#
UCT traite le choix à chaque nœud comme un bandit multi-bras et applique la formule UCB1 : le score d'un enfant est son taux de victoire w/n plus c·√(ln N / n), où n est son nombre de visites, N celui de son parent et c une constante d'exploration, égale théoriquement à √2 et ajustée en pratique. Le second terme diminue à mesure qu'un coup est essayé, empêchant ainsi quelques victoires chanceuses d'éclipser les autres coups et garantissant qu'un coup délaissé sera réexaminé.
Cet exemple Python exécute MCTS sur un petit jeu : les joueurs prennent entre une et trois pierres dans un tas de 10, et celui qui prend la dernière pierre gagne.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")Prendre deux pierres reçoit 1 889 des 2 000 visites et remporte 91 % de ses simulations, contre 68 visites pour en prendre une et 43 pour en prendre trois. C'est le coup gagnant : laisser 8, un multiple de 4, permet au premier joueur de répondre à chaque coup en rétablissant un multiple de 4 jusqu'à ce que le tas soit vide. La recherche l'a trouvé uniquement grâce à des simulations aléatoires et aux statistiques de visites, sans stratégie codée.
D'AlphaGo à AlphaZero et MuZero#
Le facteur de branchement moyen du Go, d'environ 250 coups légaux contre quelque 35 aux échecs, le rendait inaccessible à une recherche exhaustive ; MCTS a entraîné l'essor du niveau du Go sur ordinateur à partir de la fin des années 2000. AlphaGo de DeepMind guidait MCTS avec un réseau de politique proposant des coups probables et évaluait les positions à l'aide d'un réseau de valeur et de simulations rapides. En mars 2016, il a battu Lee Sedol 4 à 1. AlphaZero et MuZero sont allés plus loin. AlphaZero a complètement abandonné les simulations, évalué les positions feuilles à l'aide d'un réseau de valeur et entraîné ce réseau sur des parties jouées contre lui-même ; il a utilisé les nombres de visites issus de chaque recherche comme cible pour son réseau de politique, faisant de MCTS une étape d'amélioration de la politique dans l'apprentissage par renforcement. MuZero a exécuté la même recherche dans un modèle appris de l'environnement, ce qui lui a permis de jouer au Go, aux échecs, au shogi et à des jeux Atari sans connaître leurs règles.
MCTS pour la planification et le raisonnement#
Les robots et les véhicules autonomes utilisent MCTS pour planifier leurs actions dans des situations incertaines, comme une insertion dans la circulation. Des variantes comme POMCP l'étendent aux processus décisionnels de Markov partiellement observables en suivant une distribution de croyance sur les états cachés. Une recherche qui planifie à partir d'images de caméra a besoin d'un état à sa racine : par exemple, un bras robotisé jouant aux échecs peut utiliser un modèle Ultralytics YOLO26 entraîné sur des images de plateau pour localiser chaque pièce, puis utiliser la position reconstituée comme racine de la recherche.
Dans le raisonnement des LLM, chaque nœud représente une solution partielle et chaque arête une étape de raisonnement. Un modèle de récompense du processus ou une vérification de réponse attribue un score aux branches. Le rStar-Math de Microsoft a utilisé MCTS avec un modèle de préférence du processus pour faire passer Qwen2.5-Math-7B de 58,8 % à 90,0 % au benchmark MATH. Tree of Thoughts explore plutôt les étapes de raisonnement avec une recherche en largeur ou en profondeur. MCTS s’est avéré plus difficile à utiliser pendant l’entraînement : DeepSeek l’a cité parmi les essais infructueux pour DeepSeek-R1, car l’espace des séquences de jetons est bien plus vaste que celui d’un jeu de plateau et le modèle de valeur qui guide la recherche est difficile à entraîner. DeepSeek-R1 a plutôt été entraîné par apprentissage par renforcement avec récompenses vérifiables.










