The final lecture is a case study. We look at how reinforcement learning surpassed humans in classic games like checkers, chess, Othello, backgammon, Go, and poker. Games have simple rules yet deep concepts, they have been honed for hundreds or thousands of years, and they make a meaningful test of intelligence. In Silver’s words, they are the drosophila of artificial intelligence. Just as the fruit fly is genetics’ standard model organism, games are a laboratory that compresses real-world problems into something small. And above all, games are fun.

Lecture slides: PDF

Where we have gotten to

The lecture opens with a scoreboard. Checkers has been solved to perfect play, chess, Othello, backgammon, Scrabble, and poker are at superhuman level, and Go was (as of this lecture) at grandmaster level. The programs that set each summit are Chinook (checkers), Deep Blue (chess), Logistello (Othello), TD-Gammon (backgammon), Maven (Scrabble), MoGo/Crazy Stone/Zen (Go), and Polaris (poker).

What is interesting is the second table next to it. If you pick out “which program reached this summit with reinforcement learning,” the list shifts slightly. In chess, KnightCap and Meep replace Deep Blue, and in poker, SmooCT replaces Polaris. A chess program that reached top level with reinforcement learning alone was still only around international master strength, while for most of the rest reinforcement learning took the top spot. This lecture follows precisely that reinforcement learning lineage.

Game theory: best response and Nash equilibrium

In a game with several players, what is an “optimal policy”? It is not a problem for me alone, since there is an opponent, so what is optimal depends on what the opponent does.

The key observation is this. If every other player fixes their own policy $\pi^{-i}$, then in that moment the opponents are no longer intelligent adversaries but simply part of the environment. If the opponent is a wall that only moves by fixed rules, what remains is the problem of maximizing my reward alone against that wall. That is, the game reduces to a single MDP. My best response $\pi^{i}_*(\pi^{-i})$ is then exactly the optimal policy of that MDP. The multiplayer game folds down into a single-agent reinforcement learning problem.

Now, if everyone does their best simultaneously, what state do we arrive at? There is a joint policy $\pi$ that bundles together every player’s policy, and

$$\pi^{i} = \pi^{i}_*(\pi^{-i}) \quad \text{for all } i$$

that is, when each player’s policy is a best response to everyone else’s, no one can gain by unilaterally changing. This state is the Nash equilibrium.

Here the lecture’s first big picture appears. The Nash equilibrium is the fixed point of self-play reinforcement learning. Multiple agents play each other and accumulate experience ($a^1 \sim \pi^1$, $a^2 \sim \pi^2$, …), and each learns a best response to the others. But since one player’s policy determines another’s environment, everyone adapts to one another simultaneously. The point where this game of tag stops, the fixed point where no one has anything more to change, is exactly the Nash equilibrium.

Among these, the lecture focuses on a special class, the two-player zero-sum game. Two players move alternately (call them White and Black), and Black’s and White’s rewards are exactly opposite, so $R^1 + R^2 = 0$. As much as I win, the opponent loses. The two branches for finding the Nash equilibrium in this game are game-tree search (planning) and self-play reinforcement learning, and those two are the backbone of this lecture.

There is one more axis. If the board is fully visible, it is a perfect-information (Markov) game (chess, checkers, Othello, backgammon, Go). If the opponent’s hand is hidden, it is an imperfect-information game (Scrabble, poker). We start with perfect-information games.

The classic solution for two-player zero-sum games is minimax. Given a joint policy $\pi = (\pi^1, \pi^2)$, the value function is as always $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$. The minimax value function maximizes White’s expected return while minimizing Black’s expected return.

$$v_*(s) = \max_{\pi^1} \min_{\pi^2} v_\pi(s)$$

The joint policy that achieves this value is the minimax policy. And here is the second bridge the lecture points to. The minimax policy is a Nash equilibrium. This means the earlier game theory and the search here point to the same place. The minimax value function is unique.

The minimax value is computed by depth-first game-tree search. On my turn choose the value to be maximal, on the opponent’s turn minimal, and carry values up from the leaves to the root. Historically this idea was proposed by Claude Shannon in his 1950 paper “Programming a Computer for Playing Chess.” There was no computer, so it was run on paper.

The problem is that the tree explodes exponentially. Reading all the way to the end is realistically impossible. So we read only to a certain depth, and approximate the value of the leaf nodes below with a value-function approximator $v(s, \mathbf{w}) \approx v_*(s)$. This is called the evaluation function or the heuristic function. Minimax search descends to a fixed depth and then carries values up based on the approximate values at the leaves.

Binary-linear value function

The simplest and yet most powerful form for scoring leaves is the binary-linear value function. The lecture’s concluding recipe ultimately converges on this one line, so this is the backbone of the lecture.

We build a binary feature vector $\mathbf{x}(s)$ with one feature per piece (for example, “is this piece on this square,” as 0 or 1). Each component of the weight vector $\mathbf{w}$ is the value of that piece. Then the board’s evaluation is the sum of the weights of the active features.

$$v(s, \mathbf{w}) = \mathbf{x}(s) \cdot \mathbf{w}$$

In chess terms, if I have a pawn it is $+1$, if the opponent has a knight it is $-3$, and you sum the weights of the active features into a single score. The old intuition of a person assigning “piece values” by hand is expressed exactly as a single linear function. This simple frame runs through the entire lecture.

Deep Blue

Deep Blue is a case of pushing this frame to the extreme by human hand.

  • Knowledge: a binary-linear value function with about 8000 handcrafted chess features. Most of the weights were tuned by human experts.
  • Search: high-performance parallel alpha-beta search. With 480 chess-specific VLSI chips it read 200 million positions per second and looked 16 to 40 plies ahead.
  • Result: in 1997 it defeated world champion Garry Kasparov 4 to 2. It was the most-watched event in internet history at the time.

Deep Blue has no reinforcement learning. It is the pinnacle of handcraft, an overwhelming search laid on top of a human-written evaluation function.

Chinook

Chinook, for checkers, was also of the hand-tuning family at first.

  • Knowledge: a binary-linear value function. It used 21 knowledge-based features (position, mobility, etc.), split across the game’s four phases.
  • Search: high-performance alpha-beta search. On top of it it added retrograde analysis. Searching backward from won positions, it stored every winning position in a lookup table. Then the endgame, with only a few pieces left, is played perfectly.
  • Result: in the 1994 match against world champion Marion Tinsley it won 2 games, and Tinsley resigned for health reasons.

Then in 2007, Chinook solved checkers completely. It is perfect play that does not lose even against God. One point of caution here. The heart of this solved Chinook is the hand-tuned weights and the endgame database from retrograde analysis, not the TD leaf learning that comes later. TD leaf is a matter of a later version that was added afterward (it comes up again in a later section).

Self-play reinforcement learning

Now, instead of a person writing the evaluation function, let us have it learned by reinforcement learning. We update the value function $v(s, \mathbf{w})$ from experience gained by playing against oneself. The prediction algorithms seen in Lecture 4 apply directly.

  • MC: update toward the return $G_t$. $\Delta\mathbf{w} = \alpha(G_t - v(S_t, \mathbf{w}))\nabla_\mathbf{w} v(S_t, \mathbf{w})$
  • TD(0): update toward the next-state value $v(S_{t+1})$. $\Delta\mathbf{w} = \alpha(v(S_{t+1}, \mathbf{w}) - v(S_t, \mathbf{w}))\nabla_\mathbf{w} v(S_t, \mathbf{w})$
  • TD(λ): update toward the λ-return $G_t^\lambda$. $\Delta\mathbf{w} = \alpha(G_t^\lambda - v(S_t, \mathbf{w}))\nabla_\mathbf{w} v(S_t, \mathbf{w})$

Self-play is appealing because the curriculum rolls along on its own. Since the opponent is myself, as my skill rises the opponent grows stronger too. There is no need for a person to design an endlessly increasing difficulty.

Improving the policy with afterstates

Here there is a shortcut peculiar to games. In deterministic games it is enough to learn only $v_*(s)$. There is no need to separately learn the state-action value $q_*(s, a)$.

The reason lies in the afterstate. Since the game rules already determine the successor state $\text{succ}(s, a)$, the value of action $a$ equals the value of the board that action produces.

$$q_*(s, a) = v_*(\text{succ}(s, a))$$

Since I can know immediately how the board turns out when I make a move, given only the rules, there is no need to learn “the value of a move”; I only need to learn “the value of a board.” So actions are chosen to maximize (or minimize, if it is the opponent) the afterstate value.

$$A_t = \arg\max_a v_*(\text{succ}(S_t, a)) \quad (\text{White}), \qquad A_t = \arg\min_a v_*(\text{succ}(S_t, a)) \quad (\text{Black})$$

This single choice improves both White’s and Black’s joint policies at once.

Othello’s Logistello

What is impressive about Logistello is that it built its features on its own. Starting from raw input features like “is there a black disc on C1,” it wove them together with logical AND and OR into new features. In this way, with different configurations, it made up to 1.5 million features, and laid a binary-linear value function on top.

Learning was generalized policy iteration. Generate a batch of self-play with the current policy, evaluate the policy by Monte-Carlo regression on the outcomes (win/loss), and then make a new player by greedy improvement. The result: it beat world champion Takeshi Murakami 6 to 0.

Backgammon’s TD-Gammon

TD-Gammon is the most famous milestone in this lecture. Here a nonlinear neural network, rather than a linear function, evaluated the board.

  • Initialize with random weights (zero prior knowledge).
  • Learn by self-play.
  • Use nonlinear temporal-difference learning. $\delta_t = v(S_{t+1}, \mathbf{w}) - v(S_t, \mathbf{w})$, $\Delta\mathbf{w} = \alpha\delta_t \nabla_\mathbf{w} v(S_t, \mathbf{w})$.
  • It did only greedy policy improvement (no exploration).

There is one peculiar point here. Even though it learned by pure greedy with no exploration mechanism, it actually always converged. In theory it seems there should have to be exploration, but in backgammon it was fine. The reason is the dice. Since the dice sprinkle randomness on every move, the board scattered into variety on its own without the algorithm exploring separately. The lecture also notes that “this was not the case in other games.”

The result is summarized as a single ladder of knowledge.

  • Zero expert knowledge $\Rightarrow$ intermediate strength
  • Add handcrafted features $\Rightarrow$ advanced strength (1991)
  • 2-ply search $\Rightarrow$ strong master level (1993)
  • 3-ply search $\Rightarrow$ superhuman strength (1998)

And in 1992, it beat world champion Luigi Villa 7 to 1. A ladder climbed with no knowledge, playing only against itself.

In TD-Gammon, simple greedy action selection during learning was enough. But unfortunately this did not work everywhere. Chess is a representative example.

Running the previous section’s approach, simple TD (updating the current value with the next-state value) game by game, success and failure diverged. In Othello (Logistello) and backgammon (TD-Gammon) superhuman levels came out, but in chess and checkers the results were poor.

Why? Because chess requires tactics to find a signal on the board. For example, checkmate is hard to notice from the board alone without search. A board that looks well placed collapses into a mate a few moves later, and a static evaluation function cannot see that. The conclusion is this. You should learn not from the value of the next state, but from the value obtained by search.

Here three siblings appear. The single key that distinguishes them is “what is updated toward what.”

TD root

TD root updates the current state’s value with the next state’s search value. It computes a search value at the root position $S_t$.

$$v_+(S_t, \mathbf{w}) = \min\max_{s \in \text{leaves}(S_t)} v(s, \mathbf{w})$$

And it pulls the current value toward the next state’s search value. $v(S_t, \mathbf{w}) \leftarrow v_+(S_{t+1}, \mathbf{w}) = v(l_+(S_{t+1}), \mathbf{w})$. Here $l_+(s)$ is the leaf node that achieves the minimax value at $s$.

This is Samuel’s checkers player (1959), the first TD learning algorithm in history. It learned by self-play and beat amateur humans. It also used other ideas that look odd today.

TD leaf

TD leaf updates the current search value with the next step’s search value. Unlike TD root, it computes search values in both places, now and next.

$$v_+(S_t, \mathbf{w}) \leftarrow v_+(S_{t+1}, \mathbf{w}) \quad\Longrightarrow\quad v(l_+(S_t), \mathbf{w}) \leftarrow v(l_+(S_{t+1}), \mathbf{w})$$

Chess’s KnightCap is this method. Training against expert opponents, starting from standard piece values, it learned the weights with TD leaf. Laying standard improvements on top of alpha-beta search, it reached master level in few games. But there were two limitations. It did not work well in self-play, and it did not work well unless it started from good initial weights.

The story deferred earlier closes here. Chinook, for checkers, originally used hand-tuned weights, but a later version trained by self-play and tuned the weights with TD leaf (while keeping only the piece values fixed). The self-play weights learned this way performed as well as or better than the hand-tuned weights, that is, at superhuman level. This is why it was stressed earlier that “the solved Chinook is not TD leaf.” TD leaf is the story of this later version.

TreeStrap

TreeStrap updates a search value with a deeper search value at the same time step. Unlike TD root/leaf, which learned across time (with the next step’s value), TreeStrap pulls the values of every node in the tree toward the search value right there, within the same step.

$$v(s, \mathbf{w}) \leftarrow v_+(s, \mathbf{w}) \quad\Longrightarrow\quad v(s, \mathbf{w}) \leftarrow v(l_+(s), \mathbf{w}), \quad \forall s \in \text{nodes}(S_t)$$

Chess’s Meep is this method. It tuned a binary-linear value function of 2000 features, starting from random initial weights (zero prior knowledge), with TreeStrap. And it went beyond KnightCap’s two limitations. It was effective in self-play, and it was effective from random initial weights. The result was 13 wins and 15 losses against international masters, or rather 13/15 wins.

Replacing search with simulation

Going one step further, self-play reinforcement learning can take the place of search itself. Simulate self-play from the root state $S_t$, and apply reinforcement learning to that simulated experience. Monte-Carlo control laid onto the tree in this way is Monte-Carlo tree search (MCTS), and the most effective variant is UCT, which weighs exploration against exploitation with UCB at each node.

Here Lecture 8 and this lecture connect. Self-play UCT converges to the minimax value (in perfect-information, zero-sum, two-player games). MCTS gave the best performance in many hard games such as Go (last lecture), Hex, Lines of Action, and Amazons. Meanwhile, in some games simple Monte-Carlo search without building a tree was enough (Scrabble, backgammon).

Maven is easy to mistake as the representative case of imperfect information, but in this lecture Maven is placed as a case of that “simple Monte-Carlo search.”

  • Learning: evaluate a move by score + $v(\text{rack})$. Here $v(\text{rack})$ is a binary-linear value function that scores the value of the tiles left in hand (the rack), using one-letter, two-letter, and three-letter features (like Q??????, QU?????, III????). It was learned by Monte-Carlo policy iteration like Logistello.
  • Search: roll out imagining $n$ steps of self-play to spread out a move, and evaluate the resulting board by score + $v(\text{rack})$. Score each move by the average rollout evaluation and play the highest move. The endgame is handled by dedicated search with the B* algorithm.

As a result, Maven beat world champion Adam Logan 9 to 5. In one game it predicted it would finish the endgame with MOUTHPART, and analysis showed an error of only about 3 points per game.

Reinforcement learning in imperfect-information games

Now for games where the board is not fully visible. When the opponent’s hand is hidden, as in poker, each player knows something different and holds a different search tree. The key tool is the information state. For each information state we place one node that summarizes what a player knows, like “what cards have I seen so far.” In practice several different physical states share the same information state, and states with similar values are further grouped.

There are two branches for solving this information-state game tree.

  • Iterative forward search: representatively, counterfactual regret minimization (CFR). It essentially solved heads-up limit Texas hold’em completely.
  • Self-play reinforcement learning: representatively, Smooth UCT. It won 3 silver medals in 2-player and 3-player limit hold’em, outperforming large-scale forward-search agents.

Smooth UCT

Smooth UCT is a UCT variant that applies MCTS to the information-state game tree, inspired by fictitious play from game theory. The key is that it responds to the opponent’s average behavior. It extracts an average strategy from the action counts at each node.

$$\pi_{\text{avg}}(a \mid s) = \frac{N(s, a)}{N(s)}$$

And at each node it chooses an action with probability $\eta$ by UCT as usual, and with probability $1 - \eta$ by this average strategy $\pi_{\text{avg}}$.

$$A \sim \begin{cases} \text{UCT}(S), & \text{prob. } \eta \\ \pi_{\text{avg}}(\cdot \mid S), & \text{prob. } 1 - \eta \end{cases}$$

Why does this matter? In the poker variants, naive MCTS diverged. Chasing a constantly changing target as opponents kept shifting, they oscillated among themselves. Smooth UCT, by contrast, responds to the stable target of the opponent’s average strategy and converged to the Nash equilibrium. This lecture, which began from game theory, comes back around to game theory’s fixed point.

What runs through it all: one recipe

The lecture’s conclusion is astonishingly simple. The recipe for success was almost the same across games. Line up chess (Meep), checkers (Chinook), Othello (Logistello), backgammon (TD-Gammon), Go (MoGo), Scrabble (Maven), and limit hold’em (SmooCT) in one table, and the commonalities stand out.

  • Binary features: piece, pawn, disc placement, number of pieces left, stone patterns, letters on the rack, card abstractions. The target differs by game, but the form is uniformly binary.
  • Value function: almost all linear (only TD-Gammon’s neural network is the exception).
  • Self-play: learning was mostly done by playing against oneself (only KnightCap added expert opponents on the side).

Binary features + linear value function + self-play. The answer that different people arrived at in different games converges on this single one, and that is the picture this lecture leaves. How to weave minimax search into it (alpha-beta, TD leaf, TreeStrap, MCTS) was merely each game’s individuality.

To add just one thing, AlphaGo and AlphaZero, which came after this lecture, are direct descendants of exactly this lineage, self-play and MCTS (projects Silver himself led). By weaving policy/value neural networks and tree search with self-play they conquered Go, so it amounts to laying deep learning on top of the backbone this lecture built. That said, this is a follow-up outside the scope of the slides, so here it is noted in just one sentence.

With this, the ten lectures following Silver’s course come to a close. From here the series moves on, as foreshadowed in the resources post, to more recent methods including PPO.