Completeness of Unbounded Best-First Minimax and Descent Minimax
2026-03-25 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors studied search algorithms used to find the best moves in two-player games where both players know everything about the game. They looked at some existing algorithms that sometimes fail to always find a winning strategy, even if given unlimited time. By adding a technique called completion, they improved the algorithms and proved that these improved versions can always find the best strategy. They also ran experiments showing this technique helps win more often in practice.
two-player gamesperfect informationsearch algorithmsbest strategywinning strategyUnbounded Best-First MinimaxDescent Minimaxcompletion techniquereinforcement learningalgorithm improvement
Authors
Quentin Cohen-Solal
Abstract
In this article, we focus on search algorithms for two-player perfect information games, whose objective is to determine the best possible strategy, and ideally a winning strategy. Unfortunately, some search algorithms for games in the literature are not able to always determine a winning strategy, even with an infinite search time. This is the case, for example, of the following algorithms: Unbounded Best-First Minimax and Descent Minimax, which are core algorithms in state-of-the-art knowledge-free reinforcement learning. They were then improved with the so-called completion technique. However, whether this technique sufficiently improves these algorithms to allow them to always determine a winning strategy remained an open question until now. To answer this question, we generalize the two algorithms (their versions using the completion technique), and we show that any algorithm of this class of algorithms computes the best strategy. Finally, we experimentally show that the completion technique improves winning performance.