AlphaGo from Scratch — The Marriage of Search and Learning

Starting from why Go was considered unsolvable for so long, this piece unpacks how the policy network, the value network, Monte Carlo tree search and self-play each cover the others' weaknesses — with the formulas and the code. It closes with what this design handed down to inference-time compute in LLMs.

Mastering the game of Go with deep neural networks and tree search (Silver et al.

Why Go held out the longest

In 1997 the world chess champion lost to a computer. Go held out for nearly twenty more years. As late as 2015 the going estimate was "another decade." The search machinery that had cracked chess simply did not transfer.

There were two reasons, and neither was about sheer quantity — both were about kind.

The first is the number of forks. A Go board has 361 intersections on a 19×19 grid; averaged over a game there are roughly 250 legal moves at any point, and games run about 150 moves. Chess averages around 35 moves per turn over roughly 80 moves. That is an order-of-magnitude gap — like being asked to see all the way to the 150th junction of a maze that branches 250 ways at every step.

Multiplication makes the gap visible. Reading just three moves ahead is $250^3 \approx 15.6$ million lines. Ten moves ahead, $250^{10}$, is more than the age of the universe measured in seconds. The total number of legal positions on a 19×19 board was counted exactly in 2016: roughly $2.08 \times 10^{170}$ — more than the square of the number of atoms in the observable universe (estimated at around $10^{80}$). And since the tree multiplies by 250 with every extra move, a machine a million times faster buys you two or three more moves of depth. This was never a problem you could buy your way out of.

The second wall: nobody can say who is ahead

Chess has a crude but powerful yardstick: material. A queen is worth nine, a rook five; add and subtract and you get a decent read on a mid-game position. So you can cut a search short and still get a roughly correct evaluation back.

Go has nothing of the sort. Every stone is the same stone, so there are no point values; strength lives entirely in shape and relationship. "You lost your queen" is obviously bad to anyone. "This group is dead" may only become certain ten moves later. A strong player can glance at a board and say "Black is a little better," but nobody had ever written that judgment down as a formula.

So Go was too wide to read exhaustively and impossible to score if you stopped early. Search was blocked at both the entrance and the exit. That is why Go programs in the 2000s abandoned evaluation functions altogether and fell back on a blunt trick: play the rest of the game out at random, over and over, and count how often you won.

Search and learning began as separate tools

Put the two side by side. Search reads ahead on the spot. It runs from the rules alone and its answers are exact — but it is exponentially expensive. Learning builds a function from past experience. It answers instantly — but it is confidently wrong outside its training data, and merely looking at a board cannot follow a narrow tactical line.

Strong search is slow; fast intuition is shallow. For years Go programs bet on one side of that choice or the other. AlphaGo's invention was not a new component. It was fitting the two tools onto each other's weaknesses.

• A learned policy points to a handful of promising moves out of 250 → the tree's width is pruned
• A learned value returns a win or loss without playing to the end → the tree's depth is pruned
• Search then reads the pruned, now tractable tree carefully

The nets do the pruning; search does the reading. Together they reached a place neither could reach alone.

The policy network: pruning width

The policy network takes a board $s$ and returns a probability for every intersection, $p(a\mid s)$. The original AlphaGo built it by supervised learning on human game records — a classification problem, "where did a human play in this position?" The paper reports 57.0% accuracy.

The thing to hold onto is that 57% is not strength. Its job is not to win; its job is to narrow 250 candidates down to a dozen or so. AlphaGo also kept a fast rollout policy (a linear model, 24.2% accurate) that traded accuracy for speed, used to slam a game out to the end from a leaf.

The value network: pruning depth

The value network maps a board $s$ to a single number, $v(s) \in [-1, 1]$: $+1$ means the side to move wins, $-1$ that it loses. It is the evaluation function Go never had, obtained by learning rather than by hand.

The trap was in the training data. Using every position from a single game makes the positions too similar to one another, and the network just memorises "Black won this game." So they drew one position per game from 30 million self-play games. What that buys is not volume but independence between samples.

MCTS stitches the two together

Monte Carlo tree search (MCTS) is what takes the policy and the value and turns them into a move. To choose a single move, it repeats these four steps hundreds to thousands of times.

1. Select: walk from the root down to a leaf, following the formula below
2. Expand: create children at the leaf and have the policy net produce $p(a\mid s)$
3. Evaluate: estimate how good that leaf is
4. Back up: propagate the estimate to the root, updating the statistics of every branch along the way

The selection rule is the heart of the method.

Put in words, this says: add up "moves that worked when I tried them" and "moves the policy likes but I haven't tried yet," then take the bigger one. $Q(s,a)$ is the average search evaluation through that branch (track record), $P(s,a)$ is the prior the policy assigned (hunch), $N(s,a)$ is how often the branch has been chosen, and $c_{\mathrm{puct}}$ is the dial for how far you trust the hunch.

The second term has $N(s,a)$ in the denominator, so it shrinks every time you pick that branch. Early on the search fans out along the hunch; as the counts pile up, the track record $Q$ takes over. Explore and exploit are folded into a single line (the same lineage as Monte Carlo methods).

The original went one step further and made the third step a weighted average, $V(s_L) = (1-\lambda)\, v_\theta(s_L) + \lambda \, z_L$ — in words, mix the value network's estimate with the actual result of slamming the game out with the fast policy. The paper reports that an even split, $\lambda = 0.5$, was strongest. A learned hunch and a crude but complete read-out were better together than either alone.

Self-play: swallowing search results as your own intuition

The following year, AlphaGo Zero threw away the human games it had started from. The network became a single body with two heads growing out of it: a policy $\mathbf{p}$ and a value $v$.

The key idea is to see MCTS as a policy improvement operator. Running 1600 simulations with the raw $\mathbf{p}$ as a hunch yields a better move than $\mathbf{p}$ alone. So use the search result as the teacher: train the network to play that way without searching next time. The labels come from visit counts.

Put in words: the more a move was read, the higher the probability it gets. $\tau$ is a temperature: at $\tau = 1$ the label is the raw ratio of visit counts, and as $\tau \to 0$ all the mass collapses onto the single most-visited move.

The training objective is a sum of three terms.

$$\ell = (z - v)^2 - \boldsymbol{\pi}^\top \log \mathbf{p} + c\lVert\theta\rVert^2$$

Again in words: make the value head predict the game result $z$, make the policy head imitate the $\boldsymbol{\pi}$ that search produced, and add a penalty so the weights don't run away.

That closes the loop. A stronger net → better moves at the same simulation budget → better teaching labels. It gets stronger with no external data because search adds a small increment every time and learning freezes that increment in place.

One more piece is essential: Dirichlet noise at the root, $P(s,a) = (1-\varepsilon)\, p_a + \varepsilon\, \eta_a$. Without it, self-play keeps playing whatever currently looks good and plateaus. Swap the rules for chess and shogi and you get AlphaZero; withhold the rules entirely and you get MuZero.

PUCT-MCTS in code

import numpy as np

def puct_select(node, c=1.5):
    total = np.sqrt(node.N.sum())            # sqrt of the parent's total visits
    u = c * node.P * total / (1 + node.N)    # the hunch (largest when unvisited)
    return int(np.argmax(node.Q + u))        # track record + hunch

def simulate(node, net):
    if node.is_terminal():
        return -node.result()                # sides swap, so flip the sign
    if node.children is None:                # expand: the net is called here, once
        node.P, v = net(node.state)          # policy and value in one shot
        node.children = node.expand()
        return -v
    a = puct_select(node)
    v = simulate(node.children[a], net)      # recurse down to a leaf
    node.W[a] += v; node.N[a] += 1           # back up
    node.Q[a] = node.W[a] / node.N[a]
    return -v

The one quirk is negating at every level. A $+0.8$ (good for me) is a $-0.8$ for the opponent one ply up. Forget it, and the search will mix up your gain with your opponent's — and be confidently wrong about it.

What carried over to LLM inference

AlphaGo beat a top professional 4–1 in March 2016 and swept the world's then-strongest player 3–0 in May 2017. Its emblem is move 37 of game two — a move from outside the human record, which the system was reported to have given roughly a one-in-ten-thousand chance of being played by a human.

The design is still alive inside language models: adding compute at inference time makes a model smarter (test-time scaling), a value function as a grader of partial work (process reward models), and distilling search results back into the weights.

But the assumption that mattered most did not transfer. Go has a perfect referee, so no lie ever enters $z$. Nothing plays that role for whether a piece of writing is good; the grader is itself a learned approximation. So search goes hunting not for correctness but for holes in the grader (LLM agent basics).

In practice

Who reaches for this, and when. The pattern transfers directly when (1) the moves are finite and enumerable, and (2) a correct score falls out mechanically at the terminal state. Game AI, combinatorial optimisation (delivery routing, circuit placement), and code-generation or tool-using agents that can be graded automatically by "did the tests pass?"

Knobs you will actually touch. num_simulations (searches per move — the main dial trading strength against compute), c_puct, temperature ($\tau$: high during self-play, near zero in production), dirichlet_epsilon, virtual_loss (stops parallel threads from all piling onto the same branch), and resign_threshold. For implementations, read DeepMind's mctx (JAX) or OpenSpiel; for Go specifically, KataGo and Leela Zero.

Where this bites.

• A missing sign flip. Without negating per ply, the search will believe a losing move is best. The shortest test is "does it find a mate in one?"
• $c_{\mathrm{puct}}$ depends on the scale of $Q$. The same number means something twice as strong depending on whether $Q$ lives in $[-1,1]$ or $[0,1]$.
• Leaving search noise on at inference. Dirichlet noise and $\tau=1$ are training devices. Forget to switch them off and production is quietly weaker in a way that doesn't look like a bug.
• The moment a scoring function becomes the optimisation target, search starts breaking it. If the reward is an approximate model, stronger search finds its holes faster.

Takeaways

• Go's two walls were width and the absence of a mid-game score; search alone cleared neither
• The policy net prunes width, the value net prunes depth, and MCTS reads what is left
• Self-play is a loop in which learning freezes the increment that search produces
• What crossed over to LLMs: inference-time compute, value-based pruning, distillation of search results. What did not: the perfect referee