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.