Generating Sokoban Puzzle Game Levels with Monte Carlo Tree Search

Abstract

In this work, we propose a Monte Carlo Tree Search based approach to procedurally generate Sokoban puzzles with varying sizes. We propose two heuristic metrics surrounding box path congestion and level terrain to guide the search towards interesting puzzles. Our method generates puzzles through the simulated game play itself, guaranteeing solvability in all generated puzzles. Our algorithm is efficient, capable of generating challenging puzzles very quickly (generally in under a minute) for varying board sizes. The ability to generate puzzles quickly allows our method to be applied in a variety of applications such as procedurally generated mini-games and other puzzle-driven game elements.