Search + Learning: The Idea Behind AlphaGo, AlphaZero, MuZero

This is the recipe that beat Lee Sedol, crushed Stockfish in 4 hours of training, and reached IMO silver-medal level on Olympiad math problems in 2024. MCTS guided by a neural network — the network gives the search a smart prior, the search gives the network a stronger target. They bootstrap each other into superhuman play. And in 2025 the same recipe shows up in o1, o3, and DeepSeek-R1's reasoning. Search + learning may be the most general AI idea we have.

Scope of this lesson — the IDEA. This page teaches MCTS (the general algorithm) and tells the AlphaGo → AlphaZero → MuZero story at a conceptual level: why search and learning compose, where each step in the progression removed an assumption, and how the recipe escapes board games. For the math — the PUCT derivation, the term-by-term AlphaZero loss, the MuZero K-step loss, and a full AlphaZero (not just MCTS) tic-tac-toe trainer — read the companion lesson AlphaZero & MuZero: Search + Learning in One Loop after this one.

Learning Objectives

After this lesson, you will be able to:

Walk through MCTS step by step — selection (UCB1), expansion, simulation, backup — and understand why it became the planning algorithm of choice for combinatorial games
Trace the AlphaGo → AlphaGo Zero → AlphaZero → MuZero progression: each step removes more human knowledge while keeping the same core recipe — deep network + search + self-play
See how MCTS acts as a policy improvement operator at training time: the search produces a stronger policy than the network alone, and the network learns to imitate that stronger policy
Recognize the recipe in modern systems beyond board games — AlphaProof's IMO-medal performance and o1/o3 reasoning models are the same idea applied to math and language

Prerequisites

Before You Start

Review

Why

Why This Matters

Why AlphaGo's Move 37 became a culture-shifting moment for AI — in game 2 against Lee Sedol, AlphaGo played a move humans called "creative" — a move so novel and so good that professional Go players reconsidered their entire approach to the game; it was the first time most of the world saw an AI play with what looked like genuine insight
Why AlphaZero training Stockfish-level chess in 4 hours rewrote everyone's intuition for general AI — Stockfish is the product of decades of hand-engineered chess knowledge from grandmasters; AlphaZero learned to crush it from scratch using only the rules of chess and 4 hours of self-play on TPUs
Why AlphaProof getting an IMO silver medal in 2024 hints at the next AI frontier — DeepMind applied the same MCTS + neural network + self-play recipe to Olympiad math problems and reached the level of a strong human medalist; the recipe is no longer just for games
Build this → Implement a tic-tac-toe MCTS player from scratch with selection / expansion / simulation / backup, then bolt on a tiny neural network that learns from MCTS rollouts — a 100-line miniature of AlphaZero

Don't worry if "search + learning" sounds magical — once you implement MCTS once, you'll see it's just bookkeeping over a tree. The deep network on top is what makes it scale, but the core algorithm is something you can write in a single afternoon.

#The Two Halves of the Recipe

Intuition

Build Your Intuition

Search and learning are two ways to get a good move, and the AlphaZero recipe combines them.

Search (like minimax or MCTS) imagines many possible futures from the current position, evaluates how each one ends, and picks the move that leads to the best ones. The deeper you search, the better your move, but the search tree explodes exponentially with depth.

Learning (a deep neural network) is fast at every step but only as smart as the data it was trained on. It can suggest a move instantly but might miss subtle traps.

The genius of AlphaZero: MCTS guided by the network is much stronger than either alone. The network gives the search a smart prior on which moves to explore. The search produces an even better answer than the network would have given alone. Then the network is trained to match the search's answer. The cycle compounds.

This is why DeepMind described MCTS as a "policy improvement operator" — it takes a policy in (the network) and outputs a stronger policy out (the search-improved distribution).

#Monte Carlo Tree Search: The Four Phases

MCTS builds a search tree iteratively. Each iteration goes through four phases:

Intuition

MCTS in 60 seconds

Selection: Starting at the root, walk down the tree picking the child with the best UCB1 score until you reach a node that hasn't been fully expanded. UCB1 balances exploitation (high estimated value) with exploration (low visit count).
Expansion: Add a new child node for an unexplored action.
Simulation (or "rollout"): From the new node, simulate the game to the end — in classic MCTS with random play, in AlphaZero with the policy network's suggested moves until the value network evaluates the position.
Backup: Walk back up the tree, updating the visit counts and value estimates of every node on the path.

Repeat thousands of times. The action whose root child has the highest visit count is the agent's move. Visit count, not value, because high-value but rarely-visited nodes might be optimistic outliers.

a^{*} = \arg\max_{a} \left[\, Q(s, a) + c \cdot \sqrt{\frac{\ln N(s)}{N(s, a)}} \,\right]

Anecdote

Historical Note

MCTS was introduced by Rémi Coulom in 2006 ("Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search") for the game of Go, where minimax was failing because the branching factor (~250) and game length (~150) made traditional alpha-beta search hopeless. MCTS dominated computer Go from 2007 to 2015 and reached strong-amateur-level play.

Silver et al. 2016 "Mastering the Game of Go with Deep Neural Networks and Tree Search" (Nature) — AlphaGo combined MCTS with two neural networks (a policy net trained on 30 million human moves, then improved by RL self-play, plus a value net) and beat Lee Sedol 4-1.

Silver et al. 2017 "Mastering the Game of Go without Human Knowledge" (Nature) — AlphaGo Zero dropped the human-game pretraining entirely; pure self-play with one combined policy + value network beat the original AlphaGo 100-0 in 40 days.

Silver et al. 2018 "A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play" (Science) — AlphaZero generalized the same algorithm; in 4 hours of TPU training surpassed Stockfish at chess.

Schrittwieser et al. 2020 "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model" (Nature) — MuZero did all of the above without being given the rules of the game — it learns a dynamics model from raw experience.

2024: DeepMind's AlphaProof + AlphaGeometry 2 reached IMO silver-medal level on the 2024 International Mathematical Olympiad, applying the same recipe to formal math.

#AlphaGo: Networks + Search

The original 2016 AlphaGo had three neural networks:

Supervised policy network p_σ trained on 30 million human moves — predicts the next human move given the board.
RL policy network p_ρ — the supervised network further trained against itself via REINFORCE-style policy gradient.
Value network v_θ — predicts the winner from a given position.

At play time, MCTS used p_σ as a prior on which moves to explore (multiplied into the UCB selection), called the value network at leaf nodes for evaluation, and combined it with rollouts using a fast linear policy.

The architecture worked but was complex. AlphaGo Zero stripped it down.

#AlphaGo Zero: Self-Play From Scratch

Two key changes in 2017:

One combined policy + value network (two heads on a shared ResNet backbone) replaces the three networks.
No human data. The network starts with random weights. It plays itself with MCTS, and the MCTS-improved move distributions become the training labels.

The training signal is a single loss with three terms: value MSE (predicted value vs. actual outcome), cross-entropy between the MCTS visit-count distribution and the network's policy, and L2 weight decay. The MCTS at each position runs ~1600 simulations; the visit-count distribution at the root is treated as the improved policy π, and the network is trained to match it.

For the math. The full AlphaZero loss term by term, the PUCT vs. UCB1 distinction, and the visit-count softmax with temperature τ all live in the companion lesson AlphaZero & MuZero: Search + Learning in One Loop. This page sticks to the idea.

#AlphaZero: One Algorithm, Three Games

AlphaZero (2018) applied AlphaGo Zero to chess and shogi as well as Go. Same code, same network architecture, same algorithm. After 4 hours of training on 5000 first-gen TPUs:

Chess: surpassed Stockfish 8 (then-state-of-art).
Shogi: surpassed Elmo (the strongest shogi engine).
Go: surpassed AlphaGo Zero.

The lesson was profound: a single algorithm with no game-specific knowledge could master three completely different games at superhuman level. Decades of hand-engineered domain knowledge in chess engines were defeated by general search + general learning + self-play.

What Do You Think?

You want to apply AlphaZero-style training to a new game where you DON'T have a perfect simulator (you can't query 'if I take action a, what state results?'). What's your problem and what's the fix?

The answer is the bridge to MuZero: AlphaZero's MCTS expansion phase requires knowing how the world reacts to each action. For board games, you have the rules. For Atari games, you have the emulator. But for many real-world problems, you don't have a perfect simulator.

#MuZero: Learn the Rules Too

MuZero (2020) generalizes AlphaZero by learning a model of the environment from interaction. Instead of expanding the tree with the true game rules, it expands with a learned dynamics function that predicts the next hidden state from the current hidden state and the chosen action. Search runs entirely in a latent space defined by three networks (a representation that embeds the raw observation, a dynamics that predicts next-latent and reward, and a prediction head that emits policy and value). The model is trained to predict only the value, policy, and reward at search-relevant states, not to reconstruct the observation. This is why it works: it learns "just enough" of the world to plan well.

MuZero matched AlphaZero on board games and dramatically beat the prior state-of-art on Atari — the first algorithm to do both top-tier game playing and top-tier video-game-from-pixels with one method.

For the math. The three networks (h, g, f), the K-step unrolled loss that keeps the learned dynamics from collapsing, and a runnable AlphaZero-on-tic-tac-toe playground (not just MCTS) are in AlphaZero & MuZero: Search + Learning in One Loop.

pythonplayground.py · Pyodide

# Tic-tac-toe MCTS in ~150 lines — pure search, NO neural network.
# (The companion 'AlphaZero & MuZero' lesson has the full network-trained version.)
import math
import random
import numpy as np

# --- Game logic ---
def initial_board():
  return np.zeros(9, dtype=int)

def legal_moves(board):
  return [i for i in range(9) if board[i] == 0]

def winner(board):
  lines = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
  for a,b,c in lines:
      s = board[a] + board[b] + board[c]
      if s == 3:  return 1
      if s == -3: return -1
  if not legal_moves(board):
      return 0  # draw
  return None  # game ongoing

# --- MCTS node ---
class Node:
  __slots__ = ("board", "player", "parent", "move", "children",
               "visits", "value_sum", "untried_moves")
  def __init__(self, board, player, parent=None, move=None):
      self.board = board.copy()
      self.player = player  # +1 or -1, who moves at this node
      self.parent = parent
      self.move = move      # move that got us here from parent
      self.children = []
      self.visits = 0
      self.value_sum = 0.0
      self.untried_moves = legal_moves(board)

def q(self):
      return self.value_sum / self.visits if self.visits > 0 else 0.0

def ucb(self, c=1.4):
      if self.visits == 0: return float('inf')
      return self.q() + c * math.sqrt(math.log(self.parent.visits) / self.visits)

# --- Selection ---
def select(node):
  while not node.untried_moves and node.children:
      node = max(node.children, key=lambda n: n.ucb())
  return node

# --- Expansion ---
def expand(node):
  move = node.untried_moves.pop()
  new_board = node.board.copy()
  new_board[move] = node.player
  child = Node(new_board, -node.player, parent=node, move=move)
  node.children.append(child)
  return child

# --- Simulation (random rollout) ---
def simulate(board, player):
  b = board.copy()
  p = player
  while True:
      w = winner(b)
      if w is not None: return w
      moves = legal_moves(b)
      b[random.choice(moves)] = p
      p = -p

# --- Backup ---
def backup(node, value):
  while node is not None:
      node.visits += 1
      # value is from the perspective of the root player; flip per node player
      node.value_sum += value if node.player == -1 else -value
      node = node.parent

# --- One MCTS iteration ---
def mcts_iteration(root):
  leaf = select(root)
  w = winner(leaf.board)
  if w is None and leaf.untried_moves:
      leaf = expand(leaf)
  if w is None:
      value = simulate(leaf.board, leaf.player)
  else:
      value = w
  backup(leaf, value)

# --- Pick move via N MCTS simulations ---
def best_move(board, player, n_sims=2000):
  root = Node(board, player)
  for _ in range(n_sims):
      mcts_iteration(root)
  # Best by visit count, not by value
  best_child = max(root.children, key=lambda n: n.visits)
  return best_child.move, [(c.move, c.visits, c.q()) for c in root.children]

# --- Run a self-play game ---
print("Tic-tac-toe MCTS self-play:\n")
board = initial_board()
player = 1
for turn in range(9):
  move, stats = best_move(board, player, n_sims=1000)
  board[move] = player
  print(f"Turn {turn+1}, player {player}: move {move}")
  print(f"  Board: {board.reshape(3,3)}")
  if winner(board) is not None:
      w = winner(board)
      print(f"\nResult: {'Player 1 wins' if w==1 else 'Player -1 wins' if w==-1 else 'Draw'}")
      break
  player = -player

print("\nCHALLENGE: Replace random rollouts with a tiny policy network's prior")
print("(softmax over moves). That's how AlphaZero replaces simulation with the prior + value.")

Tests · Verify each move is legal. Verify game terminates within 9 turns. Verify visit counts at root sum to n_sims. Verify the move chosen is the most-visited child.

#The Modern Recipe

#Key Takeaways

MCTS = selection (UCB) + expansion + simulation + backup, repeated thousands of times. The visit count distribution at the root is the search-improved policy. The action with highest visit count is the move.
AlphaZero's loss is one elegant equation. Match the network's value to the game outcome (MSE), match the network's policy to MCTS visit counts (cross-entropy), L2 regularize. Train across millions of self-play positions.
MCTS is a policy improvement operator. Search converts a policy in (the prior network) to a stronger policy out (the visit-count distribution). The network learns to imitate the stronger policy. The next iteration's search is even better.
AlphaGo Zero → AlphaZero → MuZero progressively removed assumptions. AlphaGo Zero dropped human data; AlphaZero dropped game-specific tuning; MuZero dropped the requirement of perfect game rules by learning a dynamics model.
The recipe generalizes far beyond games. AlphaProof, AlphaGeometry, and o1/o3-style reasoning models are non-game applications of search + learning + self-play. The main constraint: you need a verifiable reward signal to guide the search.

Interactive Lab

Step through Monte Carlo Tree Search one iteration at a time — see how the UCB1 bandit at every node grows the tree toward promising branches, and how visit counts (not raw Q-values) become the policy improvement signal AlphaZero learns from.

MCTS Tree Builder

#Quick Check

Quick Check1 / 4

Why does AlphaZero pick its move by visit count rather than by predicted value Q?

The search-plus-learning recipe is one of the most powerful ideas in modern AI, and it took 14 years from MCTS in 2006 to AlphaProof's IMO silver in 2024. If you want the math next (PUCT, AlphaZero loss term-by-term, MuZero K-step loss, an end-to-end AlphaZero trainer), continue to AlphaZero & MuZero: Search + Learning in One Loop. Otherwise, the next track lesson covers multi-agent RL — how the recipe extends when there's more than one agent in the world.

Search + Learning: The Idea Behind AlphaGo, AlphaZero, MuZero

This is the recipe that beat Lee Sedol, crushed Stockfish in 4 hours of training, and reached IMO silver-medal level on Olympiad math problems in 2024. MCTS guided by a neural network — the network gives the search a smart prior, the search gives the network a stronger target. They bootstrap each other into superhuman play. And in 2025 the same recipe shows up in o1, o3, and DeepSeek-R1's reasoning. Search + learning may be the most general AI idea we have.

Scope of this lesson — the IDEA. This page teaches MCTS (the general algorithm) and tells the AlphaGo → AlphaZero → MuZero story at a conceptual level: why search and learning compose, where each step in the progression removed an assumption, and how the recipe escapes board games. For the math — the PUCT derivation, the term-by-term AlphaZero loss, the MuZero K-step loss, and a full AlphaZero (not just MCTS) tic-tac-toe trainer — read the companion lesson AlphaZero & MuZero: Search + Learning in One Loop after this one.

Learning Objectives

After this lesson, you will be able to:

Walk through MCTS step by step — selection (UCB1), expansion, simulation, backup — and understand why it became the planning algorithm of choice for combinatorial games
Trace the AlphaGo → AlphaGo Zero → AlphaZero → MuZero progression: each step removes more human knowledge while keeping the same core recipe — deep network + search + self-play
See how MCTS acts as a policy improvement operator at training time: the search produces a stronger policy than the network alone, and the network learns to imitate that stronger policy
Recognize the recipe in modern systems beyond board games — AlphaProof's IMO-medal performance and o1/o3 reasoning models are the same idea applied to math and language

Prerequisites

Before You Start

Review

Why

Why This Matters

Why AlphaGo's Move 37 became a culture-shifting moment for AI — in game 2 against Lee Sedol, AlphaGo played a move humans called "creative" — a move so novel and so good that professional Go players reconsidered their entire approach to the game; it was the first time most of the world saw an AI play with what looked like genuine insight
Why AlphaZero training Stockfish-level chess in 4 hours rewrote everyone's intuition for general AI — Stockfish is the product of decades of hand-engineered chess knowledge from grandmasters; AlphaZero learned to crush it from scratch using only the rules of chess and 4 hours of self-play on TPUs
Why AlphaProof getting an IMO silver medal in 2024 hints at the next AI frontier — DeepMind applied the same MCTS + neural network + self-play recipe to Olympiad math problems and reached the level of a strong human medalist; the recipe is no longer just for games
Build this → Implement a tic-tac-toe MCTS player from scratch with selection / expansion / simulation / backup, then bolt on a tiny neural network that learns from MCTS rollouts — a 100-line miniature of AlphaZero

#The Two Halves of the Recipe

Intuition

Build Your Intuition

Search and learning are two ways to get a good move, and the AlphaZero recipe combines them.

Learning (a deep neural network) is fast at every step but only as smart as the data it was trained on. It can suggest a move instantly but might miss subtle traps.

This is why DeepMind described MCTS as a "policy improvement operator" — it takes a policy in (the network) and outputs a stronger policy out (the search-improved distribution).

#Monte Carlo Tree Search: The Four Phases

MCTS builds a search tree iteratively. Each iteration goes through four phases:

Intuition

MCTS in 60 seconds

Selection: Starting at the root, walk down the tree picking the child with the best UCB1 score until you reach a node that hasn't been fully expanded. UCB1 balances exploitation (high estimated value) with exploration (low visit count).
Expansion: Add a new child node for an unexplored action.
Simulation (or "rollout"): From the new node, simulate the game to the end — in classic MCTS with random play, in AlphaZero with the policy network's suggested moves until the value network evaluates the position.
Backup: Walk back up the tree, updating the visit counts and value estimates of every node on the path.

a^{*} = \arg\max_{a} \left[\, Q(s, a) + c \cdot \sqrt{\frac{\ln N(s)}{N(s, a)}} \,\right]

Anecdote

Historical Note

2024: DeepMind's AlphaProof + AlphaGeometry 2 reached IMO silver-medal level on the 2024 International Mathematical Olympiad, applying the same recipe to formal math.

#AlphaGo: Networks + Search

The original 2016 AlphaGo had three neural networks:

Supervised policy network p_σ trained on 30 million human moves — predicts the next human move given the board.
RL policy network p_ρ — the supervised network further trained against itself via REINFORCE-style policy gradient.
Value network v_θ — predicts the winner from a given position.

The architecture worked but was complex. AlphaGo Zero stripped it down.

#AlphaGo Zero: Self-Play From Scratch

Two key changes in 2017:

One combined policy + value network (two heads on a shared ResNet backbone) replaces the three networks.
No human data. The network starts with random weights. It plays itself with MCTS, and the MCTS-improved move distributions become the training labels.

For the math. The full AlphaZero loss term by term, the PUCT vs. UCB1 distinction, and the visit-count softmax with temperature τ all live in the companion lesson AlphaZero & MuZero: Search + Learning in One Loop. This page sticks to the idea.

#AlphaZero: One Algorithm, Three Games

AlphaZero (2018) applied AlphaGo Zero to chess and shogi as well as Go. Same code, same network architecture, same algorithm. After 4 hours of training on 5000 first-gen TPUs:

Chess: surpassed Stockfish 8 (then-state-of-art).
Shogi: surpassed Elmo (the strongest shogi engine).
Go: surpassed AlphaGo Zero.