Abstract
In this article, a new approach to solving selected two-person perfect information zero-sum games is proposed. This new approach involves dividing game board into smaller parts called partial boards. Every such partial board has an associated “border state” which is an information structure vital to the game solving process. Using partial boards, it is possible to generate partial board game trees. Such structures are sufficient for the purpose of searching complete game trees - in effect. The possibility of making different board divisions allows an entire partial board game tree to be stored in computer memory. As a result, tree search algorithms based on partial board game trees work very fast. This approach can be applied only for specific games. Examples of such games are Atari-Go, Hex, and Gomoku. Experimental results relating to the solving of the Atari-Go game are presented here.
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.
Nodes, for which values are obtained from transposition table are not counted as visited.
References
Arneson, B., Hayward, R., Henderson, P.: Solving hex: beyond humans. Comput. Games 6515, 1–10 (2011)
Breuker, D., Uiterwijk, J., van den Herik, H.: Replacement schemes for transposition tables. Int. Comput. Chess Assoc. J. 17(4), 183–193 (1994)
Cazenave, T.: Generation of patterns with external conditions for the game of Go. Adv. Comput. Games 9, 275–293 (2001)
Gelly, S., Silver, D.: Monte-Carlo tree search and rapid action value estimation in computer Go. Artif. Intell. 175(11), 1856–1875 (2011)
van den Herik, H., Uiterwijk, J.W., van Rijswijck, J.: Games solved: now and in the future. Artif. Intell. 134(1–2), 277–311 (2002)
Heule, M., Rothkrantz, L.: Solving games: dependence of applicable solving procedures. Sci. Comput. Program. 67(1), 105–124 (2007)
Müller, M.: Computer Go as a sum of local games: an application of combinatorial game theory. Ph.D. thesis, Swiss Federal Institute Of Technology Zürich (1995)
Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.: Mastering the game of go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)
Tromp, J., Farnebäck, G.: Combinatorics of Go. In: van den Herik, H., Ciancarini, P., Donkers, H. (eds.) Computers and Games. LNCS, vol. 4630, pp. 84–99. Springer, Heidelberg (2007)
Von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1953)
Zobrist, A.: A new hashing method with application for game playing. Int. Comput. Chess Assoc. J. 13(2), 69–73 (1970)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix A
Appendix A
Pseudocode for partial board tree search algorithm using two OneSide partial board game trees is presented in Algorithm 1. Minimax algorithm works on two partial board game trees at the same time. Array represents two nodes, each from different OneSide partial board game tree. Border state connection matrix (
) holds values obtained from all possible connections between OneSide border states of analysed height. Recursive function
has two for loops. Inner loop iterates partial board game tree nodes. Outer loop (line 8) iterates partial board game trees, precisely partial board game nodes (
).
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Perlinski, R. (2018). Partial Board Tree Search. In: Gruca, A., Czachórski, T., Harezlak, K., Kozielski, S., Piotrowska, A. (eds) Man-Machine Interactions 5. ICMMI 2017. Advances in Intelligent Systems and Computing, vol 659. Springer, Cham. https://doi.org/10.1007/978-3-319-67792-7_50
Download citation
DOI: https://doi.org/10.1007/978-3-319-67792-7_50
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67791-0
Online ISBN: 978-3-319-67792-7
eBook Packages: EngineeringEngineering (R0)