Study and improvement of search algorithms in two-players perfect information games

• URL: http://arxiv.org/abs/2505.09639v1
• Date: Tue, 06 May 2025 19:29:59 GMT
• Title: Study and improvement of search algorithms in two-players perfect information games
• Authors: Quentin Cohen-Solal,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Games, in their mathematical sense, are everywhere (game industries, economics, defense, education, chemistry, biology, ...).Search algorithms in games are artificial intelligence methods for playing such games. Unfortunately, there is no study on these algorithms that evaluates the generality of their performance. We propose to address this gap in the case of two-player zero-sum games with perfect information. Furthermore, we propose a new search algorithm and we show that, for a short search time, it outperforms all studied algorithms on all games in this large experiment and that, for a medium search time, it outperforms all studied algorithms on 17 of the 22 studied games.

Related papers

• People use fast, goal-directed simulation to reason about novel games [71.0171482296852]
  We study how people reason about a range of simple but novel Connect-N style board games.<n>We ask people to judge how fair and how fun the games are from very little experience.
  arXiv  Detail & Related papers  (2024-07-19T07:59:04Z)
• 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)
• 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)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• 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)
• 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)
• Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms [0.6749750044497732]
  Recent advancements in algorithms for sequential decision-making under imperfect information have shown remarkable success in large games. These algorithms traditionally formalize the games using the extensive-form game formalism. We show that a popular workaround involves using a specialized representation based on player specific information-state trees.
  arXiv  Detail & Related papers  (2021-12-20T22:34:19Z)
• Student of Games: A unified learning algorithm for both perfect and imperfect information games [22.97853623156316]
  Student of Games is an algorithm that combines guided search, self-play learning, and game-theoretic reasoning. We prove that Student of Games is sound, converging to perfect play as available computation and approximation capacity increases. Student of Games reaches strong performance in chess and Go, beats the strongest openly available agent in heads-up no-limit Texas hold'em poker, and defeats the state-of-the-art agent in Scotland Yard.
  arXiv  Detail & Related papers  (2021-12-06T17:16:24Z)
• 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)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• 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.