# On some improvements to Unbounded Minimax

arXiv: https://arxiv.org/abs/2505.04525 · HTML: https://mlsanity.com/paper/2505.04525/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 7 May 2025.

## Builds on (most cited first, 5 of 5)

- [Learning to Play Two-Player Perfect-Information Games without Knowledge](https://mlsanity.com/paper/2008.01188/) (2020)
- [Minimax Strikes Back](https://mlsanity.com/paper/2012.10700/) (2020)
- [Completeness of Unbounded Best-First Game Algorithms](https://mlsanity.com/paper/2109.09468/) (2021)
- [Study and improvement of search algorithms in two-players perfect information games](https://mlsanity.com/paper/2505.09639/) (2025)
- [Monte Carlo Game Solver](https://mlsanity.com/paper/2001.05087/) (2020)

## Built on by (most cited first, 2 of 2)

- [Minibal: Balanced Game-Playing Without Opponent Modeling](https://mlsanity.com/paper/2603.23059/) (2026)
- [Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games](https://mlsanity.com/paper/2604.17378/) (2026)

## Abstract (arXiv)

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.