TLDR: The paper introduces an iterative Relevance-Zone (RZ) reduction method (RZR) to make game-solving more efficient. By repeatedly solving game positions under gradually stricter constraints, RZR guides the solver to find optimal strategies that result in smaller RZs. Smaller RZs improve strategy reuse and pruning efficiency, significantly reducing the search space. Experiments on 7×7 Killall-Go show an average RZ size reduction to 85.95% of the original, especially when combined with a modified RZ Pattern Table and a “Heatmap” constraint generation strategy. This method creates reusable knowledge for future game-solving tasks.
Game solving, a distinct challenge from game playing, aims to uncover the optimal strategies for all players and determine the theoretical outcome of a game. While systems like AlphaZero have achieved superhuman performance in game playing, they can still make suboptimal moves. Game solving, on the other hand, seeks perfect play, often by constructing a solution tree that guarantees the game-theoretic value. However, the sheer size of game trees, which grow exponentially, makes many games intractable for brute-force analysis.
To tackle this complexity, researchers often employ techniques that reuse solutions for identical board states, known as transpositions. A more generalized approach involves Relevance-Zones (RZs), which are local regions on the game board that encompass all points critical to a strategy’s outcome. Moves made outside an RZ can be safely ignored, significantly reducing the search space. RZ pattern tables (RZTs) store these patterns and their outcomes, allowing solvers to skip redundant computations when a matching pattern is encountered.
A crucial observation is that RZs are not unique; a single game position might have multiple optimal strategies, each leading to a different RZ pattern. Smaller RZs are highly desirable because they allow for more aggressive pruning of the search tree and increase the likelihood of reusing patterns across different game states. This paper introduces an innovative iterative RZ reduction (RZR) method designed to guide game solvers toward discovering these more compact RZs.
The RZR algorithm works by repeatedly solving the same game position while progressively imposing constraints that restrict the regions where the RZ can form. This iterative process encourages the solver to find alternative strategies that result in smaller, more efficient RZs. The method unfolds in two main phases: an initialization phase, where a baseline solution is found without constraints, and an iterative re-solving phase.
During the iterative phase, new constraints are generated based on the RZ from the most recent successful solution. These constraints involve an ‘outer-region lock’ to prevent the RZ from expanding outward and an ‘inner-point removal’ where a single point within the RZ is banned, forcing the solver to find a solution that doesn’t rely on that specific point. The solver then attempts to re-solve the position under these new restrictions. To prevent endless searches on overly strict constraints, a fixed simulation budget is applied, and the process terminates if no smaller RZs are found in a set number of consecutive iterations.
The paper explores three strategies for selecting which inner point to ban: Random, Erosion, and Heatmap. The Heatmap strategy, which prioritizes points least covered by RZs across the solution tree, proved most effective. Furthermore, the RZ Pattern Table (RZT) is integrated into the RZR process. Unlike traditional RZTs that return any valid match, the modified RZT returns all matching entries, which are then filtered against the current constraints, and the smallest valid RZ is selected. This continuous caching and reuse of RZ patterns across iterations significantly accelerates the solving process and helps populate the RZT with more efficient local patterns.
Experiments were conducted on 10,000 opening positions in 7×7 Killall-Go, a variant of Go. The results demonstrated that the RZR method, particularly when using the Heatmap constraint generation strategy in conjunction with the RZT, reduced the average RZ size to 85.95% of its original size. This reduction leads to more efficient strategy reuse and overall improved search performance. The study also found that positions with larger initial RZs benefited most from the reduction, achieving higher reduction ratios. The reduced RZs can be permanently stored, serving as valuable, reusable knowledge for future game-solving tasks, including larger board sizes or different game openings.
Also Read:
- Interactive Refinement: A New Strategy to Combat Over-fitting in Constraint Acquisition
- Unlocking Exact Nash Equilibria in Multiplayer Imperfect-Information Games
This iterative RZ reduction method offers a significant advancement in game solving, providing a systematic way to discover more compact and efficient strategies. By guiding solvers towards smaller Relevance-Zones, it enhances the reusability of solutions and improves the pruning efficiency of game trees, making complex games more tractable for complete analysis. For more details, you can refer to the full research paper here.
