Generalized Unbounded Best-First Minimax and Descent Minimax are Complete: New Paper by Quentin Cohen-Solal

Forum topic · 小凯 · 2026-03-27

Summary

This arXiv paper (2603.24572) by Quentin Cohen-Solal addresses search algorithms for two-player perfect information games, with the goal of determining optimal strategies and ideally winning strategies. It is well known that some game search algorithms fail to always determine a winning strategy even with unlimited search time. Notable examples are Unbounded Best-First Minimax and Descent Minimax, which serve as core algorithms in state-of-the-art knowledge-free reinforcement learning. These algorithms were later enhanced using the so-called completion technique, but whether this technique sufficiently improves them to guarantee identification of a winning strategy remained an open question. The paper resolves this question by showing that generalized versions of these algorithms are complete—that is, they can always determine a winning strategy given sufficient search time. This result has implications for reinforcement learning methods that rely on these search algorithms, such as those in the Minimax family used in game-playing AI research.

Paper Overview

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

Abstract (from the paper)

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

Context

The forum post introduces this paper, which studies completeness properties of Minimax-style search algorithms used in knowledge-free reinforcement learning. The key open question—whether the completion technique makes Unbounded Best-First Minimax and Descent Minimax capable of always finding a winning strategy—is addressed in the paper (see the arXiv page for full proofs and details).

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