Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing

• URL: http://arxiv.org/abs/2205.15126v1
• Date: Mon, 30 May 2022 14:18:45 GMT
• Title: Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing
• Authors: Linjie Xu, Jorge Hurtado-Grueso, Dominic Jeurissen, Diego Perez Liebana, Alexander Dockhorn
• Abstract summary: 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.
• Score: 58.720142291102135
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Strategy video games challenge AI agents with their combinatorial search space caused by complex game elements. State abstraction is a popular technique that reduces the state space complexity. However, current state abstraction methods for games depend on domain knowledge, making their application to new games expensive. State abstraction methods that require no domain knowledge are studied extensively in the planning domain. However, no evidence shows they scale well with the complexity of strategy games. In this paper, we propose Elastic MCTS, an algorithm that uses state abstraction to play strategy games. In Elastic MCTS, the nodes of the tree are clustered dynamically, first grouped together progressively by state abstraction, and then separated when an iteration threshold is reached. The elastic changes benefit from efficient searching brought by state abstraction but avoid the negative influence of using state abstraction for the whole search. To evaluate our method, we make use of the general strategy games platform Stratega to generate scenarios of varying complexity. Results show that Elastic MCTS outperforms MCTS baselines with a large margin, while reducing the tree size by a factor of $10$. Code can be found at: https://github.com/egg-west/Stratega

Related papers

• Strategy Game-Playing with Size-Constrained State Abstraction [44.99833362998488]
  Playing strategy games is a challenging problem for artificial intelligence (AI) One of the major challenges is the large search space due to a diverse set of game components. State abstraction has been applied to search-based game AI and has brought significant performance improvements.
  arXiv  Detail & Related papers  (2024-08-12T14:50:18Z)
• Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions [89.89612827542972]
  This paper proposes a variant of Monte-Carlo tree search (MCTS) that spends more search time on harder states and less search time on simpler states adaptively. We evaluate the performance and computations on $9 times 9$ Go board games and Atari games. Experiments show that our method can achieve comparable performances to the original search algorithm while requiring less than $50%$ search time on average.
  arXiv  Detail & Related papers  (2022-10-23T06:39:20Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• Split Moves for Monte-Carlo Tree Search [6.026538435601293]
  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.
  arXiv  Detail & Related papers  (2021-12-14T22:06:54Z)
• MDP Abstraction with Successor Features [14.433551477386318]
  We study abstraction in the context of reinforcement learning, in which agents may perform state or temporal abstractions. In this work, we propose successor abstraction, a novel abstraction scheme building on successor features. Our successor abstraction allows us to learn abstract environment models with semantics that are transferable across different environments.
  arXiv  Detail & Related papers  (2021-10-18T11:35:08Z)
• Learning Abstract Models for Strategic Exploration and Fast Reward Transfer [85.19766065886422]
  We learn an accurate Markov Decision Process (MDP) over abstract states to avoid compounding errors. Our approach achieves strong results on three of the hardest Arcade Learning Environment games. We can reuse the learned abstract MDP for new reward functions, achieving higher reward in 1000x fewer samples than model-free methods trained from scratch.
  arXiv  Detail & Related papers  (2020-07-12T03:33:50Z)
• 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)
• 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.