Monte Carlo Tree Search: The Algorithm Behind Superhuman Go

For decades, Go resisted the alpha–beta methods that conquered chess. Its branching factor is around 250, and — worse — nobody could write a good evaluation function for Go positions. The breakthrough came in 2006 with Monte Carlo Tree Search (MCTS), which estimates position values from random play-outs and focuses effort on the most promising moves. A decade later MCTS combined with deep networks produced AlphaGo.

The key idea#

Instead of evaluating a position with hand-written heuristics, play many games to the end from that position, choosing moves randomly (or with a cheap policy), and record the win rate. A position from which random play often wins is probably good. Then grow a search tree selectively — spending more simulations on promising moves.

The four phases#

Each MCTS iteration consists of:

1. Selection — starting at the root, descend the tree choosing children by a tree policy that balances exploration and exploitation, until reaching a node with unexpanded children.
2. Expansion — add one (or more) child nodes.
3. Simulation (roll-out) — play a random game from the new node to a terminal state.
4. Backpropagation — propagate the result up the path, updating visit counts $N$ and total rewards $W$ at every node.

After the time budget is exhausted, play the move at the root with the most visits (more robust than highest average).

UCT: the tree policy#

Choosing a child is a multi-armed bandit problem. The UCB1 formula, applied to trees (UCT, Kocsis & Szepesvári 2006), picks the child maximising

The first term favours children with high average reward (exploitation); the second favours rarely visited children (exploration). The constant $c$ (theoretically $\sqrt{2}$ for rewards in $[0,1]$) tunes the balance. Under UCT, the estimated values converge to the minimax values as simulations grow.

Implementation#

import math, random

class Node:
    def __init__(self, state, parent=None, move=None):
        self.state, self.parent, self.move = state, parent, move
        self.children = []
        self.untried = list(state.legal_moves())
        self.N, self.W = 0, 0.0

    def uct_child(self, c=1.4):
        return max(self.children,
                   key=lambda ch: ch.W / ch.N + c * math.sqrt(math.log(self.N) / ch.N))

def mcts(root_state, iterations=2000):
    root = Node(root_state)
    for _ in range(iterations):
        node, state = root, root_state.copy()
        # 1. Selection
        while not node.untried and node.children:
            node = node.uct_child()
            state.play(node.move)
        # 2. Expansion
        if node.untried:
            move = node.untried.pop(random.randrange(len(node.untried)))
            state.play(move)
            child = Node(state.copy(), node, move)
            node.children.append(child)
            node = child
        # 3. Simulation
        while not state.is_over():
            state.play(random.choice(state.legal_moves()))
        # 4. Backpropagation (reward from the perspective of the player who moved into node)
        while node is not None:
            node.N += 1
            node.W += state.reward_for(node.state.player_who_just_moved())
            node = node.parent
    return max(root.children, key=lambda ch: ch.N).move

The state object needs legal_moves, play, copy, is_over, reward_for and player_who_just_moved methods. Implement them for tic-tac-toe or Connect Four and you will have a strong player with no game knowledge beyond the rules.

Why MCTS is attractive#

• Anytime: stop whenever you like and return the best move so far.
• Asymmetric: the tree grows deep along promising lines and stays shallow elsewhere.
• Domain-independent: only needs a simulator of the rules — no evaluation function.
• Handles stochasticity and imperfect information with variants (e.g. Information Set MCTS).

From MCTS to AlphaZero#

Random roll-outs are noisy. AlphaGo (2016) and AlphaZero (2017) replaced them with deep neural networks:

• A policy network $p(a \mid s)$ provides priors that focus selection on plausible moves.
• A value network $v(s)$ estimates the outcome directly — AlphaZero dropped roll-outs entirely.

The selection rule becomes PUCT:

AlphaZero trains both networks from self-play, using MCTS as a policy improvement operator: the visit distribution produced by search is a better policy than the raw network, so the network is trained to imitate it. Starting from random play and given only the rules, AlphaZero reached superhuman strength in chess, shogi and Go. MuZero (2019) went further, learning a model of the rules themselves.