Strategy Game-Playing with Size-Constrained State Abstraction
This work addresses the problem of search space reduction for AI in strategy games, offering an incremental improvement over existing state abstraction techniques.
The paper tackles the challenge of large search spaces in strategy game AI by proposing a size-constrained state abstraction (SCSA) that limits node grouping, eliminating the need to abandon abstractions during search. Empirical results on three strategy games show that the SCSA agent outperforms previous methods and achieves robust performance across different games.
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 https://github.com/GAIGResearch/Stratega.