Finding Optimal Solutions to Sokoban Using Instance Dependent Pattern Databases

Abstract

Pattern databases have been successfully applied to several problems. Their use assumes that the goal state is known, and once the pattern database is built, commonly it can be used by all instances. However, in Sokoban, before solving the puzzle, the goal position of each stone is unknown. Moreover, each Sokoban instance has its own state space search. In this paper we apply pattern databases to Sokoban. The proposed approach uses an instance decomposition, that allows multiple possible goal states to be abstracted into a single state. Thus, an instance dependent pattern database is employed. Experiments with the standard set of instances show that the proposed approach overcomes the current best lower bounds in initial states for several instances. Furthermore, three of these new best lower bounds match exactly with the optimal solution length. Finally, we run experiments of 5 million explored states for each instance. Nine instances were solved with optimality guarantees, while only four instances were solved under the same conditions by previous methods.