Abstract
Recent works have shown that Genetic Programming (GP) can be quite successful at evolving human-competitive strategies for games ranging from classic board games, such as chess, to action video games. However to our knowledge GP was never applied to modern complex board games, so-called eurogames, such as Settlers of Catan, i.e. board games that typically involve four characteristics: they are non zero-sum games, multiplayer, with hidden information and random elements. In this work we study how GP can evolve artificial players from low level attributes of a eurogame named “7 Wonders”, that features all the characteristics of this category. We show that GP can evolve competitive artificial intelligence (AI) players against human-designed AI or against Monte Carlo Tree Search, a standard in automatic game playing.
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
Notes
- 1.
While the rule allows 2 player games, these are played by simulating a 3rd “dumb” player.
References
Pfeiffer, M.: Reinforcement learning of strategies for Settlers of Catan. In: Mehdi, Q., Gough, N., Natkin, S., Al-Dabass, D. (eds.) 5th international conference on computer games: artificial intelligence, design and education, pp. 384–388 (2004)
Szita, I., Chaslot, G., Spronck, P.: Monte-Carlo tree search in settlers of catan. In: van den Herik, H.J., Spronck, P. (eds.) ACG 2009. LNCS, vol. 6048, pp. 21–32. Springer, Heidelberg (2010)
Winder, R.K.: Methods for approximating value functions for the Dominion card game. Evol. Intell. 6(4), 195–204 (2013)
Chaslot, G.M.J.P., Saito, J.-T., Bouzy, B., Uiterwijk, J.W.H.M., Van Den Herik, H.J.: Monte-Carlo strategies for computer Go. In: Proceedings of the 18th BeNeLux Conference on Artificial Intelligence, Namur, Belgium, pp. 83–91 (2006)
Hauptman, A., Sipper, M.: GP-endchess: using genetic programming to evolve chess endgame players. In: Keijzer, M., Tettamanzi, A.G.B., Collet, P., van Hemert, J., Tomassini, M. (eds.) EuroGP 2005. LNCS, vol. 3447, pp. 120–131. Springer, Heidelberg (2005)
Sipper, M.: Evolving game-playing strategies with genetic programming. ERCIM News 64, 28–29 (2008). Invited article
Shannon, C.E.: XXII. Programming a computer for playing chess. Philos. Mag. (Ser. 7) 41(314), 256–275 (1950)
Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 282–293. Springer, Heidelberg (2006)
Coulom, R.: Efficient selectivity and backup operators in monte-carlo tree search. In: Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 72–83. Springer, Heidelberg (2007)
Gelly, S., Silver, D.: Combining online and offline knowledge in uct. In: Proceedings of the 24th International Conference on Machine learning, pp. 273–280. ACM (2007)
Lorentz, R.J.: Amazons discover Monte-Carlo. In: Herik, H.J., Xu, X., Ma, Z., Winands, M.H.M. (eds.) CG 2008. LNCS, vol. 5131, pp. 13–24. Springer, Heidelberg (2008)
Cazenave, T.: Monte-Carlo kakuro. In: van den Herik, H.J., Spronck, P. (eds.) ACG 2009. LNCS, vol. 6048, pp. 45–54. Springer, Heidelberg (2010)
Arneson, B., Hayward, R.B., Henderson, P.: Monte-Carlo tree search in Hex. IEEE Trans. Comput. Intell. AI Games 2(4), 251–258 (2010)
Teytaud, F., Teytaud, O.: Creating an upper-confidence-tree program for havannah. In: van den Herik, H.J., Spronck, P. (eds.) ACG 2009. LNCS, vol. 6048, pp. 65–74. Springer, Heidelberg (2010)
Robilliard, D., Fonlupt, C., Teytaud, F.: Monte-Carlo tree search for the game of “7 wonders”. In: Cazenave, T., Winands, M.H.M., Björnsson, Y. (eds.) CGW 2014. CCIS, vol. 504, pp. 64–77. Springer, Heidelberg (2014)
Whitehouse, D., Powley, E.J., Cowling, P.I.: Determinization and information set Monte-Carlo tree search for the card game Dou Di Zhu. In: IEEE Conference on Computational Intelligence and Games (CIG), pp. 87–94. IEEE (2011)
Hoock, J.-B., Teytaud, O.: Bandit-based genetic programming. In: Esparcia-Alcázar, A.I., Ekárt, A., Silva, S., Dignum, S., Uyar, A.Ş. (eds.) EuroGP 2010. LNCS, vol. 6021, pp. 268–277. Springer, Heidelberg (2010)
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
Robilliard, D., Fonlupt, C. (2016). Towards Human-Competitive Game Playing for Complex Board Games with Genetic Programming. In: Bonnevay, S., Legrand, P., Monmarché, N., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2015. Lecture Notes in Computer Science(), vol 9554. Springer, Cham. https://doi.org/10.1007/978-3-319-31471-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-31471-6_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-31470-9
Online ISBN: 978-3-319-31471-6
eBook Packages: Computer ScienceComputer Science (R0)