تقرير
A Novel Approach to Solving Goal-Achieving Problems for Board Games
| العنوان: | A Novel Approach to Solving Goal-Achieving Problems for Board Games |
|---|---|
| المؤلفون: | Shih, Chung-Chin, Wu, Ti-Rong, Wei, Ting Han, Wu, I-Chen |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Artificial Intelligence, Computer Science - Machine Learning |
| الوصف: | 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. Comment: Accepted by AAAI2022. In this version, supplementary materials are added |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2112.02563 |
| رقم الأكسشن: | edsarx.2112.02563 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |