Temporal difference learning and TD-Gammon

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Temporal difference learning and TD-Gammon

Full text

Pdf (4.47 MB)

Source

Communications of the ACM archive
Volume 38 , Issue 3 (March 1995) table of contents

Pages: 58 - 68

Year of Publication: 1995

ISSN:0001-0782

Author

Gerald Tesauro

IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 171, Citation Count: 90

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/203330.203343 What is a DOI?

Warning: The download time has expired please click on the item to try again.

ABSTRACT

Ever since the days of Shannon's proposal for a chess-playing algorithm [12] and Samuel's checkers-learning program [10] the domain of complex board games such as Go, chess, checkers, Othello, and backgammon has been widely regarded as an ideal testing ground for exploring a variety of concepts and approaches in artificial intelligence and machine learning. Such board games offer the challenge of tremendous complexity and sophistication required to play at expert level. At the same time, the problem inputs and performance measures are clear-cut and well defined, and the game environment is readily automated in that it is easy to simulate the board, the rules of legal play, and the rules regarding when the game is over and determining the outcome.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Berliner, H. Computer Backgammon Sci. Amer. 243, 1, (1980), 64-72.
	2	Susan L. Epstein, Toward an Ideal Trainer, Machine Learning, v.15 n.3, p.251-277, June 1994 [doi>10.1023/A:1022637925775]
	3	Scott E. Fahlman , Christian Lebiere, The cascade-correlation learning architecture, Advances in neural information processing systems 2, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	4	Tom E. Fawcett , Paul E. Utgoff, Automatic feature generation for problem solving systems, Proceedings of the ninth international workshop on Machine learning, p.144-153, July 1992, Aberdeen, Scotland, United Kingdom
	5	K. Hornik , M. Stinchcombe , H. White, Multilayer feedforward networks are universal approximators, Neural Networks, v.2 n.5, p.359-366, 1989 [doi>10.1016/0893-6080(89)90020-8]
	6	Isabelle, J.-F. Auto-apprentissage, a paide de research de neurones, de fonctions heuristic utilities dans les. jeux strageties Master's thesis.. Univ of Montreal, 1993
	7	Magreal,P. Backgammon, Times Books, Newyork, 19736.
	8	Robertie. B, Carbonm Versus silicon: Matching wits with TD-Gammon. Inside Backmonnom 2, 2, (1992), 14-22.
	9	D. E. Rumelhart , G. E. Hinton , R. J. Williams, Learning internal representations by error propagation, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
	10	Samuel, A. Some studies in machine learning using the game of checkers Ibm J. of Research and Deveopment 3. (1959), 210-229
	11	Schraudolph, N.N. DAyan P. and Sjnoeski, Tj> Temporal difference learning of positoin evaluation in the game of Go. In J. D, Cowan, el al. Eds., Advances in Neural Information Processing Systems 6, 817-824.Morgan Kaufmann, San Mateo, Calif 1994
	12	Shannon, C.E Programming aComputer for Playing Chess. Philosophical Mag,41, (1950), 265-275.
	13	Richard S. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, v.3 n.1, p.9-44, August 1988 [doi>10.1023/A:1022633531479]
	14	Tesauro, G. Neurogammon wins Computer Olympiad. Neura Computation-I, (1989),321-323.
	15	Gerald Tesauro, Practical Issues in Temporal Difference Learning, Machine Learning, v.8 n.3-4, p.257-277, May 1992 [doi>10.1007/BF00992697]
	16	Zadeh, N, and Kobiska, G. On optima doubing in backgammon, Manage, sci. 23 (1977), 853-858.

CITED BY 90

	Sašo Džeroski , Luc De Raedt , Kurt Driessens, Relational Reinforcement Learning, Machine Learning, v.43 n.1-2, p.7-52, April-May 2001
	Jon Doyle , Thomas Dean, Strategic directions in artificial intelligence, ACM Computing Surveys (CSUR), v.28 n.4, p.653-670, Dec. 1996
	Dimitrios Kalles , Panagiotis Kanellopoulos, On verifying game designs and playing strategies using reinforcement learning, Proceedings of the 2001 ACM symposium on Applied computing, p.6-11, March 2001, Las Vegas, Nevada, United States
	Bruno Bouzy , Tristan Cazenave, Computer Go: an AI oriented survey, Artificial Intelligence, v.132 n.1, p.39-103, October 2001
	Christopher D. Rosin , Richard K. Belew, A competitive approach to game learning, Proceedings of the ninth annual conference on Computational learning theory, p.292-302, June 28-July 01, 1996, Desenzano del Garda, Italy
	Gerald Tesauro, Programming backammon using self-teaching neural nets, Artificial Intelligence, v.134 n.1-2, p.181-199, January 2002
	Daphna Joel , Yael Niv , Eytan Ruppin, Actor-critic models of the basal ganglia: new anatomical and computational perspectives, Neural Networks, v.15 n.4, p.535-547, June 2002
	James F. Swafford, II, Optimizing parameter learning using temporal differences, Eighteenth national conference on Artificial intelligence, p.965-966, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Michael Buro, Improving heurisitic mini-max search by supervised learning, Artificial Intelligence, v.134 n.1-2, p.85-99, January 2002
	Shiu-li Huang , Fu-ren Lin, Designing intelligent sales-agent for online selling, Proceedings of the 7th international conference on Electronic commerce, August 15-17, 2005, Xi'an, China
	Timothy Huang, The game of go: an ideal environment for capstone and undergraduate research projects, ACM SIGCSE Bulletin, v.35 n.1, January 2003
	Dimitar Kazakov , Daniel Kudenko, Machine learning and inductive logic programming for multi-agent systems, Mutli-agents systems and applications, Springer-Verlag New York, Inc., New York, NY, 2001
	Brian Sheppard, World-championship-caliber Scrabble, Artificial Intelligence, v.134 n.1-2, p.241-275, January 2002
	Philippe Preux , Samuel Delepoulle , Jean-Claude Darcheville, A generic architecture for adaptive agents based on reinforcement learning, Information Sciences—Informatics and Computer Science: An International Journal, v.161 n.1-2, p.37-55, 5 April 2004
	Dehu Qi , Ron Sun, A multi-agent system integrating reinforcement learning, bidding and genetic algorithms, Web Intelligence and Agent System, v.1 n.3-4, p.187-202, March 2003
	Roni Khardon, Learning to Take Actions, Machine Learning, v.35 n.1, p.57-90, April 1999
	Darse Billings , Aaron Davidson , Jonathan Schaeffer , Duane Szafron, The challenge of poker, Artificial Intelligence, v.134 n.1-2, p.201-240, January 2002
	Eric B. Baum, Toward a Model of Intelligence as an Economy of Agents, Machine Learning, v.35 n.2, p.155-185, May 1999
	Kurt Driessens, Relational reinforcement learning, Mutli-agents systems and applications, Springer-Verlag New York, Inc., New York, NY, 2001
	Rich Bateman, Training a multi-layer feedforward neural network to play Othello using the backpropogation algorithm and reinforcement learning, Journal of Computing Sciences in Colleges, v.19 n.5, p.296-297, May 2004
	C. Ribeiro, Reinforcement Learning Agents, Artificial Intelligence Review, v.17 n.3, p.223-250, May 2002
	Jonathan Dinerstein , Parris K. Egbert, Fast multi-level adaptation for interactive autonomous characters, ACM Transactions on Graphics (TOG), v.24 n.2, p.262-288, April 2005
	Scott M. Thede, Using reinforcement learning to introduce artificial intelligence in the CS curriculum, Journal of Computing Sciences in Colleges, v.18 n.1, p.107-112, October 2002
	Jiří Grim , Petr Somol , Pavel Pudil, Probabilistic neural network playing and learning tic-tac-toe, Pattern Recognition Letters, v.26 n.12, p.1866-1873, September 2005
	Darse Billings , Lourdes Peña , Jonathan Schaeffer , Duane Szafron, Learning to play strong poker, Machines that learn to play games, Nova Science Publishers, Inc., Commack, NY, 2001
	Erik C. D. van der Werf , H. Jaap van den Herik , Jos W. H. M. Uiterwijk, Learning to score final positions in the game of Go, Theoretical Computer Science, v.349 n.2, p.168-183, 14 December 2005
	D. Gomboc , M. Buro , T. A. Marsland, Tuning evaluation functions by maximizing concordance, Theoretical Computer Science, v.349 n.2, p.202-229, 14 December 2005
	Pascal Poupart , Nikos Vlassis , Jesse Hoey , Kevin Regan, An analytic solution to discrete Bayesian reinforcement learning, Proceedings of the 23rd international conference on Machine learning, p.697-704, June 25-29, 2006, Pittsburgh, Pennsylvania
	Carlos H. C. Ribeiro , Renê Pegoraro , Anna H. Reali Costa, Experience generalization for concurrent reinforcement learners: the minimax-QS algorithm, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy
	Satinder Singh, Introduction, Machine Learning, v.49 n.2-3, p.107-109, November-December 2002
	Rémi Munos , Andrew Moore, Variable Resolution Discretization in Optimal Control, Machine Learning, v.49 n.2-3, p.291-323, November-December 2002
	Michael Bowling , Johannes Fürnkranz , Thore Graepel , Ron Musick, Machine learning and games, Machine Learning, v.63 n.3, p.211-215, June 2006
	Jordan B. Pollack , Alan D. Blair, Co-Evolution in the Successful Learning of Backgammon Strategy, Machine Learning, v.32 n.3, p.225-240, Sept. 1998
	B. F. Melnikov, Heuristics in Programming of Nondeterministic Games, Programming and Computing Software, v.27 n.5, p.277-288, September-October 2001
	Engin Ïpek , Sally A. McKee , Rich Caruana , Bronis R. de Supinski , Martin Schulz, Efficiently exploring architectural design spaces via predictive modeling, ACM SIGOPS Operating Systems Review, v.40 n.5, December 2006
	Pablo Funes , Jordan Pollack, Evolutionary Body Building: Adaptive Physical Designs for Robots, Artificial Life, v.4 n.4, p.337-357, October 1998
	Pieter R. Roelfsema , Arjen R. Van Ooyen, Attention-Gated Reinforcement Learning of Internal Representations for Classification, Neural Computation, v.17 n.10, p.2176-2214, October 2005
	Richard S. Sutton , Anna Koop , David Silver, On the role of tracking in stationary environments, Proceedings of the 24th international conference on Machine learning, p.871-878, June 20-24, 2007, Corvalis, Oregon
	Munir H Naveed , Peter I Cowling, Using coevolution and gradient-based learning for the virus game, Proceedings of the 2006 international conference on Game research and development, p.283-287, December 04-06, 2006, Perth, Australia
	Pasquale Fiengo , Giovanni Giambene , Edmondo Trentin, Neural-based downlink scheduling algorithm for broadband wireless networks, Computer Communications, v.30 n.2, p.207-218, January, 2007
	Fernando J. Pineda, Mean-field theory for batched TD (&lgr;), Neural Computation, v.9 n.7, p.1403-1419, Oct. 1, 1997
	Eric B. Baum , Igor B. Durdanovic, Evolution of Cooperative Problem Solving in an Artificial Economy, Neural Computation, v.12 n.12, p.2743-2775, December 2000
	Sooraj Bhat , David L. Roberts , Mark J. Nelson , Charles L. Isbell , Michael Mateas, A globally optimal algorithm for TTD-MDPs, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Stefan J. Johansson, On using multi-agent systems in playing board games, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Mark J. Nelson , David L. Roberts , Charles L. Isbell, Jr. , Michael Mateas, Reinforcement learning for declarative optimization-based drama management, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Shiu-li Huang , Fu-ren Lin, The design and evaluation of an intelligent sales agent for online persuasion and negotiation, Electronic Commerce Research and Applications, v.6 n.3, p.285-296, October, 2007
	Sanmay Das, Learning to trade with insider information, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA
	Liviu Panait , Sean Luke, Cooperative Multi-Agent Learning: The State of the Art, Autonomous Agents and Multi-Agent Systems, v.11 n.3, p.387-434, November 2005
	Yaniv Azaria , Moshe Sipper, GP-Gammon: Genetically Programming Backgammon Players, Genetic Programming and Evolvable Machines, v.6 n.3, p.283-300, September 2005
	Jelle R. Kok , Nikos Vlassis, Collaborative Multiagent Reinforcement Learning by Payoff Propagation, The Journal of Machine Learning Research, 7, p.1789-1828, 12/1/2006
	Satinder Singh , Tommi Jaakkola , Michael L. Littman , Csaba Szepesvári, Convergence Results for Single-Step On-PolicyReinforcement-Learning Algorithms, Machine Learning, v.38 n.3, p.287-308, March 2000
	Robert H. Crites , Andrew G. Barto, Elevator Group Control Using Multiple Reinforcement Learning Agents, Machine Learning, v.33 n.2-3, p.235-262, Nov./Dec. 1998
	David Choi , Benjamin Roy, A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning, Discrete Event Dynamic Systems, v.16 n.2, p.207-239, April 2006
	John W. Sheppard, Colearning in Differential Games, Machine Learning, v.33 n.2-3, p.201-233, Nov./Dec. 1998
	Theodore J. Perkins , Andrew G. Barto, Lyapunov design for safe reinforcement learning, The Journal of Machine Learning Research, 3, 3/1/2003
	Gerald Tesauro , Nicholas K. Jong , Rajarshi Das , Mohamed N. Bennani, On the use of hybrid reinforcement learning for autonomic resource allocation, Cluster Computing, v.10 n.3, p.287-299, September 2007
	Keith L. Downing, Reinforced Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.3, p.259-288, September 2001
	Gerald Tesauro , Jeffrey O. Kephart, Pricing in Agent Economies Using Multi-Agent Q-Learning, Autonomous Agents and Multi-Agent Systems, v.5 n.3, p.289-304, September 2002
	Nicholas K. Jong , Peter Stone, Model-based function approximation in reinforcement learning, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Engin Ipek , Sally A. McKee , Karan Singh , Rich Caruana , Bronis R. de Supinski , Martin Schulz, Efficient architectural design space exploration via predictive modeling, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.4, p.1-34, January 2008
	Nees Jan van Eck , Michiel van Wezel, Application of reinforcement learning to the game of Othello, Computers and Operations Research, v.35 n.6, p.1999-2017, June, 2008
	Shiu-li Huang , Fu-ren Lin, Using temporal-difference learning for multi-agent bargaining, Electronic Commerce Research and Applications, v.7 n.4, p.432-442, January, 2009
	Rémi Munos , Csaba Szepesvári, Finite-Time Bounds for Fitted Value Iteration, The Journal of Machine Learning Research, 9, p.815-857, 6/1/2008
	Dimitris Kalles, Player Co-Modelling in a Strategy Board Game: Discovering How to Play Fast, Cybernetics and Systems, v.39 n.1, p.1-17, January 2008
	Qian Zhu , Gagan Agrawal, An adaptive middleware for supporting time-critical event response, Cluster Computing, v.12 n.1, p.87-100, March 2009
	Bethany R. Leffler , Michael L. Littman , Timothy Edmunds, Efficient reinforcement learning with relocatable action models, Proceedings of the 22nd national conference on Artificial intelligence, p.572-577, July 22-26, 2007, Vancouver, British Columbia, Canada
	Wee-Chong Oon , Martin Henz, M²ICAL analyses HC-gammon, Proceedings of the 22nd national conference on Artificial intelligence, p.621-626, July 22-26, 2007, Vancouver, British Columbia, Canada
	Shogo Takeuchi , Tomoyuki Kaneko , Kazunori Yamaguchi , Satoru Kawai, Visualization and adjustment of evaluation functions based on evaluation values and win probability, Proceedings of the 22nd national conference on Artificial intelligence, p.858-863, July 22-26, 2007, Vancouver, British Columbia, Canada
	Thomas G. Dietterich, Machine learning, Encyclopedia of Computer Science, 4th edition, John Wiley and Sons Ltd., Chichester, 2003
	Benoít Frénay , Marco Saerens, QL2, a simple reinforcement learning scheme for two-player zero-sum Markov games, Neurocomputing, v.72 n.7-9, p.1494-1507, March, 2009
	Patrick McDowell , Cris Koutsougeras, Graph memory development in a robot control architecture, Journal of Computing Sciences in Colleges, v.24 n.4, April 2009
	Andrea Bonarini , Alessandro Lazaric , Francesco Montrone , Marcello Restelli, Reinforcement distribution in fuzzy Q-learning, Fuzzy Sets and Systems, v.160 n.10, p.1420-1443, May, 2009
	Rogier Koppejan , Shimon Whiteson, Neuroevolutionary reinforcement learning for generalized helicopter control, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada
	Mehdi Samadi , Jonathan Schaeffer , Fatemeh Torabi Asr , Majid Samar , Zohreh Azimifar, Using abstraction in Two-Player Games, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.545-549, June 27, 2008
	Dimitris Kalles , Christos Kalantzis, Evolving Computer Game Playing via Human-Computer Interaction: Machine Learning Tools in the Knowledge Engineering Life-Cycle, Proceeding of the 2008 conference on Knowledge-Based Software Engineering: Proceedings of the Eighth Joint Conference on Knowledge-Based Software Engineering, p.59-68, June 29, 2008
	Sébastien Jodogne , Justus H. Piater, Closed-loop learning of visual control policies, Journal of Artificial Intelligence Research, v.28 n.1, p.349-391, January 2007
	Satinder Singh , Diane Litman , Michael Kearns , Marilyn Walker, Optimizing dialogue management with reinforcement learning: experiments with the NJFun system, Journal of Artificial Intelligence Research, v.16 n.1, p.105-133, January 2002
	Branislav Kveton , Milos Hauskrecht , Carlos Guestrin, Solving factored MDPs with hybrid state and action variables, Journal of Artificial Intelligence Research, v.27 n.1, p.153-201, September 2006
	Michael Buro, Statistical feature combination for the evaluation of game positions, Journal of Artificial Intelligence Research, v.3 n.1, p.373-382, June 1995
	Leslie Pack Kaelbling , Michael L. Littman , Andrew W. Moore, Reinforcement learning: a survey, Journal of Artificial Intelligence Research, v.4 n.1, p.237-285, Jnauary 1996
	Megan Smith , Stephen Lee-Urban , Héctor Muñoz-Avila, RETALIATE: learning winning policies in first-person shooter games, Proceedings of the 19th national conference on Innovative applications of artificial intelligence, p.1801-1806, July 22-26, 2007, Vancouver, British Columbia, Canada
	Mehdi Samadi , Ariel Felner , Jonathan Schaeffer, Learning from multiple heuristics, Proceedings of the 23rd national conference on Artificial intelligence, p.357-362, July 13-17, 2008, Chicago, Illinois
	Arthur Guez , Robert D. Vincent , Massimo Avoli , Joelle Pineau, Adaptive treatment of epilepsy via batch-mode reinforcement learning, Proceedings of the 20th national conference on Innovative applications of artificial intelligence, p.1671-1678, July 13-17, 2008, Chicago, Illinois
	Tom Croonenborghs , Jan Ramon , Hendrik Blockeel , Maurice Bruynooghe, Online learning and exploiting relational models in reinforcement learning, Proceedings of the 20th international joint conference on Artifical intelligence, p.726-731, January 06-12, 2007, Hyderabad, India
	Jonathan Dinerstein , Parris K. Egbert , Dan Ventura, Learning policies for embodied virtual agents through demonstration, Proceedings of the 20th international joint conference on Artifical intelligence, p.1257-1262, January 06-12, 2007, Hyderabad, India
	Julien Laumonier, Reinforcement using supervised learning for policy generalization, Proceedings of the 22nd national conference on Artificial intelligence, p.1882-1883, July 22-26, 2007, Vancouver, British Columbia, Canada
	Lourdes Pefia Castillo , Stefan Wrobel, Learning Minesweeper with multirelational learning, Proceedings of the 18th international joint conference on Artificial intelligence, p.533-538, August 09-15, 2003, Acapulco, Mexico
	Jonathan Schaeffer , Markian Hlynka , Vili Jussila, Temporal difference learning applied to a high-performance game-playing program, Proceedings of the 17th international joint conference on Artificial intelligence, p.529-534, August 04-10, 2001, Seattle, WA, USA
	Leo Galway , Darryl Charles , Michaela Black, Machine learning in digital games: a survey, Artificial Intelligence Review, v.29 n.2, p.123-161, April 2008
	Tuomas Sandholm, Perspectives on multiagent learning, Artificial Intelligence, v.171 n.7, p.382-391, May, 2007

INDEX TERMS

Primary Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE
I.2.1 Applications and Expert Systems
Subjects: Games

General Terms:
Algorithms, Measurement, Performance

REVIEW

"Jaak Tepandi : Reviewer"

Complex board games are a natural testing ground for machine learning and artificial intelligence. They are based on experience; they are attractive; and they do not have the safety requirements that sometimes block the use of heur more...

Collaborative Colleagues:

Gerald Tesauro: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player