Loading the document
Key insights
5 slides
The game
Solving 7x7 Killall-Go is computationally intensive.
7x7 Killall-Go is a variant of Go where Black aims to capture all White stones.
Key bottleneck. Seki detection is a critical computational bottleneck in game solving.
1 / 5
- 01Integrating a pre-computed seki database into a 7x7 Killall-Go solver increases the success rate for positions containing seki patterns from below 7% to over 85%.See it on page 7
- 02The use of a seki lookup table enables the resolution of previously unsolvable positions within 482 seconds, compared to a 24-hour timeout threshold.See it on page 10
- 03General performance metrics show a 10% to 20% improvement in both wall-clock time and node count when utilizing the database for game solving.See it on page 8
- 04The research generated a database of over 250,000 verified seki patterns by enumerating local configurations for area sizes ranging from 5 to 8.See it on page 5
- 05Seki detection is identified as a critical computational bottleneck in game solving, which can be effectively mitigated by shifting verification from online search to offline lookup.See it on page 10
Ask AI about this report
Summary
The research addresses the computational challenge of solving 7x7 Killall-Go, a variant of Go where Black attempts to capture all White stones. The primary thesis is that integrating a pre-computed seki (mutual life) database significantly reduces the heuristic search space and improves the efficiency of game-solving algorithms. By identifying seki patterns offline and storing them in a lookup table, the solver can recognize terminal positions during search without requiring exhaustive, time-intensive verification.
The methodology involves enumerating all potential local seki patterns for area sizes ranging from 5 to 8. These patterns are verified using a depth-first search approach to confirm whether they constitute a seki, resulting in a database of over 250,000 verified patterns. This database is then integrated into an online fine-tuning distributed solver. The study evaluates performance across ten benchmark openings, comparing solving times and node counts with and without the seki database.
Key findings demonstrate substantial performance gains. In extreme cases, positions that were previously unsolvable within a 24-hour window were resolved in as little as 482 seconds using the database. For general positions, the inclusion of the seki table resulted in a 10% to 20% improvement in both wall-clock time and node count. Furthermore, analysis of job-specific data indicates that when seki patterns are present, the database increases the solving success rate from below 7% to over 85%. The results confirm that seki detection is a critical bottleneck in game solving, and the use of an endgame database provides a scalable, efficient solution for complex board game analysis.
