On Grid Graph Reachability and Puzzle Games
This work addresses puzzle game solving for AI planning, but it is incremental as it builds on existing reachability encodings.
The paper tackles the problem of solving puzzle video games like Sokoban by studying constraint programming (CP) and SAT approaches, proposing a new reachability encoding that is empirically shown to be effective for solving these problems, especially with parallel actions.
Many puzzle video games, like Sokoban, involve moving some agent in a maze. The reachable locations are usually apparent for a human player, and the difficulty of the game is mainly related to performing actions on objects, such as pushing (reachable) boxes. For this reason, the difficulty of a particular level is often measured as the number of actions on objects, other than agent walking, needed to find a solution. In this paper we study CP and SAT approaches for solving these kind of problems. We review some reachability encodings and propose a new one. We empirically show that the new encoding is well-suited for solving puzzle problems in the planning as SAT paradigm, especially when considering the execution of several actions in parallel.