Solving 7x7 Killall-Go with Seki Database
Authors:
Preprint
Abstract
Game solving is the process of finding the theoretical outcome for a game, assuming that all player choices are optimal. This paper focuses on a technique that can reduce the heuristic search space significantly for 7x7 Killall-Go. In Go and Killall-Go, live patterns are stones that are protected from opponent capture. Mutual life, also referred to as seki, is when both players' stones achieve life by sharing liberties with their opponent. Whichever player attempts to capture the opponent first will leave their own stones vulnerable. Therefore, it is critical to recognize seki patterns to avoid putting oneself in jeopardy. Recognizing seki can reduce the search depth significantly. In this paper, we enumerate all seki patterns up to a predetermined area size, then store these patterns into a seki table. This allows us to recognize seki during search, which significantly improves solving efficiency for the game of Killall-Go. Experiments show that a day-long, unsolvable position can be solved in 482 seconds with the addition of a seki table. For general positions, a 10% to 20% improvement in wall clock time and node count is observed.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- MiniZero: Comparative Analysis of AlphaZero and MuZero on Go, Othello, and Atari GamesIEEE Transactions on Games, 2024
- A Local-Pattern Related Look-Up TableIEEE Transactions on Games, 2023
- A general reinforcement learning algorithm that masters chess, shogi, and Go through self-playScience, 2018
- Seki with 2 Liberties per Chain in the Game of GoICGA Journal: The Journal of the Computer Games Community, 2017
- Combinatorial games modeling seki in GODiscrete Mathematics, 2014
- Checkers Is SolvedScience, 2007
- When One Eye is Sufficient: A Static Classification2004
- Games solved: Now and in the futureArtificial Intelligence, 2002
- Proof-number searchArtificial Intelligence, 1994
- Life in the game of GoInformation Sciences, 1976