Width-based Planning for General Video-Game Playing

Iterated Width is a simple search algorithm that assumes that states can be characterized in terms of a set of boolean features or atoms. In par-ticular, 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 exponen-tial 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 com-petition (GVG-AI) which, unlike classical plan-ning problems and the Atari games, are stochas-tic. 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 win-dow size. The exception are the puzzle-like games where all the algorithms do poorly. For such prob-lems, we show that much better results can be ob-tained 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.