Procedural Generation of Initial States of Sokoban
This addresses the need for challenging test cases in planning systems and machine learning, though it is incremental as it builds on existing procedural generation methods.
The paper tackled the problem of generating hard and solvable initial states for Sokoban puzzles, proposing hardness metrics based on pattern database heuristics and novelty to improve search exploration, with experiments showing that their system Beta generated states harder to solve by a specialized solver than those designed by human experts.
Procedural generation of initial states of state-space search problems have applications in human and machine learning as well as in the evaluation of planning systems. In this paper we deal with the task of generating hard and solvable initial states of Sokoban puzzles. We propose hardness metrics based on pattern database heuristics and the use of novelty to improve the exploration of search methods in the task of generating initial states. We then present a system called Beta that uses our hardness metrics and novelty to generate initial states. Experiments show that Beta is able to generate initial states that are harder to solve by a specialized solver than those designed by human experts.