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
翻译:策略性游戏用复杂的游戏元素造成的组合搜索空间对AI代理器提出挑战。 国家抽象化是一种受欢迎的技术,可以降低国家空间的复杂性。 但是, 当前的游戏抽象化方法取决于域知识, 使游戏应用到新游戏费用昂贵。 在规划领域广泛研究不需要域知识的国家抽象化方法。 但是, 没有证据表明它们与战略游戏的复杂性相比范围很广。 在本文中, 我们提出使用国家抽象来玩战略游戏的高级战略游戏MSTS算法。 在高级的MCTS 中, 树的节点是动态组合的, 首先是州抽象化, 然后在达到迭代阈值时分离。 州抽象化带来的有效搜索有利于弹性变化, 但是避免了整个搜索使用状态抽象的负面影响。 为了评估我们的方法, 我们利用了通用战略游戏平台Stratega 来生成不同复杂情景。 结果显示, 弹性的MCTS超越了以大边距构建的 MCTS基线, 同时将树的树体大小减少10美元系数。 代码可以在 http://Sgestarate: http://Sqast/starate.