Planning Algorithms for Zero-Sum Games with Exponential Action Spaces: A Unifying Perspective
Planning Algorithms for Zero-Sum Games with Exponential Action Spaces: A Unifying Perspective
复制标题
DOI：
10.24963/ijcai.2020/681
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Levi H. S. Lelis
中科院分区：
文献类型：
--
作者：
Levi H. S. Lelis
在本文中，我们回顾了几个规划算法开发的零和游戏与指数行动空间，即，在给定的游戏状态下，随着可以同时动作的游戏组件的数量呈指数增长的空间。例如，实时策略游戏具有指数动作空间，因为可用动作的数量随着玩家控制的单位数量呈指数增长。我们还提出了一个统一的角度来看，现有的几个算法可以被描述为一个实例化的一个变种的天真MCTS。除了描述几个现有的规划算法的指数动作空间，我们表明，其他实例化的这种变体的NaiveMCTS代表新的和有前途的算法，在未来的工作中进行研究。
In this paper we review several planning algorithms developed for zero-sum games with exponential action spaces, i.e., spaces that grow exponentially with the number of game components that can act simultaneously at a given game state. As an example, real-time strategy games have exponential action spaces because the number of actions available grows exponentially with the number of units controlled by the player. We also present a unifying perspective in which several existing algorithms can be described as an instantiation of a variant of NaiveMCTS. In addition to describing several existing planning algorithms for exponential action spaces, we show that other instantiations of this variant of NaiveMCTS represent novel and promising algorithms to be studied in future works.