Abstract
Finding the winner of a game of Go is difficult even on small boards due to the game’s complexity. Static safety detection algorithms can find a winner long before the end of a game, thereby reducing the number of board positions that must be searched. These static algorithms find safe points for each player and so help prove the outcome for positions that would otherwise require a deep search. Our board evaluation algorithm Bounded Static Safety (BSS) introduces two new methods for finding valid lower bounds on the number of safe points: extending liberties and intersecting play. These methods define statically evaluated greedy playing strategies to raise the lower bound of a player’s guaranteed score. BSS can solve positions from a test set of \(6\times 6\) games at an average of 27.29 plies, a significant improvement over the previous best static safety method of locally alternating play (31.56 plies), and far surpassing Benson’s unconditional safety (42.67 plies).
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
Sensei’s Library. https://senseis.xmp.net/
Benson, D.: Life in the Game of Go. Information Sciences 10, 17–29 (1976). Reprinted in Computer Games, Levy, D.N.L. (ed.), vol. II, pp. 203–213, Springer, New York (1988)
Enzenberger, M., Müller, M., Arneson, B., Segal, R.: Fuego-an open-source framework for board games and go engine based on Monte Carlo tree search. IEEE Trans. Comput. Intell. AI Games 2(4), 259–270 (2010)
Haque, R., Wei, T.H., Müller, M.: On the road to perfection? Evaluating Leela chess zero against endgame tablebases. In: ACG 2021. LNCS, vol. 13262, pp. 142–152. Springer, Cham (2021). https://doi.org/10.1007/978-3-031-11488-5_13
Kishimoto, A.: Correct and efficient search algorithms in the presence of repetitions. Ph.D. thesis, University of Alberta (2005)
Müller, M.: Playing it safe: recognizing secure territories in computer go by using static rules and search. In: Game Programming Workshop in Japan ’97, pp. 80–86. Computer Shogi Association, Tokyo, Japan (1997)
Niu, X., Kishimoto, A., Müller, M.: Recognizing Seki in computer go. In: van den Herik, H.J., Hsu, S.-C., Hsu, T., Donkers, H.H.L.M.J. (eds.) ACG 2005. LNCS, vol. 4250, pp. 88–103. Springer, Heidelberg (2006). https://doi.org/10.1007/11922155_7
Niu, X., Müller, M.: An improved safety solver for computer go. In: van den Herik, H.J., Björnsson, Y., Netanyahu, N.S. (eds.) CG 2004. LNCS, vol. 3846, pp. 97–112. Springer, Heidelberg (2006). https://doi.org/10.1007/11674399_7
Niu, X., Müller, M.: An open boundary safety-of-territory solver for the game of go. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 37–49. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75538-8_4
Niu, X., Müller, M.: An improved safety solver in go using partial regions. In: van den Herik, H.J., Xu, X., Ma, Z., Winands, M.H.M. (eds.) CG 2008. LNCS, vol. 5131, pp. 102–112. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87608-3_10
Schaeffer, J., et al.: Checkers is Solved. Science 317(5844), 1518–1522 (2007)
Schrittwieser, J., et al.: Mastering atari, go, chess and shogi by planning with a learned model. CoRR abs/1911.08265 (2019). http://arxiv.org/abs/1911.08265
Silver, D., et al.: Mastering the game of go with deep neural networks and tree search. Nature 529, 484–489 (2016)
Silver, D., et al.: Mastering chess and shogi by self-play with a general reinforcement learning algorithm. CoRR abs/1712.01815 (2017). http://arxiv.org/abs/1712.01815
Silver, D., et al.: Mastering the game of go without human knowledge. Nature 550, 354–359 (2017). https://doi.org/10.1038/nature24270
van der Werf, E., Winands, M.: Solving go for rectangular boards. ICGA J. 32(2), 77–88 (2009). https://doi.org/10.3233/ICG-2009-32203
van der Werf, E., Herik, H., Uiterwijk, J.: Solving go on small boards. ICGA J. 26 (2003). https://doi.org/10.3233/ICG-2003-26205
Wu, D.J.: Accelerating self-play learning in go. CoRR abs/1902.10565 (2019). http://arxiv.org/abs/1902.10565
Wu, T.R., Shih, C.C., Wei, T.H., Tsai, M.Y., Hsu, W.Y., Wu, I.C.: AlphaZero-based proof cost network to aid game solving. In: International Conference on Learning Representations (2022). https://openreview.net/forum?id=nKWjE4QF1hB
Wu, T.R., et al.: Multi-labelled value networks for computer go. CoRR abs/1705.10701 (2017). http://arxiv.org/abs/1705.10701
Acknowledgements
The authors acknowledge financial support from NSERC, the Natural Sciences and Engineering Research Council of Canada, Alberta Innovates, DeepMind, and the Canada CIFAR AI Chair program.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Randall, O., Wei, TH., Hayward, R., Müller, M. (2023). Improving Search in Go Using Bounded Static Safety. In: Browne, C., Kishimoto, A., Schaeffer, J. (eds) Computers and Games. CG 2022. Lecture Notes in Computer Science, vol 13865. Springer, Cham. https://doi.org/10.1007/978-3-031-34017-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-34017-8_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34016-1
Online ISBN: 978-3-031-34017-8
eBook Packages: Computer ScienceComputer Science (R0)