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

• URL: http://arxiv.org/abs/2604.17378v1
• Date: Sun, 19 Apr 2026 11:03:45 GMT
• Title: Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games
• Abstract summary: 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.<n>We experimentally show that this generalized algorithm also achieves better performance than the main multiplayer search algorithms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• 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)
• Playing Board Games with the Predict Results of Beam Search Algorithm [0.0]
  This paper introduces a novel algorithm for two-player deterministic games with perfect information, which we call PROBS (Predict Results of Beam Search) We evaluate the performance of our algorithm across a selection of board games, where it consistently demonstrates an increased winning ratio against baseline opponents. A key result of this study is that the PROBS algorithm operates effectively, even when the beam search size is considerably smaller than the average number of turns in the game.
  arXiv  Detail & Related papers  (2024-04-23T20:10:27Z)
• A Generalized Extensive-Form Fictitious Play Algorithm [0.0]
  We introduce a simple extensive-form algorithm for finding equilibria of two-player, zero-sum games. We compare its performance to that of a similar extensive-form fictitious play algorithm and a counter-factual regret minimization algorithm.
  arXiv  Detail & Related papers  (2023-10-14T20:18:49Z)
• 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)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning. We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures. Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
  arXiv  Detail & Related papers  (2022-01-30T06:10:04Z)
• 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)
• Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games [95.70078702838654]
  This paper studies natural extensions of Natural Policy Gradient algorithm for solving two-player zero-sum games. We thoroughly characterize the algorithms' performance in terms of the number of samples, number of iterations, concentrability coefficients, and approximation error.
  arXiv  Detail & Related papers  (2021-02-17T17:49:57Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-02-19T21:36:58Z)
• Fast Complete Algorithm for Multiplayer Nash Equilibrium [1.7132914341329848]
  We describe a new complete algorithm for computing Nash equilibrium in multiplayer general-sum games. We demonstrate that the algorithm runs significantly faster than the prior fastest complete algorithm on several game classes previously studied.
  arXiv  Detail & Related papers  (2020-02-11T23:42:14Z)

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.