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.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 12th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2016 |
| Editors | Nathan Sturtevant, Brian Magerko |
| Publisher | Association for the Advancement of Artificial Intelligence |
| Pages | 58-64 |
| Number of pages | 7 |
| ISBN (Electronic) | 9781577357728 |
| State | Published - Oct 8 2016 |
| Event | 12th Annual AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2016 - Burlingame, United States Duration: Oct 8 2016 → Oct 12 2016 |
Publication series
| Name | Proceedings - AAAI Artificial Intelligence and Interactive Digital Entertainment Conference, AIIDE |
|---|---|
| ISSN (Print) | 2326-909X |
| ISSN (Electronic) | 2334-0924 |
Conference
| Conference | 12th Annual AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2016 |
|---|---|
| Country/Territory | United States |
| City | Burlingame |
| Period | 10/8/16 → 10/12/16 |
Bibliographical note
Publisher Copyright:Copyright © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.