Completeness of Unbounded Best-First Minimax and Descent Minimax

• URL: http://arxiv.org/abs/2603.24572v1
• Date: Wed, 25 Mar 2026 17:50:31 GMT
• Title: Completeness of Unbounded Best-First Minimax and Descent Minimax
• Abstract summary: This article focuses on search algorithms for two-player perfect information games.<n>We show that any algorithm of this class of algorithms computes the best strategy.<n>We experimentally show that the completion technique improves winning performance.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Who is the Winning Algorithm? Rank Aggregation for Comparative Studies [4.501091570166657]
  We introduce a novel conceptual framework for estimating the win probability for each of the m algorithms.<n>Our proposed framework significantly improves upon currently known methods in synthetic and real-world examples.
  arXiv  Detail & Related papers  (2026-01-04T20:52:47Z)
• Study and improvement of search algorithms in two-players perfect information games [0.0]
  We propose a new search algorithm for two-player zero-sum games with perfect information.<n>We show that, for a short search time, it outperforms all studied algorithms on all games in this large experiment.<n>We also show that, for a medium search time, it outperforms all studied algorithms on 17 of the 22 studied games.
  arXiv  Detail & Related papers  (2025-05-06T19:29:59Z)
• Research Re: search & Re-search [0.0]
  This study takes a closer look at a depth-first algorithm, AB, and a best-first algorithm, SSS. The prevailing opinion on these algorithms is that SSS offers the potential for a more efficient search, but that its complicated formulation and exponential memory requirements render it impractical.
  arXiv  Detail & Related papers  (2024-03-20T16:08:57Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  We introduce an alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. We derive a provably sound search algorithm for fully cooperative games based on mirror descent and a search algorithm for adversarial games based on magnetic mirror descent.
  arXiv  Detail & Related papers  (2023-04-25T20:28:55Z)
• Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge [5.071342645033634]
  We extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information. We evaluate them on the game Ein wurfelt! against state-of-the-art algorithms. It is our generalization of Descent which obtains the best results.
  arXiv  Detail & Related papers  (2023-02-08T20:27:45Z)
• The Information Geometry of Unsupervised Reinforcement Learning [133.20816939521941]
  Unsupervised skill discovery is a class of algorithms that learn a set of policies without access to a reward function. We show that unsupervised skill discovery algorithms do not learn skills that are optimal for every possible reward function.
  arXiv  Detail & Related papers  (2021-10-06T13:08:36Z)
• Completeness of Unbounded Best-First Game Algorithms [0.0]
  We prove the completeness of two game search algorithms: best-first minimax with completion and descent with completion. We generalize these algorithms in the context of perfect information multiplayer games.
  arXiv  Detail & Related papers  (2021-09-11T23:13:52Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors. We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
  arXiv  Detail & Related papers  (2021-07-20T11:23:21Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds [48.312484940846]
  We revisit the problem of online learning with sleeping experts/bandits. In each time step, only a subset of the actions are available for the algorithm to choose from. We give an algorithm that provides a no-approximate-regret guarantee for the general sleeping expert/bandit problems.
  arXiv  Detail & Related papers  (2020-03-07T02:13:21Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.