Generating Sokoban Levels that are Interesting to Play using Simulation

Abstract

Procedural Content Generation for Games (PCG-G) is the act of generating content for games using a procedure. There are many valid reason why game creators could be interested in using PCG-G. An example is that artists can be aided in creating massive game worlds, since creating all the content by hand is too time consuming. By using pseudo randomness, procedures are able to generate content useful in games, however without the input of an expert artist, procedures struggle to generate content that is interesting to play.

The focus in this work lies on generating interesting game worlds. Generating interesting game worlds can be subdivided into the generation of the space and the mission of the game world. The abstract equivalent of the mission is a puzzle. A puzzle generator that can generate interesting puzzles can therefore be used to generate interesting worlds.

Previous work has shown that challenging Sokoban puzzles can be generated by simulated play. Although these generated puzzles are slightly challenging, they do not come near the interestingness of handcrafted puzzles. There seems to be an upper limit that the current approach cannot (consistently) exceed. This is mainly due to the use of simple metrics that do not seem to be able to capture the underlying concepts of interestingness.

Seven candidate improvements on a replica of the foundational work were created. The Push Alteration and the Hard-coded Symmetry Reduction seemed to be the most promising. These two candidate improvements were taken to the test in an user study experiment. The user study showed that these candidate improvements result in generally more interesting puzzles than puzzles generated by the replica of the foundational work, but that they are still much less interesting than puzzles generated by expert artists.