Abstract
The research presented in this paper forms part of a larger initiative aimed at creating a general game player for two player zero sum board games. In previous work, we have presented a novel heuristic based genetic programming approach for evolving game playing for the board game Othello. This study extends this work by firstly evaluating it on a different board game, namely, checkers. Secondly, the study investigates incorporating reinforcement learning to further improve evolved game playing strategies. Genetic programming evolves game playing strategies composed of heuristics, which are used to decide which move to make next. Each strategy represents a player. A separate genetic programming run is performed for each move of the game. Reinforcement learning is applied to the population at the end of a run to further improve the evolved strategies. The evolved players were found to outperform random players at checkers. Furthermore, players induced combining genetic programming and reinforcement learning outperformed the genetic programming players. Future research will look at further application of this approach to similar non-trivial board games such as chess.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Schaeffer, J., Burch, N., Bjornsson, Y., Kishimoto, A., Muller, M., Lake, R., Lu, P., Sutphen, S.: Checkers is solved. Science 317(5844), 1518–1522 (2007)
Duch, W.: What is computational intelligence and where is it going? In: Duch, W., Mandziuk, J. (eds.) Challenges for Computational Intelligence. Springer Studies in Computational Intelligence, vol. 63, pp. 1–13. Springer, Heidelberg (2007)
Waledzik, K., Mandziuk, J.: The Layered Learning method and its application to generation of evaluation functions for the game of checkers. In: 11th International Conference, pp. 543–552. Kraków, Poland, (2010)
Lucas, S.: Computational intelligence and games: challenges and opportunities. Int. J. Autom. Comput. 5(1), 45–57 (2008)
Chellapilla, K., Fogel, D.: Evolving an expert checkers playing program without using human expertise. IEEE Trans. Evol. Comput. 5(4), 422–428 (2001)
Kusiak, M., Waledzik, K., Mandziuk, J.: Evolutionary approach to the game of checkers. 8th International Conference on Adaptive and Natural Computing Algorithms, ICANNGA 2007, pp. 432–440. Warsaw, Poland (2007)
Pell, B.: Strategy Generation and Evaluation for Meta-Game Playing. Ph.D. Dissertation, University of Cambridge (1993)
David, O., van den Herik, J., Koppel, M., Netanyahu, N.: Genetic algorithms for evolving computer chess programs. IEEE Trans. Evol. Comput. 18(5), 779–789 (2001)
Mukherjee, A.: A Genetic Programming Approach to. Modified Chinese Checkers. https://cs4701.wikispaces.com/file/view/4701+final+report.pdf (2013)
Kusiak, M., Waledzik, K., Mandziuk, J.: Evolutionary-based heuristic generators for checkers and give-away checkers. Expert Syst. 24(4), 189–211 (2007)
Benbassat, A., Sipper, M.: Evolving lose-checkers players using genetic programming. In: Proceedings of the 2010 IEEE Symposium on Computational Intelligence and Games (CIG), pp. 30–37. Dublin (2010)
Frankland, C., Pillay, N.: Evolving game playing strategies for othello. In: Proceedings of the 2015 IEEE Congress on Evolutionary Computation (CEC 2015), pp. 1498–1504. Sendai, Japan, 25–28 May 2015
Rules of Draughts (Checkers), http://www.wcdf.net/rules/rules_of_checkers_english.pdf
Koza, J.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press (1992)
Finnsson, H., Björnsson, Y.: Simulation control in general game playing agents. In: Proceedings of the AAAI conference on Artificial Intelligence, Atlanta, pp. 954–959. Atlanta (2010)
Van Lishout, F., Chaslot, G., Uiterwijk, J.: Monte-Carlo tree search in backgammon. In: Proceedings of the Computer Games Workshop (GCW 2007), pp. 175–184. Amsterdam (2007)
Chaslot, G., Bakkes, S., Szita, I., Spronck, P.: Monte-Carlo tree search: a new framework for game AI. In: Proceedings of the 4th Artificial Intelligence and Interactive Digital Entertainment Conference, pp. 216–217. AAAI Press, Menlo Park (2008)
Benbassat, A., Sipper, M.: Evolving board-game players with genetic programming. In: Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO ‘11), pp. 739–742 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Frankland, C., Pillay, N. (2016). Evolving Heuristic Based Game Playing Strategies for Checkers Incorporating Reinforcement Learning. In: Pillay, N., Engelbrecht, A., Abraham, A., du Plessis, M., Snášel, V., Muda, A. (eds) Advances in Nature and Biologically Inspired Computing. Advances in Intelligent Systems and Computing, vol 419. Springer, Cham. https://doi.org/10.1007/978-3-319-27400-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-27400-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27399-0
Online ISBN: 978-3-319-27400-3
eBook Packages: Computer ScienceComputer Science (R0)