---
title: "Case Studies: Learning to Play"
module: Deep Reinforcement Learning
moduleNumber: 4
lessonNumber: 5
order: 405
summary: >
  The game-playing systems that turned reinforcement learning from a theory into a
  track record: Samuel's checkers player, TD-Gammon, Watson's Daily-Double wagering,
  a reinforcement-learning memory controller, DQN, and AlphaGo through AlphaGo Zero.
  Read as a set they draw one line — a value function, learned by self-play or
  interaction, refined by search, carried by a deep network — that runs from a 1959
  checkers program to superhuman Go.
topics: [Deep RL]
sources:
  - book: Sutton & Barto
    ref: "Ch. 16 — Applications and Case Studies; §16.1 TD-Gammon; §16.2 Samuel's Checkers Player"
  - book: Sutton & Barto
    ref: "§16.3 Watson's Daily-Double Wagering; §16.4 Optimizing Memory Control; §16.5 Human-level Video Game Play"
  - book: Sutton & Barto
    ref: "§16.6 Mastering the Game of Go; §16.6.1 AlphaGo; §16.6.2 AlphaGo Zero"
---

The methods in these notes were built to be general, but generality is not the
same as evidence. What settles whether an idea works is a system that beats the
best alternative on a problem nobody could hand-tune. Chapter 16 of Sutton and
Barto collects those systems, and read in sequence they show one pattern. Every
landmark shares the same skeleton: **a value function**, learned by acting or by
playing against a copy of itself, **refined by search** at decision time, and,
in the later cases, **carried by a deep network** that discovers its own
features. The pieces were assembled a little more each decade; the last assembly,
AlphaGo Zero, needed no human data at all.

$$
% caption: The through-line of the case studies. A value or policy is learned
% from experience — often self-play — a search may sharpen it at decision time,
% and a function approximator (linear, then deep) carries it. Each system adds a
% piece; the shape is constant.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=26mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (exp)  at (0,0)    {experience\\(self-play)};
  \node[box] (val)  at (3.6,0)  {value / policy\\learned};
  \node[box] (srch) at (7.2,0)  {search ref\/ines\\at decision time};
  \node[box, draw=acc, text=acc, thick] (act) at (10.8,0) {action};
  \draw[->, acc, thick] (exp) -- (val);
  \draw[->, acc, thick] (val) -- (srch);
  \draw[->, acc, thick] (srch) -- (act);
  \draw[->, black, thick] (val.south) .. controls (3.6,-1.5) and (0,-1.5) .. (exp.south)
    node[midway, below, font=\scriptsize, text=black] {better play generates better experience};
\end{tikzpicture}
$$

## Samuel's checkers player: the historical root

Before there was a name for it, Arthur Samuel was doing temporal-difference
learning. His checkers programs, written for the IBM 701 starting in 1952 with a
learning version finished in 1955, are the earliest ancestor in the line.[^sb-samuel]
Samuel chose checkers over chess deliberately: simple enough that learning, not
search bookkeeping, could be the object of study, yet still "taken from life."

The program played by a minimax lookahead from the current position. Terminal
positions of the search were **scored** by a linear evaluation function, a
"scoring polynomial" over hand-chosen features, and the score was backed up
through the tree under the assumption that each side plays to its own advantage.
The most important feature was **piece advantage**, weighted by a fixed,
non-modifiable coefficient, so the program's goal was, in effect, to win.

The learning was the interesting part. Samuel's second method, which he called
_learning by generalization_, adjusted the weights of the scoring polynomial
after each move by pushing a position's value toward the backed-up minimax value
of a search launched one move later. That is a TD update in all but name: the
value of a state is made to equal the value of the states likely to follow it.
Sutton and Barto state the connection plainly — Samuel's method "was the same in concept
as that used much later by Tesauro in TD-Gammon."

$$
% caption: Samuel's backup. The value of an on-move position is nudged toward the
% minimax value of a search launched from the on-move position one full move
% later — a temporal-difference update between successive real positions, with a
% search filling the gap.
\begin{tikzpicture}[>=stealth, font=\small,
  statenode/.style={circle, draw, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[statenode] (p0) at (0,0) {};
  \node[anchor=north, font=\scriptsize] at (0,-0.5) {on-move now};
  \node[statenode] (p1) at (5.2,0) {};
  \node[anchor=north, font=\scriptsize] at (5.2,-0.5) {on-move next};
  % the intervening move (opponent + self) as a faint span
  \draw[black, thick, ->] (p0) -- (p1) node[midway, above=1mm, font=\scriptsize, text=black] {one full move of play};
  % search from the later position
  \node[statenode, fill=black!8] (t1) at (7.0,1.2) {};
  \node[statenode, fill=black!8] (t2) at (7.0,0.0) {};
  \node[statenode, fill=black!8] (t3) at (7.0,-1.2) {};
  \draw[black] (p1) -- (t1);
  \draw[black] (p1) -- (t2);
  \draw[black] (p1) -- (t3);
  \node[anchor=west, font=\scriptsize] at (7.3,-1.2) {minimax search};
  % backed-up value returned as the target
  \draw[acc, thick, ->] (p1) .. controls (3.5,2.4) and (1.7,2.4) .. (p0)
    node[midway, above, font=\scriptsize, text=acc] {backed-up value = target};
\end{tikzpicture}
$$

Samuel's checkers player rose to a strong amateur level and was, for years, one of
the most visible achievements of machine learning. It also carried a warning that
the modern theory later formalized. Samuel included **no rewards** and no special
treatment of terminal positions, so nothing tied his value function to actually
winning. As he himself noted, a constant value for every position would satisfy
his self-consistency criterion perfectly while playing terrible checkers. He kept
the piece-advantage weight fixed precisely to forbid that degenerate fixed point.
The lesson — that a self-consistent value function must be _anchored_ to a reward
and to terminal values — names the discipline that
[dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming)
and [TD learning](/reinforcement-learning/tabular-methods/temporal-difference-learning)
build in from the start.

## TD-Gammon: self-play meets a neural net

TD-Gammon, written by Gerald Tesauro around 1992, is the system that first showed
reinforcement learning could reach expert human play. It put three ideas together
that recur through every later case: **TD(λ)**, **self-play**, and a **neural
network** as the value function.[^sb-tdgammon]

Backgammon suits reinforcement learning better than chess or checkers do. The game
is stochastic (a dice roll before each move) with a branching factor near 400,
far too large for the deep heuristic search that dominated chess. But its full
state is always visible, and every game ends in a win or a loss that reads
naturally as a reward. Tesauro set the reward to zero on every step except the
final one, so the estimated value $\hat v(s, \mathbf{w})$ of a board position $s$
is literally the probability of winning from $s$.

The value function was a standard multilayer network: an input layer encoding the
board (198 units in the first version), one hidden layer, and an output unit whose
sigmoid produces a win probability. Weights were updated by the semi-gradient
TD(λ) rule with the gradient computed by backpropagation,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\Big[\,R_{t+1} + \gamma\,\hat v(S_{t+1},\mathbf{w}_t) - \hat v(S_t,\mathbf{w}_t)\Big]\,\mathbf{z}_t,
\qquad
\mathbf{z}_t \;\doteq\; \gamma\lambda\,\mathbf{z}_{t-1} + \nabla \hat v(S_t,\mathbf{w}_t),
$$

with $\gamma = 1$ and the reward zero until the game is won, so the TD error is
usually just $\hat v(S_{t+1},\mathbf{w}) - \hat v(S_t,\mathbf{w})$. Nothing here is
new to these notes; it is the [eligibility-trace](/reinforcement-learning/approximation/eligibility-traces)
form of TD applied to a nonlinear approximator.

The source of games was the second idea. Tesauro's learner played _against
itself_. To move, it considered every position its dice roll allowed, evaluated
each with the network, and chose the highest-valued one; these are **afterstates**,
the position after the move but before the opponent's dice. Both sides moved this
way, generating an endless stream of games at no cost.

$$
% caption: TD-Gammon's self-play loop. The same network scores every afterstate a
% dice roll allows and the move to the best-valued one is taken; both sides play
% this way, and each transition supplies a TD backup that updates the weights.
% Here $v(s)$ is the network's win-probability estimate.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (roll)  at (0,0)    {dice roll};
  \node[box] (cand)  at (3.4,0)  {candidate\\afterstates};
  \node[box, draw=acc, text=acc, thick] (net) at (6.8,0) {network\\v(s)};
  \node[box] (move)  at (10.2,0) {play best\\afterstate};
  \draw[->, acc, thick] (roll) -- (cand);
  \draw[->, acc, thick] (cand) -- (net);
  \draw[->, acc, thick] (net) -- (move);
  % TD backup arrow underneath
  \draw[->, red, thick] (move.south) .. controls (10.2,-1.6) and (6.8,-1.6) .. (net.south)
    node[midway, below, font=\scriptsize, text=red] {TD backup updates weights};
  % loop back to the next roll
  \draw[->, black, thick] (move.north) .. controls (10.2,1.5) and (0,1.5) .. (roll.north)
    node[midway, above, font=\scriptsize, text=black] {next turn};
\end{tikzpicture}
$$

Started from random weights, early play was near-random and games ran for hundreds
of moves, but after a few dozen games performance climbed fast. TD-Gammon 0.0,
with a raw board encoding and _essentially zero_ backgammon knowledge, learned in
about 300,000 self-play games to match the best previous programs — programs stuffed
with hand-built expert features. Adding a small set of backgammon-specific input
features produced TD-Gammon 1.0, which beat every prior program and competed with
human experts. Later versions added a shallow two- or three-ply search over the
opponent's likely rolls, combining a learned value function with decision-time
lookahead — the same pairing AlphaGo would scale up. By the mid-1990s the program
played at or above the level of the world's best humans, and it changed how those
humans played certain openings.

> **Definition (Afterstate value).** A value function defined on the position
> _after_ the agent has moved but _before_ the environment's stochastic response.
> When many state–action pairs lead to the same afterstate (a dice roll, a
> checkers capture), evaluating afterstates shares learning across them and makes
> greedy move selection a simple comparison of resulting positions.

## Watson's Daily-Double wagering: RL for a sub-decision

Not every application asks a learner to play the whole game. IBM's Watson, which
won _Jeopardy!_ against human champions in 2011, is celebrated for its natural
language answering — but that is not the part that owes anything to reinforcement
learning. The reinforcement-learning component is a single sub-decision: how much
to **wager on a Daily Double**.[^sb-watson]

When Watson hit a Daily-Double square it had to bet before seeing the clue. Its
designers adapted the TD-Gammon recipe to learn a state-value function
$\hat v(\cdot, \mathbf{w})$ (the probability of an eventual win from a game state,
learned by a multilayer network trained with TD errors) over features specific to
_Jeopardy!_: the three players' scores, how many Daily Doubles remained, the value
of clues left. To turn that value into a bet it also estimated $p_{DD}$, the
in-category confidence that Watson would answer the upcoming clue correctly.
Watson then scored each legal bet by the expected afterstate value,

$$
\hat q(s, \textit{bet}) \;=\; p_{DD}\cdot \hat v(S_W + \textit{bet}, \ldots) \;+\; (1 - p_{DD})\cdot \hat v(S_W - \textit{bet}, \ldots),
$$

where $S_W$ is Watson's current score, and picked the bet with the largest action
value — an action value that equals the expected next-afterstate value.

$$
% caption: Watson's wager as an afterstate expectation. In-category confidence
% $p_{DD}$ splits each candidate bet into a correct branch (score up) and a wrong
% branch (score down); the learned value $v$ scores each resulting state and the
% bet maximizing the expectation is chosen.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=30mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc, thick] (bet) at (0,0) {candidate bet};
  \node[box] (up)   at (5.2,1.4)  {correct: score up\\value v(up)};
  \node[box] (dn)   at (5.2,-1.4) {wrong: score down\\value v(down)};
  \draw[->, acc, thick] (bet) -- (up) node[midway, above, sloped, font=\scriptsize, text=black] {prob p};
  \draw[->, red, thick] (bet) -- (dn) node[midway, below, sloped, font=\scriptsize, text=black] {prob 1-p};
  \node[box] (q) at (10.6,0) {q(s, bet) =\\expected value};
  \draw[->, black, thick] (up) -- (q);
  \draw[->, black, thick] (dn) -- (q);
\end{tikzpicture}
$$

For example, suppose Watson leads with
$S_W = 12{,}000$ against opponents at $9{,}000$ and $6{,}000$, and its in-category
confidence is $p_{DD} = 0.8$. Compare a cautious bet of $2{,}000$ against an all-in
bet of $12{,}000$. Reading approximate win probabilities off the learned $\hat v$: a
correct $2{,}000$ bet lifts Watson to $14{,}000$ with, say, $\hat v \approx 0.83$,
and a wrong one drops it to $10{,}000$ with $\hat v \approx 0.62$, so
$\hat q(s, 2000) = 0.8 \cdot 0.83 + 0.2 \cdot 0.62 = 0.664 + 0.124 = 0.788$. The
all-in bet swings further: correct takes Watson to $24{,}000$ and near-certain
victory, $\hat v \approx 0.97$, while wrong collapses it to $0$ and a poor position,
$\hat v \approx 0.15$, giving $\hat q(s, 12000) = 0.8 \cdot 0.97 + 0.2 \cdot 0.15 =
0.776 + 0.030 = 0.806$. On raw expected value the all-in bet edges ahead, $0.806$
versus $0.788$ — but its outcomes are spread across a huge range ($0.97$ down to
$0.15$), and subtracting a fraction of that spread as a risk penalty, exactly the
standard-deviation term the designers added, reverses the ranking and picks the
$2{,}000$ bet. That penalty is what keeps a single wrong answer on a Daily Double
from throwing away a winning game.

Two details matter. First, unlike TD-Gammon, Watson could _not_ learn $\hat v$ by
self-play: _Jeopardy!_ is a game of imperfect information — a contestant does not
know how confident opponents are — and self-play would explore states no human
match ever reaches, like poker against someone holding the same cards. So $\hat v$
was trained over millions of simulated games against carefully-built stochastic
models of human contestants. Second, maximizing the raw expected value "incurred a
frightening amount of risk," so the designers subtracted a fraction of the
standard deviation from each bet's value to damp catastrophic all-in wagers. In
simulation the learned strategy raised the win rate from 61% (a heuristic
baseline) to 67% — a large edge given that a Daily-Double bet arises only about
one or two times per game.

## Optimizing memory control: RL below the game layer

Reinforcement learning need not sit at the top of a system. İpek, Mutlu,
Martínez, and Caruana built a **DRAM memory controller** whose scheduling policy
is learned online, on the chip, while programs run.[^sb-memory] A memory controller
decides, at each cycle, which pending read/write request to service subject to a
thicket of timing constraints — a genuine scheduling problem that conventional
controllers attack with fixed heuristics that ignore past experience.

They cast it as an MDP: the state is the contents of the transaction queue, the
actions are the DRAM commands (_activate_, _precharge_, _read_, _write_, and a
_NoOp_ when nothing else is legal), and the reward is 1 whenever the action is a
_read_ or _write_ (the commands that actually move data) and 0 otherwise.
Transitions are stochastic because the next state depends on processor workloads
the scheduler cannot control.

$$
% caption: The reinforcement-learning DRAM controller as an MDP. The scheduler is
% the agent; its state is the transaction queue, its actions are DRAM commands,
% and its reward is 1 for a read or write that moves data. The agent learns
% online with Sarsa and linear tile-coding features.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=26mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc, thick] (sch) at (0,0) {scheduler\\(agent)};
  \node[box] (dram) at (5.6,0) {DRAM system\\(environment)};
  \draw[->, acc, thick] (sch.north) .. controls (2.0,1.5) and (3.6,1.5) .. (dram.north)
    node[midway, above, font=\scriptsize, text=black] {command: read / write / activate};
  \draw[->, black, thick] (dram.south) .. controls (4.6,-1.4) and (3.4,-1.4) .. (sch.south east)
    node[midway, below, font=\scriptsize, text=black] {queue state};
  \node[box] (rw) at (-2.6,-2.4) {reward = 1\\on read / write};
  \draw[->, red, thick] (rw) -- (sch.south west)
    node[midway, left=1mm, font=\scriptsize, text=red] {reward};
\end{tikzpicture}
$$

The scheduling agent used [Sarsa](/reinforcement-learning/tabular-methods/temporal-difference-learning)
with a linear action-value function over six integer features, approximated by
[tile coding](/reinforcement-learning/approximation/on-policy-prediction) with
hashing and ε-greedy exploration. One design detail: the features used to _learn_
values were not the ones used to define which actions were _legal_, so the
learner's exploration could never violate a hardware constraint. In simulation the
learned controller beat the best fixed policy (FR-FCFS) by 7% to 33% across nine
memory-intensive workloads (averaging a 19% speedup) and its ability to adapt
online was worth another 8% over a controller frozen after learning. The point is
not the numbers but the placement: the same value-and-reward machinery works two
levels below where anyone would call it "AI."

## DQN: human-level video game play

The deep Q-network (DQN) from Google DeepMind is the case study these notes have
already met in [deep Q-networks](/reinforcement-learning/deep-rl/deep-q-networks);
here it stands as the demonstration that _one_ learning system, unchanged, can
reach human level across a wide range of tasks.[^sb-dqn] DQN combined Q-learning
with a deep **convolutional** network and learned to play 49 Atari 2600 games from
raw pixels. Its weights were reset to random before each game, so it learned a
different policy for each, but the raw input, architecture, hyperparameters, and
algorithm were _identical_ for all of them. No per-game feature engineering.

DQN is the descendant of TD-Gammon on the video-game branch: both use a multilayer
network as a semi-gradient TD approximator with backpropagated gradients. The
differences are what made Atari tractable. Where TD-Gammon estimated afterstate
values (cheap in backgammon, where the rules give the post-move position), DQN
estimated **action values** $\hat q(s,a,\mathbf{w})$ directly, so it never needed a
model to generate next states. It used the semi-gradient form of **Q-learning**,

$$
\mathbf{w}_{t+1} \;=\; \mathbf{w}_t + \alpha\Big[R_{t+1} + \gamma\max_a \tilde q(S_{t+1},a,\mathbf{w}_t) - \hat q(S_t,A_t,\mathbf{w}_t)\Big]\nabla \hat q(S_t,A_t,\mathbf{w}_t),
$$

and — being off-policy — could reuse stored transitions. Three modifications
stabilized the notoriously fragile combination of bootstrapping, function
approximation, and off-policy updates — the
[deadly triad](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad):

- **Experience replay.** Each transition $(S_t, A_t, R_{t+1}, S_{t+1})$ is stored
  in a replay memory; updates draw minibatches sampled uniformly at random. This
  reuses experience, decorrelates successive updates, and cuts variance.
- **A target network.** The bootstrap target uses a _duplicate_ network $\tilde q$
  whose weights are frozen and only refreshed every $C$ steps, so the target does
  not chase the parameters being updated.
- **Reward clipping.** Score changes are mapped to $+1$, $-1$, or $0$, letting one
  step size work across games with wildly different score scales.

DQN reached or exceeded human level on 29 of the 46 games tested. Its failures —
Montezuma's Revenge, which needs long-horizon planning — marked the open problems.
But as a proof that deep networks can supply the features a
reinforcement learner needs, on tasks as varied as _Breakout_ and _Space
Invaders_, without a human touching the representation, DQN is the starting point
of modern deep RL.

## Mastering Go: AlphaGo

Go was the standing challenge. Its search space dwarfs chess — roughly 250 legal
moves per position against 35, games twice as long, but size is not the real
obstacle. The obstacle is that no one could write a good **position evaluation
function** for Go; Müller's 2002 verdict was that none would ever be found. AlphaGo,
from DeepMind, broke through by _learning_ that evaluation and pairing it with
search.[^sb-alphago]

AlphaGo learns a network that estimates who is winning and which moves look
promising, then uses those estimates to steer a search a few moves ahead. The
network narrows the search; the search sharpens the network's raw estimate.

Two ideas combine. The first is [Monte Carlo Tree Search](/reinforcement-learning/tabular-methods/planning-and-learning),
the decision-time planner from the tabular chapter: run many simulated games from
the current position, growing a search tree whose edges accumulate statistics (a
visit count $N$ and an action value $Q$) and, when time runs out, playing the most-
visited move from the root. Plain MCTS uses uniform-ish rollouts to evaluate leaves.
AlphaGo's contribution was to guide and replace those rollouts with **deep
networks learned by reinforcement learning**.

Three networks did the work. A **policy network** $p(a \mid s)$, a 13-layer
convolutional net, output a probability over legal moves; it was first trained by
_supervised_ learning to imitate nearly 30 million human expert moves (the "SL
policy"), then improved by policy-gradient reinforcement learning through self-play
(the "RL policy"). A separate **value network** $v(s)$, same shape but a single
output, estimated the probability of winning from a position; it was trained by
regression on the outcomes of self-play games generated by the RL policy. A small,
fast linear **rollout policy** supplied quick simulations. In the search, a newly
added leaf $s$ was evaluated by _mixing_ its value-network estimate with the return
$G$ of a rollout,

$$
v(s) \;=\; (1 - \eta)\,v_\theta(s) \;+\; \eta\,G,
$$

and the team found $\eta = 0.5$ — value network and rollouts weighted equally —
gave the best play, each covering the other's blind spots.

$$
% caption: AlphaGo's search. MCTS grows a tree from the current position; the
% policy network $p(a \mid s)$ biases which edges to expand, and each new leaf is
% scored by mixing the value network $v(s)$ with a fast rollout. Statistics N and
% Q accumulate on the edges, and the most-visited root move is played.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={circle, draw, fill=white, minimum size=5.5mm, inner sep=0pt},
  lf/.style={circle, draw, fill=black!8, minimum size=5mm, inner sep=0pt},
  box/.style={draw, minimum width=22mm, minimum height=8mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % the tree
  \node[st] (r) at (0,3.2) {};
  \node[st] (a) at (-1.4,2.0) {};
  \node[st] (b) at (0.2,2.0) {};
  \node[st] (c) at (1.6,2.0) {};
  \node[st] (d) at (0.2,0.8) {};
  \node[lf] (leaf) at (1.2,-0.4) {};
  \draw[black] (r) -- (a);
  \draw[acc, thick] (r) -- (b);
  \draw[black] (r) -- (c);
  \draw[acc, thick] (b) -- (d);
  \draw[acc, thick] (d) -- (leaf);
  \node[acc, anchor=west, font=\scriptsize] at (1.9,1.1) {N, Q on edges};
  % policy network guides expansion
  \node[box, draw=acc, text=acc] (pol) at (-3.8,0.6) {policy net};
  \draw[->, acc, thick] (pol) to[out=40, in=210] (b);
  \node[font=\scriptsize, text=black, anchor=north] at (-1.9,1.35) {bias expansion};
  % leaf evaluation: value net + rollout
  \node[box] (val) at (4.4,0.4)  {value v(s)};
  \node[box] (roll) at (4.4,-1.6) {rollout};
  \draw[->, black, thick] (leaf) -- (val);
  \draw[->, red, thick] (leaf) -- (roll);
  \node[font=\scriptsize, text=black, anchor=east] at (1.05,-0.55) {mix, back up};
\end{tikzpicture}
$$

AlphaGo defeated the European champion Fan Hui 5–0 and then, in 2016, the 18-time
world champion Lee Sedol 4–1 — a result experts had expected to be a decade away.
It is a descendant of TD-Gammon (self-play and a neural value function) and of DQN
(deep convolutional approximation), with MCTS supplying the decision-time search
that TD-Gammon only hinted at with its two-ply lookahead.

> **Definition (Policy and value networks).** Two deep networks that together let
> search evaluate positions no hand-built function could. The **policy network**
> $p(a \mid s)$ outputs a distribution over moves and biases which branches the
> search explores; the **value network** $v(s)$ estimates the probability of
> winning from a position and scores the leaves the search reaches.

## AlphaGo Zero: self-play from scratch

AlphaGo still leaned on people: its policy network was bootstrapped from 30 million
human moves. AlphaGo Zero removed that dependence. It used _no human data or guidance
beyond the rules_ — the "Zero" — and learned entirely from self-play, starting
from random weights.[^sb-alphagozero] It is both stronger and simpler, and it is
the purest statement of the through-line: value, self-play, and search, with
nothing borrowed from humans.

Three simplifications define it. **One network, not three:** a single "two-headed"
convolutional net $f_\theta$ takes a raw board $s$ and outputs both a move
distribution $\mathbf{p}$ and a scalar value $v$ — the policy and value networks
of AlphaGo fused into one body with two heads. **MCTS inside the training loop:**
where AlphaGo ran MCTS only during live play, AlphaGo Zero runs it during learning
too. And **no rollouts:** each MCTS simulation ends at a tree leaf scored by the
network's value head, not at the end of a simulated game.

The training loop is a form of [policy iteration](/reinforcement-learning/tabular-methods/dynamic-programming).
The network plays itself. At each position, MCTS — guided by the current $f_\theta$
— runs many simulations and returns an _improved_ move distribution $\pi$, better
than the network's raw $\mathbf{p}$ because the search looked ahead. The game plays
out to a winner $z$. Then the network is trained to make its policy head match
$\pi$ and its value head match $z$. Silver and colleagues put it exactly: MCTS acts
as a **policy-improvement operator**, and self-play under that operator drives the
whole system upward.

$$
% caption: AlphaGo Zero's self-play policy iteration. The network $f_\theta$
% guides MCTS, which returns an improved policy $\pi$ at each position; a game is
% played to a winner z, then $f_\theta$ is trained so its policy head matches
% $\pi$ (improvement) and its value head matches z (evaluation). No human data.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=26mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc, thick] (net) at (0,0) {network f\\p and v};
  \node[box] (mcts) at (4.6,0)  {MCTS search\\improved policy};
  \node[box] (play) at (9.2,0)  {self-play game\\winner z};
  \draw[->, acc, thick] (net) -- (mcts) node[midway, above, font=\scriptsize, text=black] {guides};
  \draw[->, acc, thick] (mcts) -- (play) node[midway, above, font=\scriptsize, text=black] {picks moves};
  % training arrow back to the network
  \draw[->, red, thick] (play.south) .. controls (9.2,-1.9) and (0,-1.9) .. (net.south)
    node[midway, below, font=\scriptsize, text=red] {train: match policy to search, value to z};
\end{tikzpicture}
$$

The result is decisive. Started from random play, AlphaGo Zero surpassed the
Lee-Sedol version of AlphaGo in three days and beat it 100 games to 0; a larger,
longer-trained version reached an Elo rating above 5,000, well past every prior
program and every human. Trained only against itself, it rediscovered classical
Go openings and then, in places, discarded them for moves no human had played.
This lesson followed the through-line through the game-playing systems. The same
skeleton reaches problems with no opponent at all — web personalization, a glider
learning to ride turbulent air, and the industrial-scale systems (AlphaStar, OpenAI
Five, GT Sophy, and RLHF) that carried it past Sutton & Barto — which continue in
[Reinforcement Learning Beyond Games](/reinforcement-learning/deep-rl/rl-beyond-games).

[^sb-samuel]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §16.2 — Samuel's Checkers Player: minimax search over a linear scoring polynomial, rote learning, and "learning by generalization," which updates a position's value toward the minimax value of a search one move later — the same idea as TD-Gammon — with the caution that Samuel's value function had no reward or terminal anchor.
[^sb-tdgammon]: **Sutton & Barto**, §16.1 — TD-Gammon: nonlinear TD(λ) with a multilayer network estimating win probability $\hat v(s,\mathbf{w})$, trained by self-play over afterstates (§6.8), reaching human-expert level from a raw board encoding (TD-Gammon 0.0) and beyond with added features and shallow search.
[^sb-watson]: **Sutton & Barto**, §16.3 — Watson's Daily-Double Wagering: a TD-Gammon-style value network $\hat v(\cdot,\mathbf{w})$ over _Jeopardy!_ features, combined with in-category confidence $p_{DD}$ to form action values $\hat q(s,\textit{bet})$ (16.2); trained against human models rather than by self-play (imperfect information), with a variance penalty to limit risk.
[^sb-memory]: **Sutton & Barto**, §16.4 — Optimizing Memory Control: İpek et al.'s DRAM scheduler as an MDP with commands as actions and reward 1 for read/write, learned online on-chip with Sarsa and tile-coding function approximation, outperforming the best fixed policy and benefiting from online adaptation.
[^sb-dqn]: **Sutton & Barto**, §16.5 — Human-level Video Game Play: DQN combines semi-gradient Q-learning (16.3) with a deep convolutional network over raw Atari frames; experience replay, a periodically-updated target network, and reward clipping stabilize training, giving human-level play on 29 of 46 games with one architecture and hyperparameter set.
[^sb-alphago]: **Sutton & Barto**, §16.6.1 — AlphaGo: APV-MCTS guided by an SL/RL policy network $p(a \mid s)$ and evaluating leaves by mixing a value network $v_\theta(s)$ with rollouts, $v(s) = (1-\eta)v_\theta(s) + \eta G$ (16.4), with $\eta = 0.5$ best; policy trained by supervision then policy-gradient self-play, value trained on self-play outcomes; defeated Fan Hui and Lee Sedol.
[^sb-alphagozero]: **Sutton & Barto**, §16.6.2 — AlphaGo Zero: a single two-headed network $f_\theta$ producing $(\mathbf{p}, v)$, trained purely by self-play policy iteration (§4.3) with MCTS as a policy-improvement operator inside the loop and no rollouts or human data; from random weights it exceeded all prior AlphaGo versions and every human, reaching Elo above 5,000.