构建围棋残局的劫争模式数据库，大幅加速7x7杀尽围棋求解。
Solving 7x7 Killall-Go with Seki Database
- 枚举并存储所有劫争模式，搜索时快速识别以减少计算量。
- 复杂局面求解时间从1天缩短至482秒，效率提升显著。
- 适合研究博弈求解、围棋算法或对搜索优化感兴趣的开发者。
博弈求解是通过假设双方最优决策来确定游戏理论结果的过程。本文针对7x7杀尽围棋（Killall-Go），提出一种显著缩小启发式搜索空间的技术。在围棋和杀尽围棋中，活棋指不会被对手吃掉的棋子组合；互活（seki）指双方因共享气而彼此无法吃掉对方，谁先动手都会自陷险境。因此，准确识别劫争模式可避免主动送死，大幅降低搜索深度。本文系统枚举了预设面积范围内的所有劫争模式，并将其存入劫争表。在搜索过程中，若发现当前局面匹配已知劫争模式，则直接跳过后续分析，从而极大提升求解效率。实验表明，原本需耗时一天无法求解的局面，加入劫争表后可在482秒内完成；对于一般局面，求解时间与节点数均下降10%~20%。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。