Abstract
Unbounded Best-First Minimax (UBFM) is a search paradigm that combines the best-first expansion strategy of Monte Carlo Tree Search (MCTS) with the deterministic value propagation of traditional minimax search. This paper presents the first rigorous experimental evaluation of four key modifications to UBFM: transposition tables, full backpropagation, completion techniques, and terminal state evaluation. Testing across a diverse suite of 22 games reveals that these enhancements significantly improve performance and robustness.
Introduction
In game-playing AI, Alpha-Beta pruning and MCTS have long been the dominant search paradigms. Recently, Unbounded Best-First Minimax (UBFM) has emerged as a powerful alternative, serving as the core of the Athénan system. UBFM's ability to outperform AlphaZero-style algorithms in specific domains while maintaining computational efficiency makes it a compelling subject for optimization. This study evaluates several proposed enhancements to determine their impact on search quality across a wide variety of game types.
Methods
We evaluate four specific algorithmic modifications to the baseline UBFM:
- Transposition Tables (TT): Standard state-caching to prevent redundant evaluations and transform the search tree into a Directed Acyclic Graph (DAG).
- Full Backpropagation: Unlike the original "lazy" approach by Korf & Chickering, which stops updates when a node's value remains unchanged, "Full" backpropagation updates values all the way to the root.
- Heuristic vs. Terminal Evaluation: Comparing the use of exact win/loss/draw status for terminal nodes against using the learned heuristic function.
- Completion: A technique that explicitly labels resolved states (guaranteed wins/losses) to prevent the search from stalling in local fixpoints.
Experimental Setup
The evaluation utilized a benchmark suite of 22 deterministic, perfect-information, zero-sum games, including Chess, Go (9x9), Othello, Amazons, and Hex. Approximately 2,700 matches were conducted per game, employing six distinct sets of evaluation functions to ensure heuristic independence.
Key Results
Performance was measured by disabling specific features in a fully-optimized "benchmark adversary" and observing the resulting score drop.
As shown in the aggregate results, Completion is the most critical single feature, with its removal leading to a mean score drop of -5.03. Transposition Tables are also essential (-4.15 drop), confirming the necessity of state reuse. Furthermore, the "Full" backpropagation strategy significantly outperformed the original Korf & Chickering "lazy" update method (-2.37).
Game-Specific Analysis
While the improvements were generally beneficial across the board, certain games exhibited extreme sensitivity to specific features.
For instance, in Xiangqi, the removal of exact terminal evaluations caused a catastrophic performance drop of -89%. This suggests that for games with complex end-state rules, the precision of terminal evaluation is paramount. Conversely, in games where terminal status is expensive to compute, a heuristic approach might be viable if it allows for significantly higher search volume.
Conclusion
The experimental data confirms that modern UBFM implementations should prioritize the inclusion of transposition tables, completion logic, and full backpropagation. These features address the "lazy" backpropagation trap and the "fixpoint" problem, ensuring the algorithm reliably finds winning lines. Future work should investigate the interaction of these techniques with deep neural network heuristics and their applicability to stochastic environments.
Summary updated