TD-Gammon
In plain wordsA backgammon program built at IBM in the early 1990s that taught itself to play at near world-champion level by playing more than a million games against itself.
A backgammon program that learned its own evaluation function by TD(λ)temporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches. from games against itself, built by Gerald Tesauro at IBM's Thomas J. Watson Research Center. A multilayer neural networkneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain. took an encoding of the board (later versions added hand-designed features) and estimated the probabilities of the possible outcomes; after each move its weights were nudged toward its own next prediction, with the actual result as the final target. Without expert games, versions trained on roughly 300,000 to 1.5 million self-play games reached strong master level, close to the best human players, and its unconventional opening choices changed how experts played. TD-Gammon was the first widely publicized success of reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time. with neural function approximation, two decades before the deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level., and a direct inspiration for later self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples. systems; early attempts to repeat it in chess and Go failed, which some attribute to backgammon's dice providing natural exploration.
Like TD-Gammon, the agent learned purely from games against itself, starting from random weights.
Origin
Described by Gerald Tesauro in 'Practical Issues in Temporal Difference Learning' (Machine Learning, 1992) and 'TD-Gammon, a Self-Teaching Backgammon Program, Achieves Master-Level Play' (Neural Computation, 1994), with a retrospective in Communications of the ACM (1995). The name joins 'TD' (temporal difference) with the '-gammon' of backgammon, echoing Tesauro's earlier supervised-learning program Neurogammon, winner of the 1989 Computer Olympiad.
Related
- temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches.
- self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.
- deep reinforcement learningdeep reinforcement learning, n.: Reinforcement learning in which a large neural network does the learning, letting an AI learn tasks such as video games or robot control directly from raw inputs like screen pixels or camera images.
- rolloutrollout, n.: Letting an AI play out a task with its current strategy, from some starting point to the end, to see how things turn out and gather data for learning or planning.
- AlphaZeroAlphaZero, prop. n.: A 2017 DeepMind program that taught itself chess, shogi and Go from nothing but the rules by playing against itself, and within hours of training beat the strongest existing programs.
Sources
- Tesauro, G. (1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM 38(3), 58–68.
- Tesauro, G. (1994). TD-Gammon, a Self-Teaching Backgammon Program, Achieves Master-Level Play. Neural Computation 6(2), 215–219.
Mentioned in
reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time., deep reinforcement learningdeep reinforcement learning, n.: Reinforcement learning in which a large neural network does the learning, letting an AI learn tasks such as video games or robot control directly from raw inputs like screen pixels or camera images., rolloutrollout, n.: Letting an AI play out a task with its current strategy, from some starting point to the end, to see how things turn out and gather data for learning or planning., self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples., temporal difference learningtemporal difference learning, n.: A way of learning predictions by adjusting each guess toward the next, slightly better-informed guess instead of waiting for the final outcome — like revising a weather forecast every day as the date approaches., Gerald TesauroGerald Tesauro, prop. n.: An American IBM researcher whose program TD-Gammon learned backgammon purely by playing against itself and by the early 1990s rivaled the best human players, a landmark for machines that learn by trial and error., Samuel's checkers programSamuel's checkers program, prop. n.: A 1950s IBM program by Arthur Samuel that learned to play checkers better than its author, partly by playing against itself. It was among the first programs to learn, and its 1959 paper popularized the phrase 'machine learning'.