AlphaGo and AlphaZero

AlphaGo and AlphaZero are built on a policy/value network $f_\theta(s) = (p, v)$ that maps a board state $s$ to a probability distribution $p$ over legal moves (the policy) and a scalar $v \in [-1, 1]$ estimating the expected outcome for the current player (the value). This single network replaces two separate estimators used in classical game-playing systems: a move generator and a static evaluation function. Because Go and chess have far too many states to tabulate, the network is a deep convolutional (AlphaGo) or residual (AlphaZero) architecture that generalizes across positions it has never seen exactly. The second ingredient is Monte-Carlo Tree Search used as policy improvement. Classical MCTS estimates the value of moves by running many random rollouts to game end and averaging outcomes — this is Planning and Monte-Carlo Tree Search in its vanilla form. AlphaGo/AlphaZero instead use the network's value $v$ in place of random rollouts (AlphaGo blends both; AlphaZero uses only the network) and use the network's policy $p$ to bias which branches get explored, via a PUCT (Predictor + Upper Confidence bound applied to Trees) formula. The tree search, run for a fixed simulation budget from the current position, produces a refined visit-count distribution $\pi$ over moves that is demonstrably better than the raw network policy $p$ — this refinement is the mechanism that drives learning. The third ingredient is self-play reinforcement learning. The network plays complete games against itself, at each move running MCTS to produce the improved policy $\pi$ and eventually observing a game outcome $z \in \{-1, 0, +1\}$. These $(s, \pi, z)$ triples become training data: the network is updated to make its raw policy $p$ match the search-improved $\pi$, and its value $v$ match the actual outcome $z$. Because $\pi$ is a better policy than $p$, training the network toward $\pi$ improves the network, which in turn makes future MCTS searches even stronger — a policy iteration loop, related in spirit to Deep Policy Gradient Methods but distinguished by using search rather than gradient ascent on return as the improvement operator.

Network architecture. AlphaGo used two separate deep convolutional networks (SL/RL policy networks and a value network), each trained on stacks of feature planes encoding the board (stone positions, liberties, ko status, move history). AlphaZero unified these into a single network with a shared "trunk" of residual blocks and two output "heads": a policy head producing a distribution over moves, and a value head producing a scalar. Sharing the trunk means the network learns representations useful for both tasks jointly, and halves the parameter count and inference cost relative to two separate networks.

MCTS with network guidance. Each simulation traverses the tree from the root using a selection rule that balances exploitation of high-value moves against exploration of moves the policy network favors but that have not been tried often:

Here $Q(s,a)$ is the mean value backed up from simulations through that edge, $P(s,a)$ is the network's prior probability for move $a$ (encouraging exploration proportional to how promising the policy thinks the move is), and $N(s,a)$ is the visit count (the bonus term shrinks as a move is tried more, forcing exploration of under-visited alternatives). This is a variant of the standard Planning and Monte-Carlo Tree Search UCB1 formula adapted to incorporate a learned prior — hence "PUCT." When a simulation reaches a leaf (a state not yet expanded), the network evaluates it once: $p, v = f_\theta(s_{\text{leaf}})$. The leaf is expanded with children priors $P(s,\cdot) = p$, and the value $v$ is backed up along the path traversed, updating $Q$ and $N$ for every edge visited. No random rollout to the end of the game is performed in AlphaZero — the value network's estimate substitutes for it entirely, which is the key departure from vanilla Monte-Carlo Tree Search. After a fixed number of simulations (e.g. 800 in AlphaZero's self-play), the root's visit counts define the improved policy:

with temperature $\tau$ controlling exploration (high early in a game for training diversity, near zero for competitive play).

Self-play training loop. The network plays against itself using $\pi$ to select moves (sampled, not argmax, especially early in training), storing $(s_t, \pi_t)$ at every move. At the game's end the outcome $z$ (from the perspective of the player to move at each $s_t$) is recorded for every stored state. A replay buffer of recent self-play games supplies minibatches to a stochastic gradient descent step minimizing:

The first term drives the value head toward the game outcome (a regression loss), the second is a cross-entropy loss driving the policy head toward the search-improved distribution, and the last is L2 regularization. Crucially, both signals come from the same self-play games — there is no separate labeled dataset (in AlphaZero; AlphaGo's first stage used human game records to bootstrap the policy network before self-play took over). ```text function ALPHAZERO_TRAIN(iterations, games_per_iter, sims_per_move): theta ← random initialization replay_buffer ← empty for i in 1..iterations:

# --- Self-play phase --- for g in 1..games_per_iter: s ← initial_state history ← [] while not TERMINAL(s): pi ← MCTS_SEARCH(s, theta, sims_per_move) history.append((s, pi)) a ← SAMPLE(pi) # temperature-controlled s ← APPLY(s, a) z ← OUTCOME(s) # +1 win / -1 loss / 0 draw for (s_t, pi_t) in history: z_t ← z if PLAYER(s_t) == winner else -z replay_buffer.add(s_t, pi_t, z_t)

# --- Training phase --- for step in 1..training_steps: batch ← SAMPLE_MINIBATCH(replay_buffer) loss ← 0 for (s, pi, z) in batch: p, v ← NETWORK(s, theta) loss += (z - v)^2 - dot(pi, log(p)) + c L2(theta) theta ← theta - lr GRADIENT(loss, theta)

# --- Evaluation (AlphaGo Zero variant) --- if EVALUATE(theta_new) beats theta_current by margin: theta_current ← theta_new # else keep old network return theta_current

function MCTS_SEARCH(s_root, theta, num_simulations): tree ← {s_root: new node} for i in 1..num_simulations: s ← s_root path ← [s]

# Selection: descend using PUCT until a leaf/unexpanded node while tree[s].is_expanded: a ← argmax_a [ Q(s,a) + c_puct P(s,a) sqrt(sum_b N(s,b)) / (1 + N(s,a)) ] s ← APPLY(s, a) path.append(s)

# Expansion + evaluation if TERMINAL(s): v ← OUTCOME(s) else: p, v ← NETWORK(s, theta) EXPAND(tree, s, priors = p)

# Backup for s_i in reversed(path): N(s_i, a_i) += 1 Q(s_i, a_i) += (v - Q(s_i, a_i)) / N(s_i, a_i) v ← -v # value flips sign for the opposing player return normalize(N(s_root, ·)) # visit-count distribution = pi ```

Per-move inference cost. Each MCTS simulation performs one tree descent (depth $d$, the length of the game path so far, bounded by the game's maximum length) and one network evaluation at the leaf. With $n$ simulations per move, the search costs $O(n \cdot d)$ tree operations plus $n$ network forward passes. Since $d$ is typically small relative to $n$ (a few dozen moves deep versus hundreds of simulations), the dominant cost is $n$ network evaluations, each $O(1)$ in the number of layers times input size — practically, a fixed-cost GPU/TPU forward pass. AlphaGo Zero used $n=1600$ simulations per move during self-play; AlphaZero used $n=800$.

Space. The search tree stores one node per visited state, at most $O(n)$ nodes per move since each simulation can create at most one new node. Each node stores $O(|A(s)|)$ statistics ($N$, $Q$, $P$ per legal action), so total space per search is $O(n \cdot |A|_{\max})$, where $|A|_{\max} \approx 250$ for Go, or the maximum branching factor.

Training cost. Each self-play game of length $T$ moves costs $O(T \cdot n)$ network evaluations to generate, and produces $T$ training examples. Training itself is standard supervised learning cost: $O(\text{batch size} \times \text{network size})$ per gradient step. The total computational cost is dominated by self-play game generation, which is why AlphaGo Zero's reported training used thousands of TPUs generating millions of self-play games in parallel — the wall-clock bottleneck is data generation, not gradient descent.

Why the policy-improvement loop converges (correctness argument). The central claim is that MCTS is a policy improvement operator: given any network policy $p$ and value $v$ as priors, running enough simulations of PUCT search yields a visit distribution $\pi$ whose expected value (played against a fixed opponent, or in self-play) is at least as good as $p$'s, in the same sense that greedy improvement over an approximate value function improves a policy in classical policy iteration (compare Planning and Monte-Carlo Tree Search as an approximate best-response computation). Intuitively:

• If $v$ is a decent estimate of position value and $p$ concentrates prior probability on reasonable moves, then PUCT allocates most simulations to moves with the highest estimated $Q$, refining $Q(s,a)$ toward the true minimax value of $a$ as $n \to \infty$, since PUCT search is proven (in the tabular limit) to converge to the game-theoretic optimal value, much like UCB1-based MCTS converges to minimax play with enough samples.
• Training the network to imitate $\pi$ (rather than to imitate $p$ itself, which would be a no-op) is therefore training toward a genuinely improved target — this is analogous to policy iteration: evaluate (via search), improve (network imitates search), repeat.
• This resembles Deep Policy Gradient Methods in using self-generated experience to improve a policy, but differs fundamentally: the improvement signal here is not a return-based policy gradient but a distillation target produced by explicit lookahead, which tends to be lower-variance and more sample-efficient because search amplifies a mediocre prior into a much stronger target before any gradient step happens.

Tradeoffs, honestly stated. The loop's convergence is empirical and not accompanied by a full convergence proof for the deep-network case (unlike tabular policy iteration, which is provably monotonic). Function approximation, non-stationarity of the self-play opponent, and the finite simulation budget mean genuine improvement each iteration is a strong empirical regularity rather than a guarantee — occasional regressions (the network briefly getting worse) are handled by explicit evaluation gating in AlphaGo Zero (only replace the current best network if the challenger wins a majority of an evaluation match), a safeguard AlphaZero later relaxed for continuous self-play without gating, trading strict monotonic improvement for engineering simplicity and slightly faster overall progress.

Consider a single MCTS simulation step from a simplified position with three legal moves $\{A, B, C\}$, network priors $P = (0.5, 0.3, 0.2)$, and $c_{\text{puct}} = 1.5$, starting from an empty tree (all $N=0$, $Q=0$).

After 5 simulations: $N(A)=3, N(B)=2, N(C)=0$. Normalizing visit counts (temperature $\tau=1$) gives the improved policy $\pi = (0.6, 0.4, 0.0)$ — notice this differs sharply from the raw prior $P=(0.5, 0.3, 0.2)$: move $C$, initially given 20% prior weight, received zero search visits because early evaluations of $A$ and $B$ looked good enough that PUCT never found it worth exploring within this tiny budget, while $B$'s strong evaluation ($v=0.6$) pulled visits toward it despite its lower prior. This concretely shows how a handful of simulations can already redistribute probability mass away from the network's naive guess — the exact quantity used as a training target for the next gradient step. A second, larger-scale worked fact from AlphaGo Zero's published results: after roughly 4.9 million self-play games (using 1600 simulations per move), the trained network alone (zero search) played at a strength exceeding AlphaGo Lee (the version that beat Lee Sedol) with full tree search, illustrating how much game-strength gets distilled into the raw network weights through repeated policy-improvement cycles — the network head becomes, in effect, a compressed cache of many nights of tree search.

The AlphaGo/AlphaZero architecture reshaped both game AI and the broader deep reinforcement learning field. Its direct descendant MuZero extended the same policy-improvement-via-search idea to settings where the rules of the environment are not known in advance, learning an internal model instead — relevant to any planning problem where a simulator is unavailable. Modern chess engines (including open-source projects like Leela Chess Zero) directly reimplement the AlphaZero training loop, and the technique has been applied outside games to combinatorial optimization problems (chip placement, molecule design) where a policy/value network guided by tree search proposes and evaluates candidate solutions. More broadly, the idea that search can serve as a teacher for a neural network — producing better-than-current-policy training targets on the fly — has influenced the design of self-improving systems well beyond board games, including some approaches to program synthesis and automated theorem proving where a similar look-ahead-then-distill loop is used to bootstrap capability without external supervision.

Ask the tutor: How exactly does the PUCT formula's exploration term change behavior as simulation count grows large, and why does that guarantee the search eventually favors the truly best move even if the prior initially favored a worse one?