On some improvements to Unbounded Minimax

Quentin Cohen-Solal, Tristan CazenavearXiv 2025 · DOI · arXiv

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:

  1. Transposition Tables (TT): Standard state-caching to prevent redundant evaluations and transform the search tree into a Directed Acyclic Graph (DAG).
  2. 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.
  3. Heuristic vs. Terminal Evaluation: Comparing the use of exact win/loss/draw status for terminal nodes against using the learned heuristic function.
  4. 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.

Aggregate performance impact of removing key UBFM features.

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.

Detailed game-by-game performance breakdown for UBFM variants.

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

Abstract

This paper presents the first experimental evaluation of four previously untested modifications of Unbounded Best-First Minimax algorithm. This algorithm explores the game tree by iteratively expanding the most promising sequences of actions based on the current partial game tree. We first evaluate the use of transposition tables, which convert the game tree into a directed acyclic graph by merging duplicate states. Second, we compare the original algorithm by Korf & Chickering with the variant proposed by Cohen-Solal, which differs in its backpropagation strategy: instead of stopping when a stable value is encountered, it updates values up to the root. This change slightly improves performance when value ties or transposition tables are involved. Third, we assess replacing the exact terminal evaluation function with the learned heuristic function. While beneficial when exact evaluations are costly, this modification reduces performance in inexpensive settings. Finally, we examine the impact of the completion technique that prioritizes resolved winning states and avoids resolved losing states. This technique also improves performance. Overall, our findings highlight how targeted modifications can enhance the efficiency of Unbounded Best-First Minimax.
BibTeX
@misc{cohensolal2025some,
  author = {Quentin Cohen-Solal and Tristan Cazenave},
  title = {{On some improvements to Unbounded Minimax}},
  year = {2025},
  eprint = {2505.04525},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.04525},
}
Figure