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.
Kartal, Bilal; Sohre, Nick; Guy, Stephen.
Generating Sokoban Puzzle Game Levels with Monte Carlo Tree Search.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.