Completeness of Unbounded Best-First Minimax and Descent Minimax

Computer Science > Artificial Intelligence [Submitted on 25 Mar 2026] Completeness of Unbounded Best-First Minimax and Descent Minimax Quentin Cohen-Solal 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. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2603.24572 [cs.AI]   (or arXiv:2603.24572v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2603.24572 Focus to learn more Submission history From: Quentin Cohen-Solal [view email] [v1] Wed, 25 Mar 2026 17:50:31 UTC (472 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-03 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)