UCT, in depth: Upper Confidence bounds applied to Trees, from UCB1 to a runnable Monte Carlo Tree Search, a hand-traced selection step, tuning, enhancements and PUCT

From bandits to trees

In a multi-armed bandit you repeatedly pick one of K arms and receive a random reward. Pick the arm with the best average and you may lock onto an arm that was lucky early; pick at random and you waste pulls on bad arms. UCB1 (Auer, Cesa-Bianchi and Fischer, 2002) resolves this with optimism: play the arm maximising

score(i) = mean_reward(i) + sqrt(2 * ln(N) / n(i))

where n(i) is how often arm i was pulled and N the total pulls. The bonus is a confidence-interval width from Hoeffding's inequality for rewards in [0, 1]. Arms pulled rarely get a large bonus and are tried again; as n(i) grows, the bonus shrinks and the average dominates. Because ln N grows slowly, every arm is still revisited occasionally, and the expected regret grows only logarithmically in N. The multi-armed bandit article covers bandits in more depth.

UCT's insight is that choosing a move at a tree node is a bandit problem whose arms are the children, and whose rewards are results of playing on from there. The twist is that the rewards are not stationary: as the subtree below a child improves its own choices, that child's average drifts. Kocsis and Szepesvári showed that UCB1 still works in this setting: with enough iterations, the probability of choosing a suboptimal move at the root goes to zero.

The four phases

Each iteration does four things. Selection starts at the root and, while the current node is fully expanded and not terminal, moves to the child with the highest UCB1 score. Expansion adds one untried child of the node where selection stopped. Simulation (the rollout) plays from the new node to the end of the game with a cheap default policy, often uniformly random moves. Backpropagation walks back to the root, incrementing each node's visit count n and adding the result to its total reward w.

The tree grows asymmetrically: promising lines are explored deeply and poor ones only enough to be confident they are poor. That is the key difference from fixed-depth minimax, which spends the same effort on every line up to its horizon.

A complete implementation

The implementation below plays a simple subtraction game: a pile of stones, each player takes 1, 2 or 3, and whoever takes the last stone wins. Theory says positions that are a multiple of 4 are lost for the player to move, so from 10 the winning move is to take 2. The one subtle point is perspective: each node stores rewards from the view of the player who made the move into it, so a parent choosing among children is always maximising its own player's win rate.

import math, random

class Nim:
    def __init__(self, stones, to_move=0):
        self.stones, self.to_move = stones, to_move
    def copy(self): return Nim(self.stones, self.to_move)
    def legal_moves(self): return [k for k in (1, 2, 3) if k <= self.stones]
    def play(self, k):
        self.stones -= k
        self.last, self.to_move = self.to_move, 1 - self.to_move
    def terminal(self): return self.stones == 0
    def reward(self, player): return 1.0 if self.last == player else 0.0

class Node:
    __slots__ = ("parent", "move", "mover", "children", "untried", "n", "w")
    def __init__(self, parent, move, mover, moves):
        self.parent, self.move, self.mover = parent, move, mover
        self.children, self.untried = [], list(moves)
        self.n, self.w = 0, 0.0
    def ucb_child(self, c):
        log_n = math.log(self.n)
        return max(self.children,
                   key=lambda ch: ch.w / ch.n + c * math.sqrt(log_n / ch.n))

def uct_search(root_state, iterations, c=math.sqrt(2)):
    root = Node(None, None, None, root_state.legal_moves())
    for _ in range(iterations):
        node, state = root, root_state.copy()
        while not node.untried and node.children:              # 1. selection
            node = node.ucb_child(c)
            state.play(node.move)
        if node.untried:                                       # 2. expansion
            move = node.untried.pop(random.randrange(len(node.untried)))
            mover = state.to_move
            state.play(move)
            child = Node(node, move, mover, state.legal_moves())
            node.children.append(child)
            node = child
        while not state.terminal():                            # 3. simulation
            state.play(random.choice(state.legal_moves()))
        while node is not None:                                # 4. backpropagation
            node.n += 1
            if node.mover is not None:
                node.w += state.reward(node.mover)
            node = node.parent
    return max(root.children, key=lambda ch: ch.n).move       # most-visited child

print(uct_search(Nim(10), 5000))   # 2

In one run with 5,000 iterations from 10 stones, the move 'take 2' received 4,840 visits with a 0.96 win rate, while 'take 1' and 'take 3' received 105 and 55. From 13 stones it chose 'take 1', and from 7 'take 3', both correct. Note what UCT never needed: no evaluation function and no knowledge of the multiple-of-4 rule.

Worked example: one selection step

Suppose the root has been visited N = 10 times, with child A at 4 wins from 6 visits, B at 1 win from 3, and C at 0 wins from 1. With c = sqrt(2), the bonus is sqrt(2 ln 10 / n): 0.876 for A, 1.239 for B and 2.146 for C. The scores are 1.543, 1.572 and 2.146, so UCT descends into C despite its zero win rate, because one visit says almost nothing. If C then loses again (0 of 2, N = 11), its score becomes 0 + sqrt(2 ln 11 / 2) = 1.549, while the larger N lifts A to 0.667 + sqrt(2 ln 11 / 6) = 1.561 and B to 0.333 + sqrt(2 ln 11 / 3) = 1.597, so B is explored next; the three are now within 0.05 of each other, and the next few results will settle it. That balance, re-checking weak moves at a slowly decreasing rate, is the whole algorithm.

The exploration constant, rewards and the final move

The constant c = sqrt(2) assumes rewards in [0, 1]. If your rewards are game scores in the hundreds, the exploration term becomes negligible and UCT turns greedy; if they are tiny, it explores almost uniformly. Normalise rewards to [0, 1] (win = 1, draw = 0.5, loss = 0, or min-max scaled scores) and then tune c empirically, typically in the range 0.5 to 1.5, by playing versions with different values against each other. Smaller c suits domains where rollouts are informative; larger c suits deceptive ones.

Choosing the move to actually play is a separate decision from selection. The common choice is the most-visited child (the 'robust child'), because visit counts are stable and a child with few visits can have an inflated average. Choosing the highest average is riskier. Stopping can be by iteration count, by wall-clock time, or early once the leading child cannot be overtaken in the remaining budget.

Enhancements that matter in practice

• Better rollouts. Random playouts are noisy and can be biased in tactical positions. Light heuristics (prefer captures, avoid immediate losses) usually help more than more iterations; very strong rollout policies can hurt by reducing diversity.
• Transpositions. In games where different move orders reach the same state, share statistics through a hash table keyed on the state, turning the tree into a directed acyclic graph. Back up carefully to avoid double counting.
• RAVE and AMAF. 'All moves as first' credits a move for results of any simulation in which it was played later, giving quick, biased estimates that are blended out as real visits accumulate. Effective in Go-like games.
• Progressive widening. With huge or continuous action spaces, allow a node only about k n^alpha children, so new actions are added as visits grow.
• Tree reuse. After a move is played, keep the subtree under it as the next root instead of starting over.
• Parallel search. Run several workers on one tree and apply a temporary 'virtual loss' to nodes a worker is exploring, so other workers spread out instead of all following the same path.

UCT versus PUCT

AlphaGo Zero and AlphaZero replaced rollouts with a neural network that outputs a value estimate and a prior P(s, a) over moves, and replaced UCB1 with a PUCT rule: pick the action maximising Q(s, a) + c_puct P(s, a) sqrt(N) / (1 + n(s, a)). Three differences matter. The prior focuses search on plausible moves, so large branching factors become manageable. The exploration term decays like 1/n rather than sqrt(ln N / n). And leaf evaluation is a network call rather than a playout. Use plain UCT when you have a fast simulator and no learned model; use PUCT when you have, or can train, a policy and value network, as in reinforcement learning pipelines.

Failure modes

• Perspective bugs. Backing up rewards from one player's view at every node makes the opponent help you. Test on a solved game, as above, before anything else.
• Unscaled rewards. Scores outside [0, 1] silently disable or dominate exploration.
• Traps. Narrow forced wins or losses a few moves deep are found slowly, because random rollouts rarely play the forcing line; Coquelin and Munos showed UCT's worst-case behaviour can be extremely poor on adversarial trees. Combine with shallow minimax checks or solver nodes that mark proven wins and losses.
• Selecting by average. Picking the best-average child can choose a move with three lucky visits.
• Unbounded memory. One node per iteration adds up in long searches; cap the tree or expand only after a node has been visited several times.
• Expensive copies. Copying a large state every iteration dominates runtime; use make and unmake moves or compact state encodings.

Trade-offs

What to do next

1. Run the code above, then confirm it finds the correct move from every pile size from 1 to 20 at a fixed iteration budget.
2. Port the Node and uct_search functions to your own game by implementing copy, legal_moves, play, terminal and reward.
3. Normalise rewards to [0, 1] and tune c by self-play between versions, recording the win rate with confidence intervals.
4. Add tree reuse and a time-based stopping rule, then profile iterations per second.
5. If tactics matter, add proven-win and proven-loss marking, or a shallow minimax check at expansion.
6. Compare against game-theoretic baselines and an alpha-beta engine at equal time, and move to PUCT only once you have a learned policy.