Monte Carlo Tree Search

MCTS builds an asymmetric search tree by repeated simulation, focusing effort on the most promising moves.

The four phases

Monte Carlo Tree Search (MCTS) grows a search tree one node at a time. Each iteration runs four steps: selection, expansion, simulation (rollout), and backpropagation. Over many iterations the tree deepens toward high-value regions of the state space while leaving weak lines shallow.

Selection with UCT

From the root the algorithm descends by picking children that maximize the Upper Confidence bound for Trees (UCT): Q(s,a) + c * sqrt( ln N(s) / N(s,a) ). The first term favors moves with high average return; the second favors moves tried few times. The constant c trades exploitation against exploration.

import math

def uct(child, parent_visits, c=1.41):
    if child.n == 0:
        return float('inf')  # force at least one visit
    exploit = child.total / child.n
    explore = c * math.sqrt(math.log(parent_visits) / child.n)
    return exploit + explore

Expansion and rollout

When selection reaches a node with untried actions, one child is added. A rollout then plays to a terminal state using a fast default policy (often random). The rollout return is an unbiased but high-variance estimate of the new node's value.

Backpropagation

The rollout result is added to the visit count and value sum of every node along the path back to the root. Averages sharpen as visits accumulate, so UCT gradually concentrates simulations on the best line. After the budget is spent, the move with the highest visit count (not highest value) is usually played, because visit count is the more stable statistic.

Why it works

MCTS is anytime, requires only a generative model of the environment, and needs no handcrafted evaluation function when rollouts are used. Its asymmetric growth is what lets it scale to games such as Go where the branching factor defeats full-width search.