Monte Carlo Tree Search: Search a Game Tree You Can Never Fully Build

Search without a full tree

Chess has roughly 10^120 possible games and Go has more legal positions than atoms in the observable universe, so no computer can ever expand a full game tree for either. Monte Carlo Tree Search (MCTS) sidesteps the problem: instead of exhaustively expanding every branch, it builds a small, lopsided tree that grows fastest where the game actually seems to matter, guided by randomised playouts rather than a hand-tuned evaluation function.

The algorithm repeats four phases, over and over, for as long as you can afford to think: selection, expansion, simulation (also called rollout), and backpropagation. Each repetition is one visit; after thousands of visits the tree's shape itself is the answer — the child of the root with the most visits is the recommended move, because visit count correlates with a move having survived scrutiny, not with a single lucky rollout.

Selection: the UCB1 formula

Starting at the root, the algorithm walks down the existing tree by always picking the child that maximises the UCB1 (Upper Confidence Bound) score, until it reaches a node that is not yet fully expanded:

UCB1(node) = winRate(node) + C * sqrt( ln(parentVisits) / nodeVisits )
             \_____ exploitation ____/   \______ exploration ______/

The first term rewards moves that have won often so far — exploitation. The second term grows for any child that has been visited rarely relative to its parent — exploration — and it grows without bound as a node is neglected, guaranteeing every child eventually gets revisited even after a string of bad rollouts. The constant C (root two in the original formulation) sets the balance; a larger C searches wider, a smaller C dives deeper into promising lines faster.

Expansion, simulation, backpropagation

When selection reaches a node with untried moves, one of them is added to the tree as a new child — expansion. From that brand-new node the algorithm then plays a rollout: moves chosen at random (or by a cheap heuristic policy) all the way to a terminal state, win, loss or draw. The result of that one random game is the only piece of new information this iteration contributes.

That result is then propagated back up every node visited on the way down — backpropagation — incrementing each node's visit count and win total. A single rollout is nearly meaningless noise, but the point of UCB1 is that thousands of noisy rollouts, weighted by how much attention each move has already received, converge on a visit distribution that tracks the true value of each move far better than any individual playout did.

function mctsIteration(root):
  node = root
  while node.fullyExpanded and node.children.length > 0:
    node = argmax(node.children, ucb1)          // selection
  if not node.isTerminal:
    node = expand(node)                          // expansion: add one child
  result = randomRollout(node.state)              // simulation
  while node !== null:
    node.visits += 1
    node.wins += result belongs to node's player ? 1 : 0
    node = node.parent                            // backpropagation

Why random rollouts work at all

It looks reckless to judge a position by playing it out with random moves, but random rollouts are an unbiased, if noisy, estimator of a position's value, and MCTS only needs relative ordering between sibling moves, not an accurate absolute score. Average enough independent noisy samples and the law of large numbers does the rest. This is exactly why MCTS made computer Go competitive years before deep learning arrived — the game's branching factor defeated classical alpha-beta search with a hand-built evaluation function, but a tree that adaptively spends its rollouts where they matter most did not need one.

Modern engines improve the rollout with a learned policy and value network instead of uniform randomness — this is the core idea behind AlphaGo and AlphaZero: a neural network proposes which moves are worth expanding and estimates a position's value directly, so far fewer random playouts are needed, and MCTS becomes the search scaffold around a learned intuition rather than a substitute for one.

Where MCTS shines and where it does not

MCTS needs almost nothing about the domain beyond legal moves and a win/loss signal — no hand-crafted evaluation function, no domain-specific heuristics required to get a reasonable player running. That generality is why it spread from Go into general game playing, real-time strategy AI, puzzle solvers and even non-game planning problems. It struggles on games with very long, very deep tactical sequences where a single random misstep in a rollout misjudges an entire line, and it needs a way to prevent the tree from growing without bound in memory, usually by capping total nodes or expiring the least-visited branches.

Frequently asked questions

Try it live

Everything above runs in your browser — open Monte Carlo Tree Search and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.