Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay
This work addresses gaps in game-solving definitions for AI researchers, though it appears incremental as it builds on existing solving concepts.
The authors tackled the problem of solving combinatorial games by introducing a new 'semi-strongly solved' definition and an efficient algorithm, applying it to semi-strongly solve 6x6 Othello with derived theoretical complexity.
Solving combinatorial games has been a classic research topic in artificial intelligence because solutions can offer essential information to improve gameplay. Several definitions exist for `solving the game,' but they are markedly different regarding computational cost and the detail of insights derived. In this study, we introduce a novel definition called `semi-strongly solved' and propose an algorithm to achieve this type of solution efficiently. This new definition addresses existing gaps because of its intermediate computational cost and the quality of the solution. To demonstrate the potential of our approach, we derive the theoretical computational complexity of our algorithm under a simple condition, and apply it to semi-strongly solve the game of 6x6 Othello. This study raises many new research goals in this research area.