License YOLO
Back to Ultralytics Glossary

Monte Carlo Tree Search (MCTS)

Monte Carlo Tree Search (MCTS) picks actions by growing a search tree from simulated playouts, focusing on promising moves. Used in AlphaGo and robots.

Monte Carlo tree search (MCTS) is a planning algorithm that chooses the next action by growing a tree of possible futures from many simulated playouts, spending more of its budget on the moves that look most promising. It needs only a way to generate legal moves and outcomes, such as a game's rules or a simulator, and no hand-written evaluation function. It is also an anytime algorithm: stopping at any point returns the best move found so far, and more time gives a better answer. Rémi Coulom named the method in 2006, the same year Levente Kocsis and Csaba Szepesvári published UCT, the selection rule that became the method's standard form. MCTS transformed computer Go within a few years, later powered AlphaGo and AlphaZero, and is now used to plan robot and vehicle behavior and to search over reasoning steps in large language models (LLMs).

How MCTS Works#

The search keeps a tree whose root is the current position and whose nodes store how often they were visited and how often those visits led to a win. Each iteration has four phases:

  1. Selection: Starting at the root, descend through fully explored nodes by picking the child with the highest UCT score, which balances high win rates against rarely tried moves.
  2. Expansion: At the first node with an untried move, add that move as a new child.
  3. Simulation: Play out from the new child to the end of the game, classically with random moves, to get a result.
  4. Backpropagation: Walk back up the path and update every node's visit count and win total with the result.

When the budget runs out, the algorithm plays the root's most visited child, which is a steadier choice than the one with the highest average.

Balancing Exploration and Exploitation#

UCT treats the choice at each node as a multi-armed bandit and applies the UCB1 formula: a child's score is its win rate w/n plus c·√(ln N / n), where n is the child's visit count, N is its parent's, and c is an exploration constant, √2 in theory and tuned in practice. The second term shrinks as a move is tried more often, so a move with a few lucky wins cannot crowd out the rest and a neglected move eventually gets another look.

This Python example runs MCTS on a small game: players take one to three stones from a pile of 10, and whoever takes the last stone wins.

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}")

Taking two stones receives 1,889 of the 2,000 visits and wins 91% of its simulations, against 68 visits for taking one and 43 for taking three. It is the winning move: leaving 8, a multiple of 4, lets the first player answer every reply by restoring a multiple of 4 until the pile is empty. The search found it from random playouts and visit statistics alone, with no strategy coded in.

From AlphaGo to AlphaZero and MuZero#

Go's average branching factor of about 250 legal moves, against roughly 35 in chess, put it beyond exhaustive search, and MCTS drove the jump in computer Go strength from the late 2000s onward. DeepMind's AlphaGo guided MCTS with a policy network that proposed likely moves and evaluated positions with both a value network and fast rollouts, and in March 2016 it beat Lee Sedol 4–1. AlphaZero and MuZero went further. AlphaZero dropped rollouts entirely, scored leaf positions with a value network, and trained that network on games it played against itself, using the visit counts from each search as the target for its policy network, which makes MCTS a policy improvement step inside reinforcement learning. MuZero ran the same search inside a learned model of the environment, so it played Go, chess, shogi, and Atari games without being given their rules.

MCTS for Planning and Reasoning#

Robots and autonomous vehicles use MCTS to plan through uncertain situations such as merging into traffic, and variants like POMCP extend it to partially observable Markov decision processes by tracking a belief over hidden states. A search that plans from camera input needs a state for its root: a chess-playing robot arm, for example, can use an Ultralytics YOLO26 model trained on board images to locate every piece, and the recovered position becomes the root of the search.

In LLM reasoning, each node is a partial solution and each edge a reasoning step, with a process reward model or an answer check scoring the branches. Microsoft's rStar-Math used MCTS with a process preference model to raise Qwen2.5-Math-7B from 58.8% to 90.0% on the MATH benchmark. Tree of Thoughts searches over reasoning steps with breadth-first or depth-first search instead. MCTS has been harder to use during training: DeepSeek listed it among its unsuccessful attempts for DeepSeek-R1, because the space of token sequences is far larger than a board game's and the value model that guides the search is hard to train, and trained R1 with reinforcement learning with verifiable rewards instead.

Explore solutions

Computer vision in sports

Computer vision in sports

Discover how Ultralytics YOLO powers sports vision with player and ball tracking, performance analytics, coaching insights, and athlete rehabilitation.
Learn more
Computer vision for aerial imagery

Computer vision for aerial imagery

Turn drone and aerial imagery into real-time insights for agriculture, aquaculture, conservation, and geospatial analysis with Ultralytics YOLO.
Learn more
Computer vision in aerospace

Computer vision in aerospace

Apply computer vision in aerospace with Ultralytics YOLO for aircraft inspection, runway FOD detection, airport ground operations, and composite defect detection.
Learn more
Computer vision in security

Computer vision in security

Protect every site with Ultralytics YOLO models. Vision AI powers perimeter monitoring, threat detection, license-plate recognition, and workplace safety.
Learn more
Computer vision in robotics

Computer vision in robotics

Power smarter machines with Ultralytics YOLO models. Vision AI in robotics drives autonomous navigation, perception, object tracking, and real-time control.
Learn more
Computer vision in logistics

Computer vision in logistics

Streamline logistics with Ultralytics YOLO models. Vision AI enables package inspection, sorting, vehicle tracking, and real-time warehouse safety monitoring.
Learn more
Computer vision in retail

Computer vision in retail

Reimagine retail with Ultralytics YOLO models. Vision AI powers inventory tracking, shelf monitoring, queue management, and smarter customer insights.
Learn more
Computer vision in healthcare

Computer vision in healthcare

Build healthcare solutions with Ultralytics YOLO models. Vision AI in healthcare powers faster medical imaging, smarter diagnostics, and patient monitoring.
Learn more
Computer vision in manufacturing

Computer vision in manufacturing

Optimize manufacturing with Ultralytics YOLO models. Vision AI drives quality control, defect detection, PPE compliance, and assembly line automation.
Learn more
Computer vision in automotive

Computer vision in automotive

Apply computer vision in automotive with Ultralytics YOLO models. Vision AI elevates road safety, driver assistance, and vehicle automation for smarter roads.
Learn more
Computer vision in agriculture

Computer vision in agriculture

Bring vision AI to smart agriculture with Ultralytics YOLO models. Power crop monitoring, livestock tracking, and precision farming for higher, smarter yields.
Learn more

Let's build the future of AI together!

Begin your journey with the future of machine learning