How did TD-Gammon teach itself to play backgammon at a master's level?

Most game programs before the 1990s were taught by people. Programmers sat with experts, turned their advice into rules and scores, and hoped the computer would play like a master. Gerald Tesauro, a researcher at IBM's Thomas J. Watson Research Center in New York, tried something different with backgammon. He gave a neural network the rules, let it play against itself, and let it work out on its own what a good position looks like.

The result, TD-Gammon, is one of the clearest early examples of a machine learning a hard skill from its own experience. Tesauro first reported it in 1992 and described it in detail in Communications of the ACM in March 1995.

Why backgammon was hard for computers

Backgammon is a race. Two players roll dice and move their checkers in opposite directions around a track; the first to bring all checkers home and off the board wins. Two features make it subtle. A lone checker (a "blot") can be hit and sent back to the start, and players can build walls of checkers that block the opponent. There is also a "doubling cube" that lets a player raise the stakes.

The dice are the real obstacle for a computer. In chess, a program can look many moves ahead. In backgammon, each turn has 21 possible dice rolls with about 20 legal moves each, so there are several hundred possibilities per move, and looking deep ahead is out of reach. A program must instead judge positions well, as a strong human does by feel.

Tesauro had already tried teaching that feel the conventional way. His earlier program, Neurogammon, learned from a database of expert games and won the backgammon event at the 1989 Computer Olympiad, but it only reached a strong intermediate level.

How TD-Gammon learned

TD-Gammon's brain is a neural network: layers of simple units joined by adjustable connections called weights. It takes in a description of the board and outputs four numbers, its estimates of the chances that White or Black will win normally or win double (a "gammon").

Training followed a simple loop:

1. Start with random weights, so the network's judgment is pure noise.
2. For each move, score every legal option with the network and pick the one it rates best, for whichever side is moving.
3. After each move, compare the network's new estimate of the position with its previous one, and nudge the weights so the earlier estimate moves toward the later one.
4. At the end of the game, nudge the last estimate toward the actual result.
5. Repeat for hundreds of thousands of games.

Step 3 is temporal difference learning, a family of methods named by Richard Sutton; the version used here is called TD(lambda). At first the games were absurd. With random play, a game could drag on for hundreds or thousands of moves, compared with 50 to 60 in human play. Yet within a few thousand games, the network picked up basics such as hitting the opponent and playing safe, and deeper ideas appeared after tens of thousands.

Here is how the program grew:

What it changed

Robertie, a former world champion, judged that version 2.1 played at a strong master level, within a few hundredths of a point per game of the best humans, and that its steadiness might make it the favorite over a long session. Its weak spots were endgames and doubling decisions; the doubling strategy was added after training rather than learned.

The most striking effect was on human play. For about 30 years, when the first roll of a game was 2-1, 4-1 or 5-1, experts had almost always shifted a single checker down from their 6 point onto their 5 point, a risky play called "slotting." TD-Gammon preferred splitting its back checkers instead. After Robertie published the program's analysis in 1992, top players tried the split, won with it, and slotting all but vanished from tournaments. Kit Woolsey, one of the game's leading analysts, found its positional judgment better than his own.

Tesauro also stressed what TD-Gammon meant for AI research. Reinforcement learning, where a learner improves from rewards rather than from a teacher's right answers, had few large successes before it. TD-Gammon showed that combining it with a neural network could work on a complex real problem. Later work on game-playing networks, including DeepMind's papers on AlphaGo, cites it.

What is temporal difference learning, in plain words?

Imagine forecasting the weather for Saturday. On Monday you say 70 percent chance of sun. On Tuesday the forecast changes to 50 percent. You do not need to wait until Saturday to learn something: Tuesday's forecast, made with more information, already tells you Monday's was a bit too hopeful. Temporal difference learning adjusts each guess toward the next, better-informed guess, and only the final guess is checked against what really happened.

That solves a classic puzzle called credit assignment. In a long game, the only clear signal is the result at the end. Which of the fifty moves deserves the credit or blame? By comparing each position's estimate with the next one, the method passes the final result backward through the game, a little at a time.

The "lambda" in TD(lambda) controls how far back each correction reaches. A larger lambda spreads a surprise over more of the earlier positions; a lambda of zero corrects only the immediately preceding one. TD-Gammon showed that this simple rule, repeated over enough self-played games, can grow judgment that rivals human experts.