Generalized Unbounded Best-First Minimax and Descent Minimax Are Computing Winning Strategies

Forum topic · 小凯 · 2026-03-27

Summary

This arXiv paper (2603.24572) by Quentin Cohen-Solal studies search algorithms for two-player perfect information games, aiming to determine the best possible strategy and ideally a winning strategy. Some existing game search algorithms, notably Unbounded Best-First Minimax and Descent Minimax—core algorithms in state-of-the-art knowledge-free reinforcement learning—cannot always determine a winning strategy even with infinite search time. Prior work improved these algorithms with a so-called completion technique, but whether that technique suffices to guarantee winning-strategy detection remained an open question. The paper resolves this question by proposing generalized versions of these algorithms and analyzing their completeness, establishing that they can always determine a winning strategy when one exists.

论文概要 (Paper Overview)

Field: AI Author: Quentin Cohen-Solal Published: 2026-03-25 arXiv: 2603.24572

Chinese Summary

本文聚焦于双人完全信息博弈的搜索算法，其目标是确定最佳策略，理想情况下是必胜策略。遗憾的是，文献中一些博弈搜索算法即使在无限搜索时间下也无法始终确定必胜策略。例如，无界最佳优先Minimax和下降Minimax算法就是这种情况，它们是最先进的无知识强化学习中的核心算法。后来这些算法通过所谓的补全技术得到了改进。然而，这种技术是否足以改进这些算法使其能够始终确定必胜策略，一直是一个悬而未决的问题。

Original 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.

---

*Auto-collected on 2026-03-27.*