TD-Gammon — The Self-Taught Backgammon Program That Changed Human Play

TD-Gammon was a backgammon program developed by Gerald Tesauro at IBM's Thomas J. Watson Research Center. Rather than learning from the games of human masters, its neural network played against itself over and over and learned how good a position was from the outcomes of those games. The learning method was Richard Sutton's TD(λ) (temporal-difference learning), and Sutton and Barto's textbook counts the program among the most impressive applications of reinforcement learning. The first paper appeared in the journal Machine Learning in May 1992, and in the same year a version with two-ply look-ahead played exhibition games against top players at a world tournament. TD-Gammon's judgement rewrote human opening theory, and its method of learning through self-play leads on to AlphaGo and AlphaZero.

The 1992 paper — learning from zero knowledge

In the abstract of "Practical issues in temporal difference learning" (Machine Learning vol. 8, pp. 257–277, May 1992), Tesauro writes that he examined whether temporal-difference methods such as Sutton's TD(λ) could train neural networks successfully on complex real-world problems. The test case was learning backgammon from the outcome of self-play, which the abstract calls apparently the first application of the algorithm to a complex, non-trivial task. With zero knowledge built in, the network learned the entire game from scratch to a fairly strong intermediate level — clearly better than conventional commercial programs, and better even than comparable networks trained on a massive data set of human expert play.

Behind it lay Tesauro's own earlier program. According to his 1995 article in Communications of the ACM, Neurogammon was trained with backpropagation on a database of recorded expert games and included a few hand-crafted features in its input. It won the backgammon championship at the 1989 Computer Olympiad but played only at a strong intermediate level. Whether a machine could get past the limits of being taught human knowledge was the question TD-Gammon asked.

How it learned

The network took a board position as input and output its estimate of the chances of White or Black winning a normal game or a gammon (a double win). In each game, the difference between the prediction for one position and the prediction for the next was treated as the error, and the weights were nudged to reduce it; estimates for earlier positions were corrected too, with an influence that decays over time. The only final reward was the result of the game. No teacher said which moves had been good.

The CACM article reports that in the first few thousand training games the networks learned elementary strategies such as hitting the opponent, playing safe and building new points, and that more sophisticated concepts emerged after several tens of thousands of games. Larger networks and more training brought substantial improvements. Tesauro observed that the learned weights contained patterns a knowledge engineer would call useful features, and presented this as an example of automatic "feature discovery".

The second edition of Sutton and Barto's textbook Reinforcement Learning summarises the versions as follows.

On the basis of these results and analyses by grandmasters, the textbook concludes that version 3.0 appeared to play close to, or possibly better than, the best human players in the world.

According to the CACM article, version 1.0 played 51 games in late 1991 against former world champions Bill Robertie and Paul Magriel and against Malcolm Davis, then the world's 11th-highest-rated player, losing about a quarter of a point per game. Version 2.0, which added a two-ply search, made its public debut at the 1992 World Cup of Backgammon, where it lost only 7 points over 38 exhibition games against players including Kent Goulding, Kit Woolsey and former world champion Joe Russell.

Human theory changed

TD-Gammon's influence showed less in its own strength than in how people played. The CACM article explains that for opening rolls of 2-1, 4-1 or 5-1, the near-universal choice of experts for about 30 years had been "slotting": moving a single checker from the 6 point to the 5 point. When Robertie's article on TD-Gammon appeared in Inside Backgammon in 1992, it included a rollout analysis showing the slot to be inferior to splitting the back checkers with 24-23. A few top players tried the split, had some notable tournament successes, and it gathered adherents; by the time of the 1995 article, splitting had become the near-universal choice and slotting had virtually disappeared from tournament play.

In a written evaluation sent to Tesauro, the leading player Kit Woolsey wrote: "There is no question in my mind that its positional judgment is far better than mine." In the same evaluation he noted that in some positions, such as building a board with no opposing contact, a human calculating it out can often find the better play.

According to Sutton and Barto, the impact on human play was greatly accelerated when self-teaching neural-network programs inspired by TD-Gammon — Jellyfish, Snowie and GNU Backgammon — became widely available, spreading the new knowledge the networks had generated and greatly improving the overall calibre of human tournament play. The textbook also notes that backgammon is played throughout the world, with numerous tournaments, and is a popular vehicle for wagering significant sums of money. Here, early on, the usual relationship was reversed: instead of the machine learning from human experts, human experts relearned their game from the machine.

Afterwards — Watson and AlphaGo

Tesauro carried the method into later work. According to Sutton and Barto, the strategy that IBM's Watson used for "Daily Double" wagering when it beat human champions on a quiz show in 2011 was created by Tesauro and colleagues by adapting TD-Gammon.

The path of learning games through self-play and reinforcement runs from Samuel's checkers program of 1959 through TD-Gammon to AlphaGo in 2016 and AlphaZero, which used no human games, in 2017. Tesauro himself, though, pointed in his 1995 article to a property of backgammon as one ingredient of the success. The randomness of the dice varies the positions seen in training, so even self-play explores a wide range of the game. In deterministic games, he wrote, a system training by self-play could end up exploring only a narrow part of the state space and settle on a poor strategy. AlphaGo and AlphaZero combine self-play reinforcement learning with Monte Carlo tree search; how each works is explained on its own page.