Monte Carlo Tree Search

Purpose: Choose good moves in a game without any evaluation function, by running many random playouts and building a search tree biased toward promising lines. The algorithm behind AlphaGo, and the standard tool for games where writing a heuristic evaluator is hopeless.

The Four Steps

Each iteration walks the tree once:

1. Selection. From the root, repeatedly pick a child using a tree policy — usually UCT — until reaching a node that is not fully expanded.
2. Expansion. Add one new child for an untried move.
3. Simulation (rollout). Play out the game to a terminal state with a fast default policy (uniformly random in the basic version).
4. Backpropagation. Walk back to the root, incrementing each node’s visit count $N$ and adding the result to its value sum $W$.

After the time budget expires, play the move with the most visits (more robust than the highest average).

Code skeleton

struct Node {
    Node* parent = nullptr;
    vector<Node*> children;
    vector<Move> untried;
    double W = 0;      // total value from this node's perspective
    int    N = 0;      // visit count
    Move   move;
};
 
void mcts(Node* root, State s0, int iterations) {
    for (int it = 0; it < iterations; it++) {
        Node* node = root; State s = s0;
 
        while (node->untried.empty() && !node->children.empty()) {   // select
            node = bestUCT(node);
            s.apply(node->move);
        }
        if (!node->untried.empty()) {                                // expand
            Move m = pick(node->untried);
            s.apply(m);
            node = node->addChild(m);
        }
        double result = rollout(s);                                  // simulate
        while (node) {                                               // backprop
            node->N++;
            node->W += result;
            result = 1 - result;      // flip for the opponent
            node = node->parent;
        }
    }
}

Why it works

MCTS is anytime (stop whenever, you always have an answer), aheuristic (needs only the rules and a terminal score), and asymmetric (it deepens promising lines and ignores bad ones, unlike the uniform depth of minimax).

Given infinite iterations and UCT selection, the value estimates converge to the minimax values. In practice the value comes from the asymmetry: it spends its budget where the game is actually decided.

MCTS vs Minimax

	Minimax + α-β	MCTS
Needs an evaluation function	yes — this is the hard part	no
Search shape	uniform depth	asymmetric, selective
Anytime	no (needs a full ply)	yes
Best for	chess, checkers — good evaluators exist	Go, Hex, general game playing
Branching factor tolerance	poor at $b>50$	good
Tactical sharpness	excellent	can miss narrow forced lines

Improvements that matter

• UCT — the standard selection formula; MCTS without it is much weaker
• RAVE / AMAF — share statistics between moves that appear anywhere in a playout; huge early-game speedup in Go
• Domain-specific rollout policies — replacing uniform random with even a weak heuristic policy improves strength dramatically
• Neural guidance (AlphaZero) — replace rollouts with a learned value network and bias selection with a learned policy prior. This is the change that made MCTS superhuman at Go.
• Progressive widening — for large or continuous action spaces, expand children gradually as $N$ grows
• Tree reuse — keep the subtree corresponding to the move actually played

Variants / Use Cases

• UCT — the selection rule
• Minimax and Alpha-Beta — the classical alternative
• Optimisation contests — MCTS is a strong general search for heuristic (“marathon”) problems, alongside simulated annealing
• Game Theory — the branch overview