Split Moves for Monte-Carlo Tree Search
- URL: http://arxiv.org/abs/2112.07761v1
- Date: Tue, 14 Dec 2021 22:06:54 GMT
- Title: Split Moves for Monte-Carlo Tree Search
- Authors: Jakub Kowalski, Maksymilian Mika, Wojciech Pawlik, Jakub Sutowicz,
Marek Szyku{\l}a, Mark H. M. Winands
- Abstract summary: In many games, moves consist of several decisions made by the player. These decisions can be viewed as separate moves, which is already a common practice in multi-action games for efficiency reasons.
We aim to answer how to effectively use split moves within Monte-Carlo Tree Search (MCTS) and what is the practical impact of split design on agents' strength.
- Score: 6.026538435601293
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In many games, moves consist of several decisions made by the player. These
decisions can be viewed as separate moves, which is already a common practice
in multi-action games for efficiency reasons. Such division of a player move
into a sequence of simpler / lower level moves is called \emph{splitting}. So
far, split moves have been applied only in forementioned straightforward cases,
and furthermore, there was almost no study revealing its impact on agents'
playing strength. Taking the knowledge-free perspective, we aim to answer how
to effectively use split moves within Monte-Carlo Tree Search (MCTS) and what
is the practical impact of split design on agents' strength. This paper
proposes a generalization of MCTS that works with arbitrarily split moves. We
design several variations of the algorithm and try to measure the impact of
split moves separately on efficiency, quality of MCTS, simulations, and
action-based heuristics. The tests are carried out on a set of board games and
performed using the Regular Boardgames General Game Playing formalism, where
split strategies of different granularity can be automatically derived based on
an abstract description of the game. The results give an overview of the
behavior of agents using split design in different ways. We conclude that split
design can be greatly beneficial for single- as well as multi-action games.
Related papers
- Tree Search for Simultaneous Move Games via Equilibrium Approximation [13.89302587642183]
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?
arXiv Detail & Related papers (2024-06-14T21:02:35Z) - A Marriage between Adversarial Team Games and 2-player Games: Enabling
Abstractions, No-regret Learning, and Subgame Solving [31.29335755664997]
emphEx ante correlation is becoming the mainstream approach for emphsequential adversarial team games, where a team of players faces another team in a zero-sum game.
This work shows that we can recover from this weakness by bridging the gap between sequential adversarial team games and 2-player games.
We propose a new, suitable game representation that we call emphteam-public-information, in which a team is represented as a single coordinator who only knows information common to the whole team and prescribes to each member an action for any possible private state.
arXiv Detail & Related papers (2022-06-18T10:02:08Z) - Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game
Playing [58.720142291102135]
Strategy video games challenge AI agents with their search space caused by complex game elements.
State abstraction is a popular technique that reduces the state space complexity.
We propose Elastic MCTS, an algorithm that uses state abstraction to play strategy games.
arXiv Detail & Related papers (2022-05-30T14:18:45Z) - Off-Beat Multi-Agent Reinforcement Learning [62.833358249873704]
We investigate model-free multi-agent reinforcement learning (MARL) in environments where off-beat actions are prevalent.
We propose a novel episodic memory, LeGEM, for model-free MARL algorithms.
We evaluate LeGEM on various multi-agent scenarios with off-beat actions, including Stag-Hunter Game, Quarry Game, Afforestation Game, and StarCraft II micromanagement tasks.
arXiv Detail & Related papers (2022-05-27T02:21:04Z) - 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) - MCTS Based Agents for Multistage Single-Player Card Game [0.0]
The article presents the use of Monte Carlo Tree Search algorithms for the card game Lord of the Rings.
The main challenge was the complexity of the game mechanics, in which each round consists of 5 decision stages and 2 random stages.
To test various decision-making algorithms, a game simulator has been implemented.
arXiv Detail & Related papers (2021-09-24T10:56:54Z) - 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) - TotalBotWar: A New Pseudo Real-time Multi-action Game Challenge and
Competition for AI [62.997667081978825]
TotalBotWar is a new pseudo real-time multi-action challenge for game AI.
The game is based on the popular TotalWar games series where players manage an army to defeat the opponent's one.
arXiv Detail & Related papers (2020-09-18T09:13:56Z) - 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)
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.