RL 9: Superhuman Achievement in Games (1992–1999)

For about 30 years, strong backgammon players opened certain rolls the same way. It was in the books. Then a program that had never read a backgammon book said they were all wrong, and it turned out to be right.

In Blog 8 the Q-table hit a wall: one cell per situation, and real problems have more situations than atoms in the universe. The obvious fix was a neural network that guesses values for situations it has never seen. But theory said that mixing a neural network with TD updates might blow up. One researcher at IBM tried it anyway, on a board game with dice. This post covers what happened, how the math works, and why the trick was partly luck.

Where We Are, and Where We're Going

By the end of this post you'll be able to explain, in plain words:

1. Why backgammon (a game with dice) was a harder test for learning than chess.
2. How a neural network replaces the Q-table, with a step-by-step example using real numbers.
3. Where the weight-update formula comes from, and what an eligibility trace does to it.
4. What self-play is, and why "your opponent levels up with you" is such a powerful trick.
5. Why TD-Gammon stunned human experts, and why the same recipe didn't instantly work everywhere else.

Words from earlier blogs I won't re-explain: value function V(s) and TD error δ (Blog 7), eligibility traces, a.k.a. "breadcrumbs" (Blog 8), ε-greedy exploration and "model" (Blog 8). If any feel fuzzy, a quick skim of those posts will set you up.

New words in this post:

1. Why Backgammon?

Gerald Tesauro, a researcher at IBM, picked backgammon on purpose. Not because it was easy, but because it was awkward in exactly the ways that break the usual tricks.

Chess is deterministic. No dice. A program can look many moves ahead because the number of options per turn stays manageable: roughly 30–40 legal moves in chess, 8–10 in checkers. In backgammon every turn starts with a dice roll. There are 21 distinct rolls, each allowing around 20 legal moves, so several hundred branches per ply. Look-ahead search drowns almost immediately.

You only need three ideas to follow this post: it's a race around the board, you can hit a lone enemy checker and send it back to the start, and you can block with stacked checkers. Dice make every plan fragile, so even a position's value is a probability, not a verdict.

The old way: copy the experts

Tesauro had already tried the standard approach. His earlier program, Neurogammon, was trained by supervised learning (the "show it labeled examples" method) on recorded games by expert humans. It won the 1989 Computer Olympiad. But it had a ceiling, and the ceiling was the humans it copied. And experts aren't infallible: in backgammon and Othello, expert opinion had been substantially revised over the previous twenty years.

So he built a head-to-head experiment. Same designer, same kind of network, two teachers:

• Teacher A: expert-labeled examples (Neurogammon).
• Teacher B: nobody. The network plays itself and learns from who wins (TD-Gammon).

It was a gamble. Samuel tried self-play with checkers in the 1950s (Blog 4), and self-playing learners had a reputation for developing weird, brittle strategies that beat themselves but lose to everyone else.

2. The Recipe: How a Network Replaces the Table

Blog 8 ended with the table's fatal flaw. Backgammon has more than 10^20 positions, so a table with one cell per position is impossible. Tesauro's replacement was a plain multilayer perceptron: numbers go in one end, one guess comes out the other.

What goes in, what comes out

• Input: 198 numbers describing the board. Roughly: for every point (one of the 24 narrow slots checkers sit on), a few numbers saying how many checkers each player has there, plus a handful for checkers on the bar, checkers borne off, and whose turn it is. (The very first version used only this raw board. No strategy hints.)
• Hidden layer: 40 units in the first version, 80 in later ones.
• Output: the network's estimate of who's winning. Textbooks simplify this to one number, the probability of winning. Tesauro's actual network had four outputs, covering normal wins and "gammons" (landslide wins worth double) for each side.

That output is V(s, w): the value of board s, computed by a network whose dials (weights) are w.

Count the dials: 198 × 40 + 40 × 4 is roughly 8,000 weights. Eight thousand numbers standing in for 10^20 positions. That compression only works because the network generalizes: what it learns about one position carries over to thousands of near-twins. A table can't do that.

How it picks a move

Because the rules of backgammon are known, the agent doesn't need a Q-table. (Remember the "model" from Blog 8? In a board game with clean rules, you can write the map by hand.) On each turn it:

1. Rolls the dice.
2. Lists every legal move and the board each one would create.
3. Feeds each resulting board into the network.
4. Plays the move whose board has the best estimated outcome. Greedy. No ε-greedy, no random exploration.

No exploration at all? That should worry you after Blog 8. Section 3 explains why it works anyway: the dice do that job for free.

How it learns, part 1: one game, with numbers

Here's a toy game. The network scores four positions in a row, then the game ends in a win. Inside one game there's no reward until the end and we use γ = 1, so the TD error δ from Blog 7 boils down to next estimate minus this estimate.

Read the last row first. The network said "70% for me", and the game ended in a win. It was underconfident, so the surprise is positive. Notice that the only real information from the outside world is that final win. Everything else is the network comparing its own consecutive guesses (the "fix your guess with a better guess" idea from Blog 7).

How it learns, part 2: where the update rule comes from

The surprise tells us how wrong a guess was. How do we turn that into "turn these dials this way"? It's ordinary gradient descent (the same idea as Blog 6), with one twist.

First, what's a gradient? Take a tiny network, V = 0.2·x₁ + 0.5·x₂, and a board described by x = [2, 1]. Then V = 0.4 + 0.5 = 0.9. Nudge the first dial from 0.2 to 0.21 and V becomes 0.92: it moved by 0.01 × x₁ = 0.02. So the sensitivity of V to dial 1 is x₁ = 2, and to dial 2 it's x₂ = 1. The list of sensitivities [2, 1] is the gradient, written ∇_w V. A real network has about 8,000 dials, and backprop (Blog 6) computes that whole list efficiently.

Now the rule. We want the guess at position t to move toward the next guess, which is our "better guess". Measure the miss with a squared error, treating the target as a fixed number:

Its slope with respect to the dials is −(y_t − V_t) · ∇_w V_t. Stepping downhill (with step size α) gives:

Read it in words: turn each dial in proportion to (how surprised I was) × (how much that dial mattered). That's TD(0) with a neural network.

For the mathematically curious. We froze the target y_t while taking the slope, even though y_t itself depends on w. Because of that, this update is not the true gradient of any single fixed loss. Sutton and Barto call it a semi-gradient method. It's the reason the theory is harder than ordinary supervised learning, and it's the thread we pull in Section 5.

How it learns, part 3: adding the trace (and when things happen)

TD(0) only fixes the position that just happened. But a surprise at move 4 is partly the fault of moves 1 to 3. The eligibility trace (Blog 8's breadcrumbs) handles that. In a table the breadcrumbs sat on cells. A network has no cells, so they sit on the weights.

The update happens after every move, not after the game. Each trip around the loop touches two piles of numbers:

• The weights w: the network's actual brain (about 8,000 numbers).
• The trace e: a scratchpad the same length as w. A fading memory of "which dials were involved in my recent guesses". It starts at all zeros at the start of every game, and it never changes the network by itself. Only a surprise δ does that.

For each move t:

1. Forward pass. Rate the current board: V_t.
2. Gradient. Backprop gives g_t, the list of "how much did each dial matter".
3. Update the scratchpad. Fade the old memory, add the fresh footprint.
4. The move happens and the next board arrives. Rate it (or use the real result if the game just ended) and compute the surprise δ_t.
5. Turn the dials, each in proportion to its breadcrumb.

As formulas, one per step:

Notice that with λ = 0 the trace is just g_t, and the update collapses to the TD(0) rule we derived above. The trace is TD(0) plus memory.

Also notice the timing: δ_t needs the next board's rating, so move t's update lands the moment move t+1's board appears. That's why the update sits between positions, not at the end.

How it learns, part 4: run it on the toy game

To keep the vectors small, pretend the network has just 3 dials (w_a, w_b, w_c) instead of 8,000. The gradients are made up (move 1 touches dial a, move 2 touches b, moves 3 and 4 touch c), but the arithmetic is exactly the real algorithm. Settings: λ = 0.5 (old memory halves each step), α = 0.1.

(Rounded to three decimals; the totals use exact values.)

Two things to read off it:

• The trace column is the breadcrumb trail. After move 4, dial c (used by the late positions) carries big breadcrumbs (1.5), while dial a (used only in position 1) carries a faint one (0.125).
• The last column is where it pays off. Dial a was only involved in position 1, yet the late good news still reached it. That's credit assignment traveling backward through time.

What the trace actually changed. Compare with λ = 0 (plain TD(0)), where each move only touches its own gradient:

Look at dial b. Without a trace, position 2's dial gets punished, because its own next-step surprise was negative (−0.10). With a trace, it also hears the later news: the game was won, and position 2 was on the path to that win. The final verdict flips the sign.

The food-critic version: you eat ten courses and get a stomachache. TD(0) blames only the last dish. TD(λ) spreads the blame backward, most to the last course, less to each earlier one.

Online vs offline. You could save up all four rows of the last column and apply them together after the game (offline TD(λ)). You'd still add up every row, not just the last one. TD-Gammon updated after each move (online), so later guesses in the same game already benefit from earlier lessons.

For the mathematically curious. There's a second way to read λ. Instead of breadcrumbs looking backward, imagine each position looking forward: it forms the target "look n steps ahead, then trust my own estimate" for every n, and averages them with weights that decay by λ:
G_t^λ = (1 − λ) · Σ_{n≥1} λ^(n−1) · G_t^(n).
At λ = 0 that's the one-step TD(0) target. At λ = 1 it's the full Monte Carlo return from Blog 7. So λ is a smooth dial between "bootstrap from the next guess" and "wait for the real outcome". The trace is the backward view that achieves the same averaging online, without having to store the future. The two views give the same total update (exactly in the offline case, closely in the online case).

Two roles, to keep straight: TD decides what the target should be when nobody gives you labels (Blog 7). Backprop decides how to turn the dials to move toward that target (Blog 6). TD-Gammon is those two ideas bolted together.

3. Self-Play and the "Infinite Curriculum"

Tesauro started the network with random weights, which means random play. Both sides played randomly, against each other, and the only feedback was who won.

Early games were absurd. Random backgammon can run for hundreds or even thousands of moves, compared to about 50–60 plies in a normal human game. And yet the network learned. In the first few thousand games it picked up the basics: hit the opponent, avoid leaving lone checkers exposed, build solid structures. Subtler ideas showed up after tens of thousands of games.

Why the opponent never gets too easy or too hard

Because the agent plays itself, its opponent is always exactly as strong as it is. The moment it discovers a slightly better strategy, its opponent (itself) uses that strategy too. Difficulty rises automatically with ability. Researchers later called this an infinite curriculum: a training setup that adjusts its own difficulty, with no human designing lesson plans.

It's the same loop AlphaGo Zero used in 2017, playing millions of games against itself (4.9 million, per the paper) starting from random moves.

The dice are secretly doing the exploring

Remember ε-greedy from Blog 8? The deal was: you need random moves or you'll never discover better options. TD-Gammon had none, and it worked anyway. Tesauro's explanation: the dice already randomize which positions the agent visits. Every game wanders through different territory whether the player wants to or not. A deterministic game like chess would need some other source of randomness, or self-play can get stuck replaying one narrow style forever.

5. Plot Twist: Why Didn't It Copy-Paste to Chess and Go?

If a neural network trained by TD and self-play could master backgammon, surely chess and Go were next? They weren't. A major 1996 survey of RL noted that no success close to TD-Gammon's had been repeated.

Three explanations emerged, and the third one is where the math comes back.

Explanation 1: Backgammon was a uniquely friendly game. Tesauro himself listed reasons (we met the first one already):

1. The dice provide exploration for free. (Remember the worry from Section 1 that self-play learners get brittle? In a deterministic game, a self-player can settle into one narrow style that looks great against itself and falls apart against anyone else. Random dice keep knocking it into new positions.)
2. Games always end, even with random play. (A deterministic game can loop forever, and then the network never sees a final result to learn from.)
3. The true value of a position is smooth: a small change to the board nudges the win probability slightly, instead of flipping between "win" and "lose".

Explanation 2: Maybe TD wasn't even the star. In 1996–98, Jordan Pollack and Alan Blair ran a provocative follow-up titled "Why did TD-Gammon work?" They trained a small network (about 4,000 parameters) with plain hill-climbing evolution: no backprop, no reinforcement learning, no TD. It still reached a competitive backgammon level. Their hypothesis: much of the success came from the setup (co-evolving players against each other) and the dynamics of backgammon itself. TD-Gammon still got further, so this didn't erase Tesauro's achievement. But it was a warning that "RL + neural net" wasn't a magic recipe yet.

Explanation 3: The math says it shouldn't have been safe. Remember the semi-gradient twist from Section 2: we froze the target while taking the slope. That's fine for tables. With a function approximator, three ingredients can combine badly. Sutton and Barto later named the combination the deadly triad:

With all three present, value estimates can diverge: instead of settling toward the right answer, they grow without bound.

TD-Gammon had two of the three. It learned about its own play, so it was on-policy. That's one plausible reason it got away with it, though nobody has proven that's the whole story. It sat on a lucky island, and the surrounding waters were rough.

6. What TD-Gammon Left Behind

For backgammon. By 1995, rollouts by TD-Gammon were regarded as the most reliable way to analyze checker plays, and opening theory had been rewritten.

For RL. It was the first large-scale success of RL with a nonlinear function approximator, and the blueprint for what came next. The stability problem it dodged is exactly the plot of DQN (Blog 11): DeepMind's real contribution was making this combination stable, not inventing it. And its self-play loop was an early example of the recipe later used in AlphaGo Zero.

An open question. Why did it work? Dice, smoothness, on-policy luck, or the setup? Researchers were still arguing about it years later, which is what makes it such a good puzzle.

Cheat Sheet

• TD-Gammon = a neural network V(s, w) trained by TD(λ) through self-play; the first big proof that function approximation + RL can work at scale.
• Update rule = turn each dial by α × (surprise) × (breadcrumb). With λ = 0 it's TD(0); the trace adds memory.
• Semi-gradient = we freeze the target while taking the slope, so it isn't a true gradient of a fixed loss.
• Self-play = you are your own sparring partner, so difficulty rises with your skill (an infinite curriculum).
• Why it worked on backgammon: dice (free exploration), games always end, smooth values, and on-policy learning. Maybe the setup mattered too.
• Deadly triad = function approximation + bootstrapping + off-policy. TD-Gammon had two of three.
• Honest caveat: later versions added hand-made features and a short search, and the result didn't transfer to chess or Go.

What's Coming Next

TD-Gammon worked, but the theory says value-based methods with function approximation can fail to converge. So what if we skip the value function and improve the policy directly?

That's Blog 10.

Sources and Further Reading

• G. Tesauro, "Temporal Difference Learning and TD-Gammon", Communications of the ACM, 1995 (the primary source for the architecture, scores, and the opening-play story).
• G. Tesauro, "Practical Issues in Temporal Difference Learning", Machine Learning, 1992.
• J. Pollack, A. Blair, "Why did TD-Gammon Work?", NIPS 1996.
• Sutton and Barto, Reinforcement Learning: An Introduction (TD-Gammon case study; semi-gradient methods; the deadly triad).
• J. Tsitsiklis, B. Van Roy, "An Analysis of Temporal-Difference Learning with Function Approximation", 1997.
• R. Sutton, D. McAllester, S. Singh, Y. Mansour, "Policy Gradient Methods for Reinforcement Learning with Function Approximation", NIPS 1999.