Width-Based Planning for General Video-Game Playing
Width-Based Planning for General Video-Game Playing
复制标题
适用于一般视频游戏的基于宽度的规划
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hector Geffner
中科院分区：
文献类型：
--
作者：
Tomas Geffner;Hector Geffner
IW(1)是一个简单的搜索算法，它假设状态可以用一组布尔特征或原子来表征。IW(1)由标准的广度优先搜索和一个变种组成：如果一个新生成的态不能使一个新原子为真，那么它将被修剪。因此，虽然广度优先搜索的时间是原子数量的指数，但IW(1)的时间是线性的。该算法的不同版本已被证明在经典规划和最近的雅达利视频游戏中产生了最先进的结果。在本文中，我们使用了一般视频游戏AI竞赛(GVG-AI)游戏中的动作选择算法，与经典规划问题和Atari游戏不同，GVG-AI游戏是随机的。我们使用获胜次数作为性能衡量标准，在不同的时间窗口下对算法的一个变体进行了30多场比赛的评估。我们发现，在所有的时间窗口中，IW(1)都比样本MCTS和OLMCTS控制器表现得更好，并且性能差距随着窗口大小的增大而增大。例外的是类似拼图的游戏，所有的算法都做得很差。对于这类问题，我们证明了与IW(1)算法类似的IW(2)算法可以获得更好的结果，除了在广度优先搜索中无法实现新的原子对时对状态进行剪枝。
IW(1) is a simple search algorithm that assumes that states can be characterized in terms of a set of boolean features or atoms. IW(1) consists of a standard breadth-first search with one variation: a newly generated state is pruned if it does not make a new atom true. Thus, while a breadth-first search runs in time that is exponential in the number of atoms, IW(1) runs in linear time. Variations of the algorithm have been shown to yield state-of-the-art results in classical planning and more recently in the Atari video games. In this paper, we use the algorithm for selecting actions in the games of the general video-game AI competition (GVG-AI) which, unlike classical planning problems and the Atari games, are stochastic. We evaluate a variation of the algorithm over 30 games under different time windows using the number of wins as the performance measure. We find that IW(1) does better than the sample MCTS and OLMCTS controllers for all time windows with the performance gap growing with the window size. The exception are the puzzle-like games where all the algorithms do poorly. For such problems, we show that much better results can be obtained with the IW(2) algorithm, which is like IW(1), except that states are pruned in the breadth-first search when they fail to make true a new pair of atoms.