TD-Gammon: Learning backgammon from its own games

The event and the narrow claim

In 1992 Gerald Tesauro, a research staff member at IBM's Thomas J. Watson Research Center, reported that a neural network had learned to play backgammon close to the level of human experts by playing games against itself. An early account appeared in Tesauro's paper on practical issues in temporal difference learning in the proceedings of the 1991 NIPS conference, and an expanded version ran in the May 1992 issue of Machine Learning, the same issue that carried Watkins and Dayan's convergence proof for Q-learning. Version 2.0 of the program, TD-Gammon, made its public debut at the 1992 World Cup of Backgammon, and Tesauro's retrospective in the March 1995 Communications of the ACM is the account later researchers cite.

The documented claim has three layers that should be kept apart. First, a network given only a raw encoding of the board, with no backgammon knowledge built in, learned from its own games to play about as well as the best earlier programs. Second, the same training method applied to a network that also received hand-crafted features produced a program well beyond any previous one, close to strong human tournament play. Third, later versions, with far more training and a little lookahead search, were judged by leading players to be near the very top of human play. The first two layers rest on automated tests of thousands of games; the third rests on a few dozen games against people and on expert opinion. The broader historical claim, that TD-Gammon showed reinforcement learning with neural networks could master a hard problem and became a template for self-play systems two decades later, is supported by what later researchers wrote, but it was not obvious at the time, and the method did not travel easily.

Backgammon before a program taught itself

Backgammon was a poor fit for the methods that worked in chess. As Tesauro explained in 1995, each turn offers 21 distinct dice combinations with about 20 legal ways to play each, so the game tree branches several hundred ways per ply, against roughly 30 to 40 in chess. Deep brute-force search was out of reach, so programs depended on static positional judgment: a function that looks at a position and estimates how good it is. The strongest earlier program, Hans Berliner's BKG, was built from expert knowledge in the 1970s and won a short match against the reigning world champion in 1979, though by later estimates it played at roughly a very strong intermediate level.

Tesauro's own previous program took a different route. Neurogammon was a neural network trained by backpropagation to imitate moves from a database of recorded expert games, with a few hand-designed features in its input, and it won the backgammon event at the 1989 Computer Olympiad. That approach had a ceiling built in: the network could only be as good as the human judgments it copied, and Tesauro noted that expert opinion in backgammon had itself been revised heavily over the preceding twenty years. TD-Gammon asked whether a network could skip the teacher and learn from the outcomes of games it generated itself, using the temporal-difference methods Richard Sutton had formalized in 1988.

Sutton's prediction rule inside a game-playing network

Sutton's paper introduced temporal-difference learning as a way to learn predictions from the difference between successive predictions, rather than waiting for the final outcome. His example was a forecaster predicting each day of the week whether it will rain on Saturday: a conventional learner compares every forecast with Saturday's weather, while a temporal-difference learner adjusts Monday's forecast toward Tuesday's. Sutton proved convergence and optimality only for special cases, and he pointed out that the idea had an ancestor in Arthur Samuel's checkers player.

TD-Gammon put that rule inside a multilayer network. Sutton and Barto's textbook account describes the input of the early versions: 198 units encoding how many checkers of each color sit on each of the 24 points, plus checkers on the bar and borne off and whose turn it is, feeding one hidden layer of 40 to 80 units. The outputs estimated the probabilities of the possible results, including gammons. To play, the program generated every legal move for the current roll, ran each resulting position through the network, and chose the one it rated best for the side to move. It made the moves for both players. After each move it applied TD(λ): the gap between the network's estimate of the current position and its estimate of the next one was propagated back through the weights by backpropagation, with the parameter λ controlling how far back in the game each correction reached. At the end of a game the actual result served as the final target. The 1991 paper reports settling on a learning rate of 0.1 and a λ of 0.7 after some tuning.

Nothing in that loop required a human example. The doubling cube, central to money play, was not learned at all; a separate formula from the 1970s turned the network's outcome estimates into doubling decisions.

What the network found in its own games

Tesauro expected the knowledge-free version to serve as a baseline at best. Random networks played games lasting hundreds or thousands of moves, and theory gave no assurance that a nonlinear learner trained on its own shifting play would converge at all. Instead, the results reported in 1991 showed substantial learning. Measured against Gammontool, a Sun Microsystems program representative of commercial play, the best self-taught network won 66.2 percent of games, while an otherwise identical network trained on more than 15,000 expert-labelled positions won 59.4 percent. In a direct 10,000-game match the self-taught network beat the imitation network 55 to 45 percent, and a further 10,000 games against Neurogammon came out even.

The training budget was modest by later standards but large for a workstation. Networks with 40 hidden units needed about 200,000 games, and the largest took two weeks on an IBM RS/6000. Inspecting the weights, Tesauro found hidden units that behaved like a racing detector and an attacking detector, structure nobody had specified, and he presented this as progress on the old problem of automatic feature discovery that Samuel had been unable to solve. The 1995 account adds that the network learned simple, essentially linear concepts first (hitting, playing safe, making points) and context-dependent ones later, such as the way the value of the 7 point depends on where the other checkers stand.

When Neurogammon's hand-built features were added to the input, the same method produced an 80-hidden-unit network with over 25,000 weights, trained on more than 300,000 games over more than a month of CPU time. It won 73 percent against Gammontool and nearly 60 percent against Neurogammon, and in a day-long session against the two-time world champion Bill Robertie it won 13 of 31 games. A contemporary report in Computer Business Review in October 1992 described the program running on an RS/6000 that could play some 300,000 games a month.

From exhibition matches to master level

The versions that followed traded on more training and a little search. Tesauro's 1995 table lists them. Version 1.0, trained on 300,000 games, lost 13 points over 51 games in late 1991 against Robertie, Paul Magriel and Malcolm Davis. Version 2.0 had 800,000 training games and a 2-ply search that considered the opponent's possible replies; in 38 exhibition games at the 1992 World Cup of Backgammon it lost a net 7 points, and Computer Business Review reported the series as a 19-19 draw in games. Version 2.1, trained on 1.5 million games, lost by a single point over 40 games to Robertie, who trailed for the whole session until the final game. Sutton and Barto add that the final versions, 3.0 and 3.1, used a selective three-ply search, and that version 3.0 won 6 points over 20 games against Kazaros, one of the world-class players Tesauro tested it against.

The qualitative verdicts were more striking than the scores. Robertie judged version 2.1 to be within a few hundredths of a point per game of the best humans, with remaining weaknesses in endgame technique and some cube decisions. Kit Woolsey, then among the highest-rated players in the world, analysed dozens of its games with computer rollouts and wrote that its positional judgment was far better than his own, while humans kept an edge in technical positions that could be calculated out. These are informed opinions relayed by the program's author, not controlled measurements, and over a few dozen games the dice dominate the score. They are still the best evidence the period offers, and they came from players with reputations to protect.

How a program rewrote the opening book

The most concrete change TD-Gammon made to the human game concerned the first move. With an opening roll of 2-1, 4-1 or 5-1, experts had for decades usually played the slot, moving one checker from the 6 point to the 5 point and accepting a high chance of being hit for the chance of making a strong point. When Robertie published an article on the program in Inside Backgammon in 1992, it included a rollout (playing a position to the end thousands of times with different dice) in which TD-Gammon judged the slot inferior to splitting the back checkers from the 24 point to the 23 point. For the 4-1 roll, the 1995 article reports a 10,000-game rollout giving the slot an equity of -0.040 and the split +0.005. A few top players tried the split, did well with it, and by Tesauro's 1995 account slotting had almost disappeared from tournament play.

The opening was one example among many. Tesauro described a position from the final of the 1988 World Cup in which the world's top-rated player, with three expert commentators agreeing, made the natural play, while a TD-Gammon rollout preferred an unorthodox one by nearly a tenth of a point, part of a broader revaluation of the 17 point as an advanced anchor. Rollouts by strong neural programs became the accepted way to settle such arguments, and Sutton and Barto note that the effect on human play accelerated when programs inspired by TD-Gammon, such as Jellyfish, Snowie and GNU Backgammon, became widely available.

Those successors also refined TD-Gammon's own verdicts. A 2006 survey of the opening rolls by Tom Keith, based on rollouts by GNU Backgammon at its strongest setting, still favoured the split for 4-1 (+0.0024 against -0.0063) and for 5-1 (+0.0056 against -0.0031), but by margins far smaller than TD-Gammon had estimated, and it put the 2-1 slot narrowly back on top (+0.0088 against +0.0045). The lasting change was less a single answer than a method: opening theory came to be settled by machine rollouts.

Why it worked in backgammon and stalled elsewhere

Tesauro offered reasons for the success, and they doubled as reasons for caution. In his 1995 analysis, the network's estimates were often off by a tenth of a point or more, yet it chose moves well, because the candidate positions in any one decision are similar and their errors largely cancel. The dice forced variety into self-play, so the learner saw far more of the game than a deterministic self-play loop would; even random games ended, because checkers mostly move forward; and the expected outcome of a backgammon position changes smoothly, unlike the win, loss or draw value of a chess position. He predicted that chess and Go would need some external source of noise, and that a linear first approximation would be much weaker there.

Others pushed harder on the point. Jordan Pollack and Alan Blair trained a network of about 4,000 weights by simple hill-climbing, nudging a champion network toward any randomly mutated challenger that beat it, and reached a player that won about 40 percent against Pubeval, a public program Tesauro had trained on expert preferences. They argued that TD-Gammon's success owed more to the co-evolutionary setup and the dynamics of backgammon than to temporal-difference learning. Tesauro replied that their results fell well short of his 1992 networks and that hill-climbing captured only a roughly linear approximation of good play, a limit TD learning did not share.

Attempts in other games bore out the caution. Schraudolph, Dayan and Sejnowski found that a direct adaptation to 9x9 Go, with randomness injected into move choice because Go has no dice, needed 659,000 self-play games just to edge past a weak public program; they did much better only with networks shaped to the board and exposure to competent opponents. Sebastian Thrun's NeuroChess won about 13 percent of games against GNU Chess, played poor openings, and leaned on a database of 120,000 expert games. KnightCap did reach master-level ratings on an internet chess server, rising from 1650 to 2150 in 308 games, but it combined TD learning with game-tree search, and its authors credited play against online opponents rather than self-play. Theory added a warning: Tsitsiklis and Van Roy proved convergence for linear TD learning on sampled trajectories and gave an example of divergence with a nonlinear approximator. By 2013 DeepMind's Atari paper described a widespread belief that TD-Gammon's approach was a special case that worked only in backgammon.

The line to DQN, AlphaGo and AlphaZero

That same paper is the clearest evidence of TD-Gammon's later influence. Mnih and colleagues called TD-Gammon perhaps the best-known success story of reinforcement learning and named its architecture, a network updated directly from on-policy experience, as the starting point for their own. Their deep Q-network changed the ingredients that had blocked progress: Q-learning over actions instead of a learned state value, a convolutional network reading raw pixels, and experience replay instead of purely online updates.

The game line ran through Monte Carlo search as well as learning. In 1996 Tesauro and Gregory Galperin used TD-Gammon and weaker players as base policies for real-time Monte Carlo rollouts on IBM SP1 and SP2 parallel machines, cutting error rates by as much as a factor of 5. The 2016 AlphaGo paper cites both that work and TD-Gammon; its networks were trained by a combination of supervised learning on human expert games and reinforcement learning from self-play, and they guided a Monte Carlo tree search. AlphaGo Zero in 2017 dropped the human data and listed backgammon among the earlier self-play successes, while noting that those systems had relied on handcrafted input features. AlphaZero then applied one self-play recipe to chess, shogi and Go, the deterministic games where the TD-Gammon method had stalled, and it added noise to its search priors to keep self-play exploring, the remedy Tesauro had predicted deterministic games would need. IBM reused the approach closer to home: Sutton and Barto describe how Tesauro and colleagues trained the value function behind Watson's Jeopardy! wagering with the TD-Gammon method, although against simulated human opponents rather than by self-play.

The honest limits

TD-Gammon's strongest results did not come from learning alone. The knowledge-free network matched earlier programs; the near-expert versions used Neurogammon's hand-designed features, and the best later versions added lookahead search and a doubling formula that was never learned. Sutton and Barto make the general point that the impressive reinforcement learning demonstrations of that era still needed input features handcrafted for the problem. The evidence for human-level play is also thin by modern standards: a few dozen games per version, dominated by dice, with expert verdicts conveyed through the author's own article.

Access was limited too. The method was published in detail, but Pollack and Blair observed that IBM treated the trained weights as a trade secret, and the program reached the public as a game in IBM software bundles such as the Family FunPak for OS/2 Warp announced in August 1995, whose marketing copy said it had revolutionized backgammon. Independent replication therefore meant retraining from scratch. Finally, backgammon was a gift to the method: a fully observable game that is cheap to simulate and has randomness built in. Tesauro noted in 1995 that applications such as robot control or financial trading would lose the ability to simulate the whole environment and generate unlimited experience.

How to place TD-Gammon in AI history

TD-Gammon is best read as the first convincing demonstration that a neural network trained by temporal-difference learning on its own play could reach expert level in a complex domain, and as a result whose generality was overestimated at first and underestimated afterwards. It extended Samuel's idea of learning an evaluation function through self-play, replaced his linear function and expert-chosen features with a network that partly found its own, and showed on one architecture that learning from experience could beat learning from human examples. It also changed how strong players play and analyse a game with a large competitive following.

For two decades the method did not transfer, for reasons identified early: deterministic games starve self-play of exploration, value functions in chess and Go are less smooth, and nonlinear TD learning lacked guarantees. The later systems that did carry it forward, from DQN to AlphaZero, kept the core loop of a network that judges positions and learns from outcomes it generates, and supplied by design what backgammon had supplied for free: exploration, search and far more computation. Placed that way, TD-Gammon is neither a curiosity nor the sole parent of what followed. It is the proof of concept that kept the idea alive through the years when it looked like a special case.

References

• Tesauro (1991). Practical Issues in Temporal Difference Learning (NIPS 4).
• Tesauro (1992). Practical Issues in Temporal Difference Learning (Machine Learning 8).
• Tesauro (1995). Temporal Difference Learning and TD-Gammon.
• Sutton (1988). Learning to Predict by the Methods of Temporal Differences.
• Watkins and Dayan (1992). Q-learning.
• Sutton and Barto (2018). Reinforcement Learning: An Introduction, second edition.
• Computer Business Review (1992). IBMer Teaches Neural Network to Teach Itself Backgammon.
• IBM (1995). Get Warped with the Family FunPak for OS/2 Warp.
• Pollack and Blair (1996). Why did TD-Gammon Work?.
• Tesauro (1998). Comments on Co-Evolution in the Successful Learning of Backgammon Strategy.
• Schraudolph, Dayan and Sejnowski (1993). Temporal Difference Learning of Position Evaluation in the Game of Go.
• Thrun (1994). Learning to Play the Game of Chess.
• Baxter, Tridgell and Weaver (1999). KnightCap: A chess program that learns by combining TD(lambda) with game-tree search.
• Tsitsiklis and Van Roy (1997). An Analysis of Temporal-Difference Learning with Function Approximation.
• Mnih et al. (2013). Playing Atari with Deep Reinforcement Learning.
• Tesauro and Galperin (1996). On-line Policy Improvement using Monte-Carlo Search.
• Silver et al. (2016). Mastering the game of Go with deep neural networks and tree search.
• Silver et al. (2017). Mastering the game of Go without human knowledge.
• Silver et al. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm.
• Keith (2006). How to Play the Opening Rolls.