Playing Multiaction Adversarial Games: Online Evolutionary Planning Versus Tree Search
Playing Multiaction Adversarial Games: Online Evolutionary Planning Versus Tree Search
复制标题
玩多动作对抗游戏：在线进化规划与树搜索
DOI：
--
复制
发表时间：
2018
影响因子：
2.3
通讯作者：
J. Togelius
中科院分区：
文献类型：
--
作者：
Niels Justesen;Tobias Mahlmann;S. Risi;J. Togelius
我们解决了玩回合制多行动对抗游戏的问题，其中包括许多具有极高分支因素的策略游戏，因为玩家每个回合都要采取多个行动。这导致了标准树搜索方法的崩溃，包括蒙特卡罗树搜索（MCTS），因为它们无法在游戏树中达到足够的深度。在本文中，我们引入了在线进化规划（OEP）来解决这一挑战，它在评估特定状态质量的适应度函数的指导下，在单个回合中搜索要执行的动作组合。我们将OEP与不同的MCTS变体进行比较，这些变体限制了探索，以应对回合制多人动作游戏《英雄学院》中的高分支因素。虽然受约束的MCTS变体在很大程度上优于普通的MCTS实现，但OEP能够比任何经过测试的树搜索方法更有效地搜索计划空间，因为它在每回合行动数量增加时具有相对优势。
We address the problem of playing turn-based multiaction adversarial games, which include many strategy games with extremely high branching factors as players take multiple actions each turn. This leads to the breakdown of standard tree search methods, including Monte Carlo tree search (MCTS), as they become unable to reach a sufficient depth in the game tree. In this paper, we introduce online evolutionary planning (OEP) to address this challenge, which searches for combinations of actions to perform during a single turn guided by a fitness function that evaluates the quality of a particular state. We compare OEP to different MCTS variations that constrain the exploration to deal with the high branching factor in the turn-based multiaction game Hero Academy. While the constrained MCTS variations outperform the vanilla MCTS implementation by a large margin, OEP is able to search the space of plans more efficiently than any of the tested tree search methods as it has a relative advantage when the number of actions per turn increases.
蒙特卡罗树搜索与宏观行动和启发式路线规划用于物理旅行推销员问题
DOI：
10.1109/cig.2012.6374161
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Powley E
通讯作者：
Powley E