Data Driven Sokoban Puzzle Generation with Monte Carlo Tree Search


  • Bilal Kartal University of Minnesota
  • Nick Sohre University of Minnesota
  • Stephen Guy University of Minnesota



AI, Sokoban, Puzzles, Games, PCG


In this work, we propose a Monte Carlo Tree Search (MCTS) based approach to procedurally generate Sokoban puzzles. Our method generates puzzles through simulated game play, guaranteeing solvability in all generated puzzles. We perform a user study to infer features that are efficient to compute and are highly correlated with expected puzzle difficulty. We combine several of these features into a data-driven evaluation function for MCTS puzzle creation. The resulting algorithm is efficient and can be run in an anytime manner, capable of quickly generating a variety of challenging puzzles. We perform a second user study to validate the predictive capability of our approach, showing a high correlation between increasing puzzle scores and perceived difficulty.




How to Cite

Kartal, B., Sohre, N., & Guy, S. (2021). Data Driven Sokoban Puzzle Generation with Monte Carlo Tree Search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58-64.