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

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autoren

Externe Organisationen

  • Queen Mary University of London
Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Titel des Sammelwerks2022 IEEE Conference on Games, CoG 2022
Herausgeber (Verlag)IEEE Computer Society
Seiten369-376
Seitenumfang8
ISBN (elektronisch)9781665459891
ISBN (Print)978-1-6654-5990-7
PublikationsstatusVeröffentlicht - 2022
Veranstaltung2022 IEEE Conference on Games, CoG 2022 - Beijing, China
Dauer: 21 Aug. 202224 Aug. 2022

Publikationsreihe

NameIEEE Conference on Computatonal Intelligence and Games, CIG
Band2022-August
ISSN (Print)2325-4270
ISSN (elektronisch)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

ASJC Scopus Sachgebiete

Zitieren

Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing. / Xu, Linjie; Hurtado-Grueso, Jorge; Jeurissen, Dominic et al.
2022 IEEE Conference on Games, CoG 2022. IEEE Computer Society, 2022. S. 369-376 (IEEE Conference on Computatonal Intelligence and Games, CIG; Band 2022-August).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Xu, L, Hurtado-Grueso, J, Jeurissen, D, Liebana, DP & Dockhorn, A 2022, Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing. in 2022 IEEE Conference on Games, CoG 2022. IEEE Conference on Computatonal Intelligence and Games, CIG, Bd. 2022-August, IEEE Computer Society, S. 369-376, 2022 IEEE Conference on Games, CoG 2022, Beijing, China, 21 Aug. 2022. https://doi.org/10.48550/arXiv.2205.15126, https://doi.org/10.1109/CoG51982.2022.9893587
Xu, L., Hurtado-Grueso, J., Jeurissen, D., Liebana, D. P., & Dockhorn, A. (2022). Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing. In 2022 IEEE Conference on Games, CoG 2022 (S. 369-376). (IEEE Conference on Computatonal Intelligence and Games, CIG; Band 2022-August). IEEE Computer Society. https://doi.org/10.48550/arXiv.2205.15126, https://doi.org/10.1109/CoG51982.2022.9893587
Xu L, Hurtado-Grueso J, Jeurissen D, Liebana DP, Dockhorn A. Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing. in 2022 IEEE Conference on Games, CoG 2022. IEEE Computer Society. 2022. S. 369-376. (IEEE Conference on Computatonal Intelligence and Games, CIG). doi: 10.48550/arXiv.2205.15126, 10.1109/CoG51982.2022.9893587
Xu, Linjie ; Hurtado-Grueso, Jorge ; Jeurissen, Dominic et al. / Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing. 2022 IEEE Conference on Games, CoG 2022. IEEE Computer Society, 2022. S. 369-376 (IEEE Conference on Computatonal Intelligence and Games, CIG).
Download
@inproceedings{11e7cb8dfb1c42f08eae48fa1319e6b1,
title = "Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing",
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",
author = "Linjie Xu and Jorge Hurtado-Grueso and Dominic Jeurissen and Liebana, {Diego Perez} and Alexander Dockhorn",
note = "Funding Information: ACKNOWLEDGMENTS Work supported by UK EPSRC grant EP/T008962/1.; 2022 IEEE Conference on Games, CoG 2022 ; Conference date: 21-08-2022 Through 24-08-2022",
year = "2022",
doi = "10.48550/arXiv.2205.15126",
language = "English",
isbn = "978-1-6654-5990-7",
series = "IEEE Conference on Computatonal Intelligence and Games, CIG",
publisher = "IEEE Computer Society",
pages = "369--376",
booktitle = "2022 IEEE Conference on Games, CoG 2022",
address = "United States",

}

Download

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 -

Von denselben Autoren