Completeness of Unbounded Best-First Minimax and Descent Minimax

Quentin Cohen-Solal

cs.AIMar 25, 2026

Completeness of Unbounded Best-First Minimax and Descent Minimax

Authors: Quentin Cohen-Solal

Organizations: LAMSADE, Université Paris-Dauphine, PSL, CNRS, Paris, France

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.

Figures & tables

Algorithm 1 $\mathrm{UBFM}$ tree search algorithm with completion (see Algorithm 3 for the definitions of completed_best_action( $s$ ) and backup_resolution( $s$ )).

Algorithm 2 Descent Minimax tree search algorithm with completion (see Algorithm 3 for the definitions of completed_best_action( $s$ ) and backup_resolution( $s$ )).

Algorithm 3 Definition of the algorithms completed_best_action( $s$ , $A$ ), which computes the a priori best child state by using completion from a set of child states $A$ , and backup_resolution( $s$ ), which updates the resolution of $s$ from its child states. The methods use lexicographic ordering.

Algorithm 4 Iteration of a Unbounded Minimax-based algorithm (see Algorithm 3 for the definitions of completed_best_action( $s$ ) and backup_resolution( $s$ )). It is based on two abstract methods: $\mathrm{calculate\_priority\_child}(s,A,\mathcal{S}_{\mathrm{p}},T)$ which must return one of the children of $s$ in $A$ depending on the current search status (i.e. $\mathcal{S}_{\mathrm{p}}$ and $T$ ) and $\mathrm{continue}(s,\mathcal{S}_{\mathrm{p}},T)$ which must return a boolean that determines whether to continue to explore the current line of play deeper or backtrack to the root to potentially explore a new line of play, depending on the current search status (i.e. $\mathcal{S}_{\mathrm{p}}$ and $T$ ). Note: $b$ is True if $s$ has just been extended.

Amazons	Arimaa	Ataxx	Breakthrough	Brazilian	Canadian	Clobber	Connect6	International	Chess	Go 9
1% ±2%	7% ±1%	55% ±2%	-1% ±1%	2% ±0%	6% ±1%	0% ±1%	0% ±2%	4% ±0%	1% ±1%	0% ±2%
Gomoku	Havannah	Hex 11	Hex 13	Hex 19	Lines of A.	Othello 10	Othello 8	Santorini	Surakarta	Xiangqi
0% ±1%	0% ±2%	0% ±1%	0% ±1%	0% ±1%	5% ±1%	24% ±1%	28% ±1%	14% ±2%	4% ±1%	11% ±1%

Table 1: Detailed performance of Unbounded Best-First Minimax with completion against Unbounded Best-First Minimax without completion.

Game-Playing Agents

Game-playing agents use search, learning, and reasoning to choose actions in games with strategic, uncertain, or changing environments.

See all 201 papers

Apr 19, 2026

Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games

In this article, we generalize Unbounded Minimax, the state-of-the-art search algorithm for zero sums two-player games with perfect information to the framework of multiplayer games with perfect information. We experimentally show that this generalized algorithm also achieves better performance than the main multiplayer search algorithms.

Quentin Cohen-Solal

LAMSADE, Universit´e Paris-Dauphine, PSL, CNRS, Paris, France

Game-Playing Agents Tree Search Game Theory

Ask PDF

Nov 10, 2025

Scalable Decision Making for Games of Imperfect Information

Real-world decision-making generally involves hidden information, that is, information that is unknown to one agent but possessed by another. Unfortunately, the presence of large amounts of hidden information renders established reinforcement learning and search approaches ineffective. Even with multimillion-dollar industrial research efforts, top-human-level play at Stratego---a board wargame with hidden information on a massive scale---has remained beyond the reach of artificial intelligence (AI). Here we introduce Ataraxos, an AI for Stratego based on general techniques that we developed for both self-play reinforcement learning and test-time search under hidden information. Ataraxos defeated the most decorated human Stratego player of all time by a large margin---achieving, to our knowledge, the first superhuman result in the game's history---while consuming orders of magnitude less compute and data than previous efforts. Using the same techniques, we built a superhuman AI for Barrage Stratego and state-of-the-art AIs for Hanabi and dou dizhu, all with low cost and high sample efficiency. The success of this approach across adversarial, cooperative and team games establishes a design pattern for reinforcement learning and search that is effective under large amounts of hidden information, a longstanding desideratum of the field of strategic decision-making.

Samuel Sokota, Eugene Vinitsky, Hengyuan Hu +3

Carnegie Mellon University · NYU Tandon School of Engineering · Stanford University +1

Game-Playing Agents Inference-Time Search Self-Play RL Imperfect-Information Games RL for Game AI

Ask PDF

Feb 16, 2026

Decision Making under Imperfect Recall: Algorithms and Benchmarks

In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems.

Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2

Computer Science Dept., Carnegie Mellon University, Pittsburgh, USA · Foundations of Cooperative AI Lab (FOCAL) · Strategy Robot, Inc.; Strategic Machine, Inc.; and Optimized Markets, Inc.

Sequential Decision Making Regret Minimization Constrained Optimization Imperfect-Information Games

Ask PDF

Abstract

Game-Playing Agents

Explore similar work

Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games

Scalable Decision Making for Games of Imperfect Information

Decision Making under Imperfect Recall: Algorithms and Benchmarks