Tree Search for Simultaneous Move Games via Equilibrium Approximation

• URL: http://arxiv.org/abs/2406.10411v1
• Date: Fri, 14 Jun 2024 21:02:35 GMT
• Title: Tree Search for Simultaneous Move Games via Equilibrium Approximation
• Authors: Ryan Yu, Alex Olshevsky, Peter Chin,
• Abstract summary: We study the class of simultaneous-move games. Both agents know the game state with the exception of the opponent's move. In this study we answer the question: can we take tree search algorithms trained through self-play from perfect information settings and adapt them to simultaneous move games without significant loss of performance?
• Score: 13.89302587642183
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural network supported tree-search has shown strong results in a variety of perfect information multi-agent tasks. However, the performance of these methods on partial information games has generally been below competing approaches. Here we study the class of simultaneous-move games, which are a subclass of partial information games which are most similar to perfect information games: both agents know the game state with the exception of the opponent's move, which is revealed only after each agent makes its own move. Simultaneous move games include popular benchmarks such as Google Research Football and Starcraft. In this study we answer the question: can we take tree search algorithms trained through self-play from perfect information settings and adapt them to simultaneous move games without significant loss of performance? We answer this question by deriving a practical method that attempts to approximate a coarse correlated equilibrium as a subroutine within a tree search. Our algorithm works on cooperative, competitive, and mixed tasks. Our results are better than the current best MARL algorithms on a wide range of accepted baseline environments.

Related papers

• 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)
• Collusion Detection in Team-Based Multiplayer Games [57.153233321515984]
  We propose a system that detects colluding behaviors in team-based multiplayer games. The proposed method analyzes the players' social relationships paired with their in-game behavioral patterns. We then automate the detection using Isolation Forest, an unsupervised learning technique specialized in highlighting outliers.
  arXiv  Detail & Related papers  (2022-03-10T02:37:39Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  adversarial team games reside in the asymmetric information available to the team members during the play. Our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one.
  arXiv  Detail & Related papers  (2022-01-25T15:07:12Z)
• Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
  We introduce a framework, LMAC, that automates the discovery of the update rule without explicit human design. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance. We show that LMAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO.
  arXiv  Detail & Related papers  (2021-06-04T22:30:25Z)
• 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)
• An Empirical Study on the Generalization Power of Neural Representations Learned via Visual Guessing Games [79.23847247132345]
  This work investigates how well an artificial agent can benefit from playing guessing games when later asked to perform on novel NLP downstream tasks such as Visual Question Answering (VQA) We propose two ways to exploit playing guessing games: 1) a supervised learning scenario in which the agent learns to mimic successful guessing games and 2) a novel way for an agent to play by itself, called Self-play via Iterated Experience Learning (SPIEL)
  arXiv  Detail & Related papers  (2021-01-31T10:30:48Z)
• 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)
• Finding Core Members of Cooperative Games using Agent-Based Modeling [0.0]
  Agent-based modeling (ABM) is a powerful paradigm to gain insight into social phenomena. In this paper, a algorithm is developed that can be embedded into an ABM to allow the agents to find coalition.
  arXiv  Detail & Related papers  (2020-08-30T17:38:43Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
  arXiv  Detail & Related papers  (2020-07-10T09:33:05Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  Combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. We describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards, 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search.
  arXiv  Detail & Related papers  (2020-05-22T18:02:36Z)
• Navigating the Landscape of Multiplayer Games [20.483315340460127]
  We show how network measures applied to response graphs of large-scale games enable the creation of a landscape of games. We illustrate our findings in domains ranging from canonical games to complex empirical games capturing the performance of trained agents pitted against one another.
  arXiv  Detail & Related papers  (2020-05-04T16:58:17Z)

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.