Mastering the Game of Go with Deep Neural Networks and Tree Search

Chess has roughly 10⁴⁷ legal positions; Go has approximately 10¹⁷⁰. In chess, the average branching factor is ~35 moves per turn; in Go it is ~250. Deep Blue conquered chess in 1997 by evaluating 200 million positions per second with handcrafted evaluation functions. That strategy is mathematically impossible for Go — even if you evaluated a trillion positions per second for the age of the universe, you would not scratch the surface.

Before AlphaGo, the best computer Go programs used Monte Carlo Tree Search with shallow pattern features and reached only amateur-level play (~2 dan amateur). The gap between amateur and professional was enormous — roughly equivalent to the gap between a club chess player and a world champion. Bridging that gap required replacing handcrafted features with learned representations that capture the deep positional intuition human experts develop over decades.

AlphaGo's training pipeline is a four-stage curriculum — think of it as an apprenticeship: first watch the master, then practice on your own, then develop judgment about positions.

Stage 1 — Supervised Learning (SL) Policy Network: A 13-layer deep convolutional neural network is trained on 30 million board positions from expert human games (KGS Go Server). The network takes the 19×19 board as input (with 48 feature planes encoding stone positions, liberties, capture history, etc.) and outputs a probability distribution over all 361 intersections — predicting the move a human expert would play. This network achieved 57% accuracy in predicting expert moves, a significant leap over the prior state of the art of 44%.

Stage 2 — Fast Rollout Policy: A simpler, lightweight policy trained on the same data but using only local pattern features. It sacrifices accuracy (24.2%) for speed — selecting a move in 2 microseconds instead of 3 milliseconds. This is used later inside MCTS to simulate thousands of games rapidly.

Stage 3 — Reinforcement Learning (RL) Policy Network: The SL policy is cloned and improved through self-play. The network plays games against randomly selected earlier versions of itself, and updates its weights using policy gradient methods (REINFORCE) to maximize the probability of winning. After training, the RL policy wins 80% of games against the SL policy — it has learned moves that win games, not just moves that look human.

Stage 4 — Value Network: A network with the same architecture as the policy network but outputting a single scalar — the probability of winning from a given position. Trained on 30 million positions generated by RL self-play (using different games for each position to avoid overfitting), it learns to evaluate board positions without playing to the end.

The genius of AlphaGo lies in factoring the game-playing problem into two complementary questions answered by two separate networks:

The policy network answers: "What move should I consider next?" Given a board position, it outputs a probability distribution over all legal moves. High-probability moves are explored first in the search tree, dramatically reducing the effective branching factor from ~250 to a handful of promising candidates. This is like a chess player's intuition — an instant sense of which moves "feel right" without calculating deeply.

The value network answers: "Who is winning in this position?" Given a board position, it outputs a single number between 0 and 1 — the estimated probability of winning. This replaces the need to play a game all the way to the end to know the outcome. A single forward pass through the value network is equivalent to thousands of random simulations, compressing judgment into learned intuition.

Both networks share the same deep convolutional neural network architecture (13 layers), but differ in their final output: a softmax distribution (policy) vs. a scalar regression (value).

The SL policy network learns by maximizing the log-likelihood of expert moves — the same cross-entropy objective used in classification. Given a board state $s$ and the expert move $a$, the gradient update pushes the network to assign higher probability to the correct move:

The RL policy network is then trained with REINFORCE: play a complete game, observe the outcome $z$ (+1 for win, −1 for loss), and update all moves in the game to make winning moves more likely:

Finally, the value network is trained by regression — minimizing the mean squared error between its prediction and the actual game outcome:

During actual gameplay, AlphaGo uses MCTS — a four-step cycle repeated thousands of times per move:

Selection: Starting from the root (current board position), traverse the tree by picking at each node the action that maximizes $Q(s,a) + u(s,a)$, where $Q$ is the current estimated value and $u$ is a bonus that encourages exploring moves the policy network considers promising but that haven't been tried much yet. This balances the classic tension between exploration (trying new paths) and exploitation (following paths known to be good).

Expansion: When the traversal reaches a leaf node (a position not yet in the tree), expand it by adding the new position and using the SL policy network to initialize the prior probabilities of its children.

Evaluation: Evaluate the leaf position using a weighted combination of: (a) the value network's prediction, and (b) the outcome of a fast rollout simulation using the lightweight rollout policy. The mixing parameter λ balances the neural network's deep understanding against the rollout's concrete game completion.

Backup: Propagate the evaluation value back up the tree, updating the $Q$ values of every node along the traversal path. After many iterations, the root's children have reliable value estimates, and AlphaGo selects the most-visited child as its move.

The critical insight that elevates AlphaGo beyond imitation is self-play. Once the SL policy network learned to mimic expert moves, it was cloned and set to play against itself millions of times. Through policy gradient reinforcement learning, it discovered moves that no human expert had played — moves that don't look "natural" but lead to victory.

Self-play solves two key problems simultaneously. First, it generates an unlimited supply of training data — no longer dependent on the finite corpus of human games. Second, it creates a curriculum of increasing difficulty: as the network improves, its opponent (an earlier version of itself) also improves, creating a natural arms race that pushes performance beyond what human data alone could teach.

The RL policy network after self-play training won 80% of games against the SL policy network. More importantly, it discovered novel strategies: moves that professional commentators initially called "mistakes" but later recognized as deeply creative and correct. This foreshadowed the even more dramatic discoveries in AlphaGo Zero, which learned entirely from self-play without any human data at all.

AlphaGo achieved a 99.8% win rate against all other Go programs and became the first program to defeat a human professional player on the full 19×19 board. In October 2015, it beat Fan Hui (European champion, 2 dan professional) 5–0 in a formal match. In March 2016, it defeated Lee Sedol (9 dan professional, widely considered one of the greatest players in the game's history) 4–1 in a globally televised match watched by over 200 million people.

The distributed version of AlphaGo used 1920 CPUs and 280 GPUs. However, even the single-machine version (48 CPUs + 8 GPUs) was strong enough to defeat Fan Hui — demonstrating that the algorithmic innovations, not just raw compute, were responsible for the breakthrough.

An ablation study revealed the relative contribution of each component: the value network alone was stronger than rollouts alone; combining both was stronger than either; and using the policy network to guide MCTS was essential — without it, the search explored too many irrelevant moves.

AlphaGo's most lasting contribution is not defeating a Go champion — it is the proof that combining neural network intuition with tree search planning creates systems far stronger than either approach alone. This principle — learned evaluation + intelligent search — has become a blueprint for AI reasoning systems, from AlphaGo Zero's pure self-play to modern chain-of-thought and tree-of-thought reasoning in large language models.