UCT (Upper Confidence Trees)

Purpose: The selection rule that makes Monte Carlo Tree Search work. It treats every node’s children as a multi-armed bandit problem and applies the UCB1 formula (Kocsis and Szepesvári, 2006).

The Formula

At a node with $N$ visits, choose the child $i$ maximising

${\mathrm{UCT}}_i=\underset{\text{exploitation}}{\underbrace{\frac{W_i}{N_i}}}+C\underset{\text{exploration}}{\underbrace{\sqrt{\frac{\ln N}{N_i}}}}$

where $W_i$ is the total value backed up through child $i$, $N_i$ its visit count, and $C$ the exploration constant. With rewards normalised to $[0,1]$, the theoretically motivated value is $C=\sqrt{2}$; in practice it is tuned per game, typically in $[0.5,2]$.

Unvisited children have $N_i=0$ and are given infinite priority, so every child is tried at least once.

Node* bestUCT(Node* p, double C) {
    Node* best = nullptr; double bestVal = -1e18;
    double logN = log((double)p->N);
    for (Node* c : p->children) {
        double val = (c->N == 0) ? 1e18
                   : c->W / c->N + C * sqrt(logN / c->N);
        if (val > bestVal) { bestVal = val; best = c; }
    }
    return best;
}

The Bandit Connection

The multi-armed bandit problem: $k$ slot machines with unknown payout distributions; minimise regret — the gap between your total reward and always pulling the best arm.

UCB1 achieves $O(\log n)$ regret, which is optimal up to constants. The confidence term $\sqrt{\ln N/N_i}$ is a Chernoff-Hoeffding upper confidence bound on the true mean: it shrinks as an arm is sampled more, so under-sampled arms keep getting revisited, but only until the evidence is strong enough.

UCT’s contribution is the observation that a game tree is a recursive bandit problem — each node is a bandit whose arms’ payoffs are themselves determined by bandits below. Kocsis and Szepesvári proved the value estimates converge to minimax, with the probability of choosing a suboptimal move at the root decreasing to zero.

Tuning $C$

$C$	Behaviour
$C=0$	pure greedy — locks onto the first line that looks good, often badly wrong
small (0.2-0.7)	exploitative; good when rollouts are informative and the tree is deep
$\sqrt{2}\approx 1.41$	theoretical default for $[0,1]$ rewards
large (> 2)	nearly uniform search; wastes budget

Tune it empirically against a fixed opponent. It matters more than most other MCTS parameters.

Variants worth knowing

• PUCT (predictor UCT) — used by AlphaGo/AlphaZero:
  ${\mathrm{PUCT}}_i=\frac{W_i}{N_i}+c_{\text{puct}}{P}_i\frac{\sqrt{N}}{1+N_i}$
  where $P_i$ is a neural-network prior over moves. The prior replaces uniform exploration, which is most of why AlphaZero searches so few nodes.
• UCB1-Tuned — uses the empirical variance in the bound; usually stronger than plain UCB1.
• RAVE / AMAF — blends the UCT value with an “all moves as first” statistic, weighted by confidence; a large early-search speedup.
• Progressive bias — add a decaying heuristic term $H_i/(N_i+1)$ to guide early exploration.

Beyond games

The exploration-exploitation trade-off UCT formalises appears far outside game playing:

• A/B testing and online advertising — the original bandit application
• Hyperparameter search — successive halving and Hyperband are bandit algorithms
• Heuristic contest problems — UCT-style selection over neighbourhood moves is a reasonable alternative to simulated annealing
• Monte Carlo planning in MDPs and reinforcement learning

Variants / Use Cases

• Monte Carlo Tree Search — the algorithm UCT is the heart of
• Simulated Annealing — the other main randomized search for heuristic problems
• Randomized / Approximation — the branch overview
• Game Theory — the branch overview