Abstract
Solving complex board games exactly requires proving the outcome from any given state under perfect play. Traditional deterministic solvers like Alpha-Beta search depend heavily on move ordering to prune the search space effectively. This paper introduces a hybrid approach that utilizes Monte Carlo Tree Search (MCTS) and online reinforcement learning to "scout" optimal moves, significantly enhancing the move-ordering phase of Alpha-Beta solvers. The resulting algorithm achieves orders of magnitude speedups, enabling the exact solution of games like 5x5 Nogo for the first time.
Introduction: The Challenge of Exact Solving
In game AI, a distinction exists between playing a game well and solving it. Solving a game involves a mathematical proof of the outcome (Win, Loss, or Draw). Traditional exact solvers, such as Alpha-Beta ($\alpha\beta$) search, are deterministic, but their efficiency is tied to move ordering. If the solver evaluates the best move first, it can prune vast branches of the search tree, leading to exponential performance gains.
While heuristics like the "History Heuristic" have been standard for decades, they often struggle with high-complexity games. Conversely, MCTS—the backbone of systems like AlphaZero—excels at identifying strong moves through probabilistic simulation but lacks the framework for formal proof. This research bridges the gap by using MCTS "intuition" to guide the "certainty" of exact solvers.
Methods: Integrating MCTS and Alpha-Beta
The proposed algorithm integrates MCTS and online policy learning into an Iterative Deepening Alpha-Beta solver. The process involves four key components:
- MCTS Warm-up: Before the exact search begins, a short MCTS phase identifies promising moves based on simulations.
- Playout Policy Adaptation (PPAF): An online learning technique adjusts move feature weights (e.g., piece capture) in real-time during MCTS playouts.
- Hybrid Ordering Function (
orderMC): The $\alpha\beta$ solver prioritizes moves based on MCTS simulation counts or falls back to PPAF-learned weights. - Domain Heuristics: Simple hard-coded rules are applied for specific games to further refine the search.
Experimental Evaluation
The algorithm was tested across various board games, including Atarigo, Nogo, Breakthrough, and Domineering. The research specifically focused on "Misere" versions of these games, where the objective is to lose. These are notoriously difficult to solve because players avoid terminal states, resulting in deeper search trees.
Key Results
The Monte Carlo move ordering (MC) demonstrated dramatic improvements over standard Iterative Deepening Alpha-Beta with Transposition Tables (ID $\alpha\beta$ TT).
- Atarigo 5x5: While standard solvers timed out after 24 hours, the MC-enhanced solver reached a solution in just 12.79 seconds.
- Nogo 5x5: This study represents the first time the 5x5 Nogo board has been solved, a feat requiring the evaluation of over 46 billion moves over 17 hours.
- Generality: The algorithm outperformed state-of-the-art parallel Proof Number Search methods in games like Breakthrough 5x5 by a factor of seven.
Conclusion and Future Directions
The primary insight of this work is that MCTS is highly effective as a "scout" for exact solvers. By identifying the neighborhood of the optimal solution, it allows $\alpha\beta$ search to focus its computational power where it matters most. Furthermore, the use of online learning (PPAF) removes the need for massive pre-trained models, making the approach lightweight and generalizable. Future work may involve parallelizing the search processes and applying these techniques to even more complex domains like Chess.
Summary updated