Home/Game AI/Monte Carlo tree search
Search algorithmsCTRL K

Monte Carlo tree search

· select, expand, simulate, back up
/gameai/monte-carlo-tree-search
ITERATION
0/ 12
one playout each
PHASE
—
of the four
REWARD
—
of the last playout, 0–1
ROOT VISITS
0
playouts so far
BEST MOVE
—
the most visited child
selected pathcurrentrollout ended herenever expanded
b = 3 · depth 3 · 12 iterations · seed 7 · 50 steps
step 0 / 49
Iterations12
mcts.ts
1
function mcts(root: Node, iterations: number) {
2
  for (let i = 0; i < iterations; i++) {
3
    let node = root;
4
    while (node.isExpanded && !node.isLeaf) node = selectChild(node); // UCB1: mean + c · sqrt(ln(parentVisits) / visits)
5
    if (!node.isLeaf) {
6
      node = node.expandOneChild();
7
    }
8
    const reward = rollout(node); // random moves to the end of the game
9
    for (let current: Node | null = node; current; current = current.parent) {
10
      current.visits++; current.total += reward;
11
    }
12
  }
13
  return root.children.reduce((a, b) => (b.visits > a.visits ? b : a)); // the most visited move
14
}
CURRENT STEP
line 1

An unknown game tree of depth 3: MCTS never scores every leaf, it samples. Rewards are the leaf scores scaled to 0–1 for MAX.

// how it works

Understanding Monte Carlo tree search

MCTS · random playouts decide where the tree grows
01

The idea

Monte Carlo tree search never looks at the whole tree and never needs an evaluation function. Each iteration selects a path from the root by a bandit rule, UCB1, that balances the children's average reward against how rarely they were tried; expands one new node at the end of the path; plays random moves from there to the end of the game; and backs the result up along the path, updating visit counts and mean rewards.

Promising moves are visited more and so searched deeper, bad ones are abandoned after a few playouts, and the estimates sharpen with every iteration. The move to play is the most visited child of the root. With a learned policy to guide selection and a value network instead of random playouts, this is the search inside AlphaGo.

02

The four stages

1
selectdown the tree by UCB1
2
expandadd one untried child
3
simulaterandom moves to the end of the game
4
back upvisits + 1, reward added, all the way to the root
03

Complexity

best
O(k · d)k playouts of d moves each
average
O(k · d)anytime: stop whenever, answer ready
worst
O(k · d)converges to minimax as k → ∞
space
O(k)one node per expansion
04

Versus its siblings

NODES EVALUATED · b = 3, d = 3, 12 PLAYOUTS
mcts, 12 playouts
12
minimax
27
alpha-beta
15
mcts, 100 playouts
27
leaves reached · MCTS trades exactness for an answer at any budget
05

Pseudocode

MCTS(root, iterations)
  repeat iterations times
    select: from the root, follow the child with the best UCB1 until a node with an untried child or a leaf
    expand: add one untried child of that node
    simulate: play random moves from it to the end; reward ← the result
    back up: for every node on the path, visits += 1, total += reward
  return the most visited child of the root
06

When to use

Games too wide or too hard to evaluate for minimax: go, Hex, general game playing, real-time strategy.
Planning under uncertainty with a simulator but no model: robotics, scheduling, and combined with neural networks, AlphaZero-style engines.
07

Pitfalls

The exploration constant matters: too low and the search tunnels, too high and it never commits.
Random playouts are weak in tactical games; a trap one move away can be missed for hundreds of iterations.
Pick the most visited child, not the highest mean: a high mean with few visits is noise.
08

History

Rémi Coulom named Monte Carlo tree search in 2006 for his go program Crazy Stone, and Levente Kocsis and Csaba Szepesvári gave the UCT selection rule the same year. It lifted computer go from amateur to strong-amateur level within a decade, and with deep networks became AlphaGo in 2016.

Back to Game AI