Backgammon
Backgammon,
a turn-based two-player tables board game of chance and strategy with 15 checkers each on a board of 24 spaces or points. One moves according to rolls of a pair of dice, trying to bring own checkers home and bear them off before the opponent does [2]. Opponent checkers can be "hit" and returned to the start.
Contents
Computer Backgammon
Backgammon programs were pioneered in the late 70s by Hans Berliner with focus on smooth evaluation, and by Gerald Tesauro from the late 80s, who successfully applied Neural Networks and Temporal Difference Learning to his Backgammon playing programs. Computer backgammon is regularly played at Computer Olympiads, organized by the ICGA [3].
Computer Olympiads
- 1st Computer Olympiad, London 1989
- 2nd Computer Olympiad, London 1990
- 4th Computer Olympiad, London 1992
- 7th Computer Olympiad, Maastricht 2002
- 8th Computer Olympiad, Graz 2003
- 11th Computer Olympiad, Turin 2006
- 12th Computer Olympiad, Amsterdam 2007
- 16th Computer Olympiad, Tilburg 2011
- 18th Computer Olympiad, Leiden 2015
- 19th Computer Olympiad, Leiden 2016
Photos
18th Computer Olympiad 2015, Backgammon medalists: Frank Berger (Bronze for BGBlitz),
Nikolaos Papahristou (Gold for Palamedes), and Nardy Pillards (Silver for GNU Backgammon) [4]
Evaluation
In the late 70s at Carnegie Mellon University, Hans Berliner developed the Backgammon playing program BKG 9.8 for the PDP-10 to research the principles of evaluation for another game than chess with a much higher branching factor of more than 800 at every node [5]. Early versions of BKG played badly even against weak players, but Berliner noticed that its critical mistakes were always at transitions apparently due to evaluation discontinuity. He applied principles of fuzzy logic to smooth out the transition between phases, and by July 1979, BKG 9.8 was strong enough to play against the ruling world champion Luigi Villa. It won the match 7–1, becoming the first computer program to defeat a world champion in any game. Berliner states that the victory was largely a matter of luck, as the computer received more favorable dice rolls [6] [7].
Learning
In the late 80s, IBM researcher Gerald Tesauro pioneered in applying Neural Networks to Backgammon - first within his program Neurogammon, which won the Gold medal at the 1st Computer Olympiad 1989 - and further improved by TD-Lambda based Temporal Difference Learning within TD-Gammon [8].
Publications
1977 ...
- Hans Berliner (1977). BKG - A Program that Plays Backgammon. Technical Report, Carnegie Mellon University
- Hans Berliner (1977). Experiences in Evaluation with BKG, a Program That Plays Backgammon. IJCAI, 1977, hosted by Backgammon Galore
- Hans Berliner (1979). On the Construction of Evaluation Functions for Large Domains. IJCAI 1979, Vol. 1, hosted by Backgammon Galore
- Editor (1979). Computer Backgammon. Personal Computing, Vol. 3, No. 8, pp. 81
1980 ...
- Hans Berliner (1980). Backgammon Computer Program Beats World Champion. Artificial Intelligence, Vol. 14, hosted by Backgammon Galore
- Hans Berliner (1980). Computer Backgammon. Scientific American, Vol. 242, No. 6, hosted by Backgammon Galore
1985 ...
- Gerald Tesauro, Terrence J. Sejnowski (1987). A 'Neural' Network that Learns to Play Backgammon. NIPS 1987
- Gerald Tesauro (1988). Connectionist Learning of Expert Backgammon Evaluations. ML, 1988
- Gerald Tesauro (1988). Neural network defeats creator in backgammon match. Technical report no. CCSR-88-6, Center for Complex Systems Research, University of Illinois at Urbana-Champaign
- Gerald Tesauro (1989). NEUROGAMMON: A Neural-Network Backgammon Learning Program. Heuristic Programming in Artificial Intelligence 1
- Gerald Tesauro (1989). Neurogammon Wins Computer Olympiad. Neural Computation Vol. 1, No. 3
- Gerald Tesauro, Terrence J. Sejnowski (1989). A Parallel Network that Learns to Play Backgammon. Artificial Intelligence, Vol. 39, No. 3
1990 ...
- Gerald Tesauro (1992). Temporal Difference Learning of Backgammon Strategy. ML 1992
- Justin A. Boyan (1992). Modular Neural Networks for Learning Context-Dependent Game Strategies. Master's thesis, University of Cambridge, pdf
- Gerald Tesauro (1994). TD-Gammon, a Self-Teaching Backgammon Program, Achieves Master-Level Play. Neural Computation Vol. 6, No. 2
1995 ...
- Gerald Tesauro (1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM, Vol. 38, No. 3
- Michael Buro (1999). Efficient Approximation of Backgammon Race Equities. ICCA Journal, Vol 22, No. 3,pdf
2000 ...
- Michael Buro (2001). Efficient Approximation of Backgammon Race Equities. Advances in Computer Games 9, pdf
- Gerald Tesauro (2002). Programming backgammon using self-teaching neural nets. Artificial Intelligence Vol. 134 No. 1-2
- Frank Berger (2002). BGBlitz wins Backgammon tournament. ICGA Journal, Vol. 25, No. 3 » 7th Computer Olympiad
- Frank Berger (2002). Backgammon at the 7th Computer Olympiad. ICGA Journal, Vol. 25, No. 4 » 7th Computer Olympiad
- Frank Berger (2003). BGBlitz wins Backgammon tournament. ICGA Journal, Vol. 26, No. 4 » 8th Computer Olympiad
- Thomas Hauk, Michael Buro, Jonathan Schaeffer (2004). *-Minimax Performance in Backgammon. CG 2004
2005 ...
- Frank Berger (2006). GnuBG wins Backgammon tournament. ICGA Journal, Vol. 29, No. 3 » 11th Computer Olympiad
- François van Lishout, Guillaume Chaslot, Jos Uiterwijk (2007). Monte-Carlo Tree Search in Backgammon. CGW 2007
- Frank Berger (2007). BGBlitz wins Backgammon tournament. ICGA Journal, Vol. 30, No. 2 » 12th Computer Olympiad
- Wee-Chong Oon, Martin Henz (2007). M2ICAL Analyses HC-Gammon. AAAI 2007 [9]
2010 ...
- Marco Wiering (2010). Self-play and using an expert to learn to play backgammon with temporal difference learning. Journal of Intelligent Learning Systems and Applications, Vol. 2, No. 2
- Nikolaos Papahristou, Ioannis Refanidis (2011). Training Neural Networks to Play Backgammon Variants Using Reinforcement Learning. Proceedings of Evogames 2011, Part I, LNCS 6624, pdf
- Nikolaos Papahristou, Ioannis Refanidis (2011). Improving Temporal Difference Performance in Backgammon Variants. Advances in Computer Games 13, pdf
- Frank Berger (2012). Palamedes wins Backgammon Tournament. ICGA Journal, Vol. 35, No. 1 » 16th Computer Olympiad
- Nikolaos Papahristou, Ioannis Refanidis (2013). AnyGammon: Playing backgammon variants using any board size. FDG-2013, pdf
2015 ...
- Nikolaos Papahristou, Ioannis Refanidis (2015). Constructing Pin Endgame Databases for the Backgammon Variant Plakoto. Advances in Computer Games 14 [10]
Forum Posts
- Chess, Backgammon and Neural Nets (NN) by Torsten Schoop, CCC, August 20, 1998
- Neural nets in backgammon by Albert Silver, CCC, April 07, 2004
- A SNAC, anyone? by Jan Brouwer, CCC, July 30, 2007
- What is the best backgammon software? by M. Ansari, CCC, October 15, 2008
- Backgammon is not chess! by Joe Russell, BGonline.org Forums, March 08, 2013
External Links
Computer Backgammon
- Backgammon (ICGA Tournaments)
- Backgammon Articles: Using Computers to Improve Your Game hosted by the Backgammon Galore
- the neural net backgammon programs from Machine Learning in Games by Jay Scott
- Neural Network learns Backgammon by Kimon Tsinteris and David Wilson
- FIBS, the First Internet Backgammon Server
Backgammon Programs
References
- ↑ A backgammon set, consisting of a board, two sets of 15 checkers, two pairs of dice, a doubling cube, and dice cups, Image by Ptkfgs, March 6, 2013, Backgammon from Wikipedia, Wikimedia Commons
- ↑ Backgammon Galore
- ↑ Backgammon (ICGA Tournaments)
- ↑ 18th Computer Olympiad - Day 6 Photos by Jan Krabbenbos
- ↑ Hans Berliner (1977). Experiences in Evaluation with BKG, a Program That Plays Backgammon. IJCAI, 1977, hosted by Backgammon Galore
- ↑ Hans Berliner from Wikipedia
- ↑ Hans Berliner (1980). Backgammon Computer Program Beats World Champion. Artificial Intelligence, Vol. 14
- ↑ Richard Sutton, Andrew Barto (1998). Reinforcement Learning: An Introduction. MIT Press, 11.1 TD-Gammon
- ↑ The hillclimbing HC-Gammon from Machine Learning in Games by Jay Scott
- ↑ Plakoto from Wikipedia