Licence YOLO
Retour au glossaire Ultralytics

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 :

  1. 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.
  2. Expansion : Au premier nœud où il reste un coup non essayé, ajouter ce coup comme nouvel enfant.
  3. Simulation : Jouer depuis le nouvel enfant jusqu'à la fin de la partie, classiquement avec des coups aléatoires, pour obtenir un résultat.
  4. 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.

Découvre les solutions

La vision par ordinateur dans le sport

La vision par ordinateur dans le sport

Découvre comment Ultralytics YOLO propulse la vision par ordinateur dans le sport grâce au suivi des joueurs et du ballon, aux analyses de performance, aux conseils d’entraînement et à la rééducation des athlètes.
En savoir plus
Vision par ordinateur pour les images aériennes

Vision par ordinateur pour les images aériennes

Transforme les images de drones et les images aériennes en informations exploitables en temps réel pour l’agriculture, l’aquaculture, la conservation et l’analyse géospatiale avec Ultralytics YOLO.
En savoir plus
Vision par ordinateur dans l’aérospatiale

Vision par ordinateur dans l’aérospatiale

Applique la vision par ordinateur dans l’aérospatiale avec Ultralytics YOLO pour l’inspection des aéronefs, la détection des corps étrangers sur les pistes, les opérations au sol des aéroports et la détection des défauts des matériaux composites.
En savoir plus
La vision par ordinateur dans la sécurité

La vision par ordinateur dans la sécurité

Protège chaque site avec les modèles Ultralytics YOLO. L’IA visuelle permet la surveillance des périmètres, la détection des menaces, la reconnaissance des plaques d’immatriculation et la sécurité au travail.
En savoir plus
La vision par ordinateur en robotique

La vision par ordinateur en robotique

Donne plus de capacités à tes machines grâce aux modèles Ultralytics YOLO. Dans la robotique, l’IA visuelle permet la navigation autonome, la perception, le suivi des objets et le contrôle en temps réel.
En savoir plus
La vision par ordinateur dans la logistique

La vision par ordinateur dans la logistique

Optimise la logistique avec les modèles Ultralytics YOLO. La vision par IA permet d’inspecter les colis, de les trier, de suivre les véhicules et de surveiller la sécurité des entrepôts en temps réel.
En savoir plus
La vision par ordinateur dans le commerce de détail

La vision par ordinateur dans le commerce de détail

Réinvente le commerce de détail avec les modèles Ultralytics YOLO. La vision par IA permet de suivre les stocks, de surveiller les rayons, de gérer les files d’attente et de mieux comprendre les clients.
En savoir plus
La vision par ordinateur dans le secteur de la santé

La vision par ordinateur dans le secteur de la santé

Crée des solutions de santé avec les modèles Ultralytics YOLO. La vision par IA dans le secteur de la santé accélère l’imagerie médicale, améliore les diagnostics et facilite la surveillance des patients.
En savoir plus
La vision par ordinateur dans l’industrie manufacturière

La vision par ordinateur dans l’industrie manufacturière

Optimise la fabrication avec les modèles Ultralytics YOLO. La vision par IA améliore le contrôle qualité, la détection des défauts, le respect des règles concernant les EPI et l’automatisation des chaînes de montage.
En savoir plus
La vision par ordinateur dans l’automobile

La vision par ordinateur dans l’automobile

Mets la vision par ordinateur au service de l’automobile avec les modèles Ultralytics YOLO. La vision par IA renforce la sécurité routière, l’aide à la conduite et l’automatisation des véhicules pour des routes plus intelligentes.
En savoir plus
Vision par ordinateur dans l’agriculture

Vision par ordinateur dans l’agriculture

Fais entrer l’IA de vision dans l’agriculture intelligente avec les modèles Ultralytics YOLO. Optimise le suivi des cultures et du bétail ainsi que l’agriculture de précision pour obtenir des rendements plus élevés et plus intelligents.
En savoir plus

Construisons ensemble l’avenir de l’IA !

Commence ton parcours vers l’avenir de l’apprentissage automatique