TD-Gammon

From Neurogammon to learning without a teacher

Before TD-Gammon, Gerald Tesauro had built Neurogammon at IBM: a neural network that learned from a database of recorded games by expert backgammon players, using hand-crafted features. In 1989, Neurogammon won the backgammon championship at the International Computer Olympiad, reaching a strong intermediate level. But that kind of learning required a ready-made database of labeled expert games, which doesn't exist for every domain.

Tesauro wanted to test whether a network could learn with no teacher at all. In the first TD-Gammon network, the weights started out completely random, and the network received only the raw position of the checkers on the board, with no hand-crafted features whatsoever. It played 200,000 games against itself, with 40 hidden units, using temporal difference learning. By Tesauro's own account, the result reached a level roughly comparable to Neurogammon, with no hand-crafted features and no expert games as examples at all. Only in later versions, starting with version 1.0, did Tesauro add the same set of backgammon features that Neurogammon had used, to improve performance further.

How it worked: temporal difference learning

The algorithmic basis for the method had been worked out earlier by the researcher Richard Sutton at GTE Laboratories, but Tesauro was the first to apply it at large scale. TD-Gammon's network takes the board state as input: 198 input units encoding each player's checker count at each location on the board, and, from version 1.0 on, a handful of precomputed features. After every move, the network compares the evaluation it gave the previous state to the evaluation it gives the new state, and updates its weights to shrink the gap between the two evaluations — hence the name "temporal difference." The game's actual result arrives only at the end, but the network doesn't wait for it in order to learn: the evaluation itself gradually improves, move after move. From version 1.0 on, the network had 80 hidden units. Version 2.0, from 1992, added a two-ply search (its own move and the opponent's reply), version 3.0, from 1995, deepened the search to three plies, and the last version, 3.1, had 160 hidden units.

The real test: against the world's best players

In late 1991, the first version, TD-Gammon 1.0, played 51 games against three of the strongest players in the world — Bill Robertie, Paul Magriel, and Malcolm Davis (then rated 11th in the world) — and lost by a total of 13 points, about a quarter point per game on average. In 1992, at the World Cup of Backgammon tournament, version 2.0, with a two-ply search, played 38 exhibition games against top players, among them Kit Woolsey and former World Champion Joe Russell. According to IBM's own account, it finished 19–19 on games won, and by Tesauro's account its total point deficit was only seven. In 1993, version 2.1 played 40 games against Bill Robertie. By Tesauro's own account, Robertie trailed TD-Gammon for the entire session and won only the final game — so the final margin between them was just a single point, in TD-Gammon's disfavor. In 1995, version 3.0, with a three-ply search, won a 25-point match against Neil Kazaross, a master-level player, and Tesauro estimated its level as about 0.07 to 0.08 points per game stronger than version 2.1 on average. The last version, 3.1, from 1998, was trained on more than 6 million games, with 160 hidden units; over 100 games against Malcolm Davis it lost by eight points, mainly because of a single doubling blunder: TD-Gammon chose to double the stakes, lost that game by a gammon, and gave up 32 points in it.

The move Tesauro never programmed: changing opening theory

One of TD-Gammon's most significant moments wasn't a win in a single game, but a change in backgammon opening theory itself. For decades, experts had believed that for three common opening rolls — 2-1, 4-1, and 5-1 — the right play was "slotting": moving a checker from the 6-point to the 5-point. An analysis published in 1992 in an article by Bill Robertie in Inside Backgammon, based on TD-Gammon's evaluations, showed that splitting the back checkers (24-23) was superior. Leading tournament players adopted the split, and by Tesauro's own account it "quickly gathered more adherents" until it became "the near-universal choice," while slotting "virtually disappeared from tournament competition." Another backgammon expert, Kit Woolsey, wrote that there was "no question" in his mind that its positional judgment was "far better than mine," and that its judgment on bold vs. safe play decisions was "nothing short of phenomenal." At the same time, the achievement wasn't complete: Bill Robertie found minor technical errors in its endgame play, which Tesauro expected a deeper search to eliminate, and minor errors in doubling decisions, an area the network was never trained on at all: doubling-cube decisions were added only after training, using a theoretical formula.

Why it's considered a turning point in reinforcement learning

TD-Gammon is cited again and again in reinforcement learning literature as one of the first demonstrations that a neural network can learn a complex task from scratch, purely by playing against itself — with no expert database and, in its first version, no hand-crafted features at all. TD-Gammon itself was never turned into a commercial product, but it inspired commercial backgammon programs based on neural networks, such as JellyFish (1994) and Snowie (1998). Today, as AI agents learn to play through trial and error — from DeepMind's DQN to AlphaGo and AlphaZero — they follow in the footsteps of the demonstration TD-Gammon already gave in the early 1990s: that a neural network can teach itself a strategy that, in some situations, is better even than the judgment of human experts.