Related papers: Strategy Game-Playing with Size-Constrained State Abstraction

Strategy Game-Playing with Size-Constrained State Abstraction

URL: http://arxiv.org/abs/2408.06202v1
Date: Mon, 12 Aug 2024 14:50:18 GMT
Title: Strategy Game-Playing with Size-Constrained State Abstraction
Authors: Linjie Xu, Diego Perez-Liebana, Alexander Dockhorn,
Abstract summary: 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.
Score: 44.99833362998488
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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. In recent works, state abstraction has been applied to search-based game AI and has brought significant performance improvements. State abstraction techniques rely on reducing the search space, e.g., by aggregating similar states. However, the application of these abstractions is hindered because the quality of an abstraction is difficult to evaluate. Previous works hence abandon the abstraction in the middle of the search to not bias the search to a local optimum. This mechanism introduces a hyper-parameter to decide the time to abandon the current state abstraction. In this work, we propose a size-constrained state abstraction (SCSA), an approach that limits the maximum number of nodes being grouped together. We found that with SCSA, the abstraction is not required to be abandoned. Our empirical results on $3$ strategy games show that the SCSA agent outperforms the previous methods and yields robust performance over different games. Codes are open-sourced at \url{https://github.com/GAIGResearch/Stratega}.

Related papers

How to Handle Sketch-Abstraction in Sketch-Based Image Retrieval? [120.49126407479717]
We propose a sketch-based image retrieval framework capable of handling sketch abstraction at varied levels. For granularity-level abstraction understanding, we dictate that the retrieval model should not treat all abstraction-levels equally. Our Acc.@q loss uniquely allows a sketch to narrow/broaden its focus in terms of how stringent the evaluation should be.
arXiv Detail & Related papers (2024-03-11T23:08:29Z)
Are AlphaZero-like Agents Robust to Adversarial Perturbations? [73.13944217915089]
AlphaZero (AZ) has demonstrated that neural-network-based Go AIs can surpass human performance by a large margin. We ask whether adversarial states exist for Go AIs that may lead them to play surprisingly wrong actions. We develop the first adversarial attack on Go AIs that can efficiently search for adversarial states by strategically reducing the search space.
arXiv Detail & Related papers (2022-11-07T18:43:25Z)
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)
Discrete State-Action Abstraction via the Successor Representation [3.453310639983932]
Abstraction is one approach that provides the agent with an intrinsic reward for transitioning in a latent space. Our approach is the first for automatically learning a discrete abstraction of the underlying environment. Our proposed algorithm, Discrete State-Action Abstraction (DSAA), iteratively swaps between training these options and using them to efficiently explore more of the environment.
arXiv Detail & Related papers (2022-06-07T17:37:30Z)
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)
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)
Context-Specific Representation Abstraction for Deep Option Learning [43.68681795014662]
We introduce Context-Specific Representation Abstraction for Deep Option Learning (CRADOL) CRADOL is a new framework that considers both temporal abstraction and context-specific representation abstraction to effectively reduce the size of the search over policy space. Specifically, our method learns a factored belief state representation that enables each option to learn a policy over only a subsection of the state space.
arXiv Detail & Related papers (2021-09-20T22:50:01Z)
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)

This list is automatically generated from the titles and abstracts of the papers in this site.