Abstract
A general game playing (GGP) system aims to play previously unknown board games with changeable rules without human intervention. Taking changeable game rules into consideration, a game description language presents formal descriptions of a game. Based on this description, legal moves can be automatically generated so that each player in GGP system only needs to solve the problems of searching and learning for playing well. Traditional search methods demand the player to compute all legal moves, which can be very time consuming. In GGP, the coordinate of cells in the game board is very important in board game rules. Thus we address the relationship among cell coordinates. Borrowing an idea from rule learning to prune the board game search tree, we propose a new search optimization method to reduce running time when searching a large search space. We further prove that this method can effectively improve the searching efficiency through a comparative experiment with Gomoku game in GGP system.
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
Genesereth, M., Love, N., Pell, B.: General game playing: overview of the AAAI competition. AI Mag. 26(2), 62–72 (2005)
Świechowski, M., Mańdziuk, J.: Fast interpreter for logical reasoning in general game playing. J. Log. Comput. 26(5), 1697–1727 (2014)
Love, N., Hinrichs, T., Haley, D., et al.: General game playing: game description language specification (2008)
Silver, D., Huang, A., Maddison, C.J., et al.: Mastering the game of Go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)
Mitra, A., Baral, C.: Addressing a question answering challenge by combining statistical methods with inductive rule learning and reasoning. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (2016)
Garciá, D., Ga\(\acute{{\rm m}}\)ez, J.C., Gonza\(\acute{{\rm l}}\)ez, A., Pe\(\acute{{\rm r}}\)eza, R.: An interpretability improvement for fuzzy rule bases obtained by the iterative rule learning approach. Int. J. Approximate Reasoning 67, 37–58 (2015)
Günther, M., Schiffel, S., Thielscher, M.: Factoring general games. In: Proceedings of the International Joint Conference on Artificial Intelligence-09 workshop on general game playing, pp. 27–34 (2009)
Kuželka, O., Davis, J., Schockaert, S.: Learning possibilistic logic theories from default rules. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (2016)
de Jonge, D., Zhang, D.: Lifted backward search for general game playing. In: Kang, B.H., Bai, Q. (eds.) AI 2016. LNCS (LNAI), vol. 9992, pp. 3–16. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50127-7_1
Krajnanský, M., Hoffmann, J., et al.: Learning pruning rules for heuristic search planning. In: European Conference on Artificial Intelligence, pp. 483–488 (2014)
Genesereth, M., Thielscher, M.: General Game Playing. Morgan & Claypool Publishers, Williston (2014)
Kaiser, D.M.: The design and implementation of a successful general game playing agent. In: Wilson, D., Sutcliffe, G. (eds.) International Florida Artificial Intelligence Research Society Conference 2007, pp. 110–115. AAAI Press, California (2007)
Thielscher, M.: A general game description language for incomplete information games. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 994–999. AAAI Press, Atlanta (2010)
Fürnkranz, J., Gamberger, D., Lavrac, N.: Foundations of Rule Learning. Cognitive Technologies. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-540-75197-7
Liu, C., Wang, W., Wang, M., Lv, F., Konan, M.: An efficient instance selection algorithm to reconstruct training set for support vector machine. In: Knowledge-Based Systems, pp. 58–73 (2017)
Zhang, D., Thielscher, M.: Representing and reasoning about game strategies. J. Philos. Log. 44(2), 203–236 (2015)
Acknowledgement
This work was supported by the Key Project of Chongqing Humanities and Social Science Key Research Base: Research on Coalition Welfare Distribution Mechanism and Social Cohesion Based on Cooperative Game Theory and the Ratification Number is 18SKB047.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Wang, H., Tang, Y., Liu, J., Chen, W. (2018). A Search Optimization Method for Rule Learning in Board Games. In: Geng, X., Kang, BH. (eds) PRICAI 2018: Trends in Artificial Intelligence. PRICAI 2018. Lecture Notes in Computer Science(), vol 11013. Springer, Cham. https://doi.org/10.1007/978-3-319-97310-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-97310-4_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97309-8
Online ISBN: 978-3-319-97310-4
eBook Packages: Computer ScienceComputer Science (R0)