Procedural Generation of Initial States of Sokoban

Procedural Generation of Initial States of Sokoban

Dâmaris S. Bento, André G. Pereira, Levi H. S. Lelis

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 4651-4657. https://doi.org/10.24963/ijcai.2019/646

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.
Keywords:
Multidisciplinary Topics and Applications: Computer Games
Multidisciplinary Topics and Applications: Interactive Entertainment
Planning and Scheduling: Search in Planning and Scheduling
Heuristic Search and Game Playing: Heuristic Search