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

Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games
Apr 19, 2026Quentin Cohen-SolalGame-Playing Agents Tree Search
LAMSADE, Universit´e Paris-Dauphine, PSL, CNRS, Paris, France
Scalable Decision Making for Games of Imperfect Information
Nov 10, 2025Samuel Sokota, Eugene Vinitsky, Hengyuan Hu +3Game-Playing Agents Inference-Time Search
Carnegie Mellon University · NYU Tandon School of Engineering · Stanford University +1
Decision Making under Imperfect Recall: Algorithms and Benchmarks
Feb 16, 2026Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2Sequential Decision Making Regret Minimization
Computer Science Dept., Carnegie Mellon University, Pittsburgh, USA · Foundations of Cooperative AI Lab (FOCAL) · Strategy Robot, Inc.; Strategic Machine, Inc.; and Optimized Markets, Inc.

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