Abstract
We propose an approach to the learning of long-term plans for playing chess endgames. We assume that a computer-generated database for an endgame is available, such as the king and rook vs. king, or king and queen vs. king and rook endgame. For each position in the endgame, the database gives the “value” of the position in terms of the minimum number of moves needed by the stronger side to win given that both sides play optimally. We propose a method for automatically dividing the endgame into stages characterised by different objectives of play. For each stage of such a game plan, a stage-specific evaluation function is induced, to be used by minimax search when playing the endgame. We aim at learning playing strategies that give good insight into the principles of playing specific endgames. Games played by these strategies should resemble human expert’s play in achieving goals and subgoals reliably, but not necessarily as quickly as possible.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bain, M. & Srinivasan, A. (1995). Inductive logic programming with large-scale unstructured data. In K. Furukawa, D. Michie, and S. Muggleton (Eds.), Machine Intelligence 14. Oxford: Clarendon Press.
Baxter, J., Tridgell, A., & Weaver, L. (2000). Learning to play chess using temporal differences. Machine Learning, 40(3), 243–263.
Blake, C. L. & Merz, C. J. (1998). UCI repository of machine learning databases. http://www.ics.uci.edu/mlearn/MLRepository.html, Department of Information and Computer Science, University of California, Irvine, CA.
Bratko, I. (1984). Advice and planning in chess endgames. In A. Elithorn and R. Banerji (Eds.), Artificial and human thinking (pp. 119–130). Amsterdam: North-Holland.
Bratko, I. (2001). Prolog programming for artificial intelligence, 3rd edn. Addison-Wesley Publishing Company.
Buro, M. (1999). How machines have learned to play Othello. IEEE Intelligent Systems Journal, 14(6), 12–14.
Demšar, J., Zupan, B., & Leban, G. (2004). Orange: From experimental machine learning to interactive data mining. http://www.ailab.si/orange (White Paper), Faculty of Computer and Information Science, University of Ljubljana.
Dvoretsky, M. (2003). Dvoretsky’s endgame manual. Milford, CT: Russell Enterprises.
Fürnkranz, J. (2001). Machine learning in games: A survey. In J. Fürnkranz and M. Kubat (Eds.), Machines that learn to play games. New York, NJ: Nova Scientific Publishers.
George, M. & Schaeffer, J. (1990). Chunking for experience. International Computer Chess Association Journal, 13(3), 123–132.
Morales, E. (1994). Learning patterns for playing strategies. International Computer Chess Association Journal, 17(1), 15–26.
Muggleton, S. (1989). DUCE, an oracle based approach to constructive induction. In Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Morgan Kaufmann (pp. 287–292).
Quinlan, J. R. (1979). Discovering rules by induction from large collections of examples. Expert Systems in the Micro Electronic Age.
Quinlan, J. R. (1983). Learning efficient classification procedures and their application to chess endgames. Machine Learning: An Artificial Intelligence Approach, 463–482.
Quinlan, J. R. (1986). Induction of decision trees. In J. W. Shavlik and T. G. Dietterich (eds.), Readings in machine learning. Morgan Kaufmann, Originally published in Machine Learning, 1(1), 81–106.
Samuel, A. L. (1967). Some studies in machine learning using the game of checkers II—recent progress. IBM Journal of Research and Development, 11(6), 601–617.
Shapiro, A. D. & Niblett, T. (1982) Automatic induction of classification rules for a chess endgame. In M. R. B. Clarke (Ed.), Advances in computer chess 3 (pp. 73–92). Oxford: Pergamon Press.
Tesauro, G. (1992). Practical issues in temporal difference learning. Machine Learning, 8(3–4), 257–278.
Thompson K. (1986). Retrograde analysis of certain endgames. International Computer Chess Association Journal, 9(3), 131–139.
Thompson, K. (1996). 6-piece endgames. International Computer Chess Association Journal, 19(4), 215–226.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors: Michael Bowling · Johannes Fürnkranz · Thore Graepel · Ron Musick
Rights and permissions
About this article
Cite this article
Sadikov, A., Bratko, I. Learning long-term chess strategies from databases. Mach Learn 63, 329–340 (2006). https://doi.org/10.1007/s10994-006-6747-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10994-006-6747-7