Data Driven Sokoban Puzzle Generation with Monte Carlo Tree Search

Authors

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

DOI:

https://doi.org/10.1609/aiide.v12i1.12859

Keywords:

AI, Sokoban, Puzzles, Games, PCG

Abstract

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.

Downloads

Published

2021-06-25

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. https://doi.org/10.1609/aiide.v12i1.12859