Details
| Original language | English |
|---|---|
| Title of host publication | 2022 IEEE Conference on Games, CoG 2022 |
| Publisher | IEEE Computer Society |
| Pages | 369-376 |
| Number of pages | 8 |
| ISBN (electronic) | 9781665459891 |
| ISBN (print) | 978-1-6654-5990-7 |
| Publication status | Published - 2022 |
| Event | 2022 IEEE Conference on Games, CoG 2022 - Beijing, China Duration: 21 Aug 2022 → 24 Aug 2022 |
Publication series
| Name | IEEE Conference on Computatonal Intelligence and Games, CIG |
|---|---|
| Volume | 2022-August |
| ISSN (Print) | 2325-4270 |
| ISSN (electronic) | 2325-4289 |
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
Keywords
- Game Artificial Intelligence, Monte Carlo Tree Search, State Abstraction, Strategy Games
ASJC Scopus subject areas
- Computer Science(all)
- Artificial Intelligence
- Computer Science(all)
- Computer Graphics and Computer-Aided Design
- Computer Science(all)
- Computer Vision and Pattern Recognition
- Computer Science(all)
- Human-Computer Interaction
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
2022 IEEE Conference on Games, CoG 2022. IEEE Computer Society, 2022. p. 369-376 (IEEE Conference on Computatonal Intelligence and Games, CIG; Vol. 2022-August).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing
AU - Xu, Linjie
AU - Hurtado-Grueso, Jorge
AU - Jeurissen, Dominic
AU - Liebana, Diego Perez
AU - Dockhorn, Alexander
N1 - Funding Information: ACKNOWLEDGMENTS Work supported by UK EPSRC grant EP/T008962/1.
PY - 2022
Y1 - 2022
N2 - 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
AB - 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
KW - Game Artificial Intelligence
KW - Monte Carlo Tree Search
KW - State Abstraction
KW - Strategy Games
UR - http://www.scopus.com/inward/record.url?scp=85139158425&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2205.15126
DO - 10.48550/arXiv.2205.15126
M3 - Conference contribution
AN - SCOPUS:85139158425
SN - 978-1-6654-5990-7
T3 - IEEE Conference on Computatonal Intelligence and Games, CIG
SP - 369
EP - 376
BT - 2022 IEEE Conference on Games, CoG 2022
PB - IEEE Computer Society
T2 - 2022 IEEE Conference on Games, CoG 2022
Y2 - 21 August 2022 through 24 August 2022
ER -