2021/12/05 by Chung-Chin Shih, Shih, Chung-Chin, Ti-Rong Wu +5 · 2 citations
Computer Science · Economics, Econometrics and Finance · Psychology · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #Educational Games and Gamification #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.2112.02563
openalex publication_date 2021/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Goal-achieving problems are puzzles that set up a specific situation with a clear objective. An example that is well-studied is the category of life-and-death (L&D) problems for Go, which helps players hone their skill of identifying region safety. Many previous methods like lambda search try null moves first, then derive so-called relevance zones (RZs), outside of which the opponent does not need to search. This paper first proposes a novel RZ-based approach, called the RZ-Based Search (RZS), to solving L&D problems for Go. RZS tries moves before determining whether they are null moves post-hoc. This means we do not need to rely on null move heuristics, resulting in a more elegant algorithm, so that it can also be seamlessly incorporated into AlphaZero's super-human level play in our solver. To repurpose AlphaZero for solving, we also propose a new training method called Faster to Life (FTL), which modifies AlphaZero to entice it to win more quickly. We use RZS and FTL to solve L&D problems on Go, namely solving 68 among 106 problems from a professional L&D book while a previous program solves 11 only. Finally, we discuss that the approach is generic in the sense that RZS is applicable to solving many other goal-achieving problems for board games.