Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing
Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing
复制标题
用于策略游戏的具有状态抽象的弹性蒙特卡罗树搜索
DOI：
10.1109/cog51982.2022.9893587
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Alexander Dockhorn
中科院分区：
文献类型：
--
作者：
Linjie Xu;Jorge Hurtado Grueso;Dominik Jeurissen;Diego Perez Liebana;Alexander Dockhorn
策略电子游戏以复杂游戏元素所带来的组合搜索空间挑战AI代理。状态抽象是一种降低状态空间复杂性的流行技术。然而，当前游戏的状态抽象方法依赖于领域知识，这使得它们在新游戏中的应用非常昂贵。不需要领域知识的状态抽象方法在规划领域得到了广泛的研究。然而，没有证据表明它们能够很好地适应策略游戏的复杂性。本文提出了一种使用状态抽象来进行策略博弈的算法——弹性MCTS。在弹性MCTS中，树的节点是动态聚类的，首先通过状态抽象逐步分组在一起，然后在达到迭代阈值时分离。这种弹性变化既得益于状态抽象带来的高效搜索，又避免了将状态抽象用于整个搜索的负面影响。为了评估我们的方法，我们使用通用策略游戏平台Stratega来生成不同复杂性的场景。结果表明，弹性MCTS在将树大小减少10倍的同时，在很大程度上优于MCTS基线。代码可以在https://github.com/egg-west/Stratega上找到
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
游戏状态和动作抽象蒙特卡罗树搜索以实现一般策略游戏
DOI：
10.1109/cog52621.2021.9619029
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Dockhorn A
通讯作者：
Dockhorn A
一般策略游戏的投资组合搜索和优化
DOI：
10.1109/cec45853.2021.9504824
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Dockhorn A
通讯作者：
Dockhorn A