PCG: Sokoban level generation

[ahbnr]

The purpose of this issue is to collect research and ideas regarding the automatic generation of rooms containing sokoban puzzles for 2-4 players.

Interesting questions:

• ensuring that generated puzzles are solvable
• determination of a measure of fun or complexity for the generated puzzles
• a method for optimizing these values
• adapting existing solutions to multiplayer

Collection of relevant papers and research: https://www.zotero.org/groups/2641270/synergyquest/collections/57U3PREH

[maruker]

Added code to simply test level generation and difficulty estimation https://github.com/tdelta/SynergyQuest/tree/sokoban-pcg-test

[maruker]

Difficulty Rating of Sokoban Puzzle (Petr Jarusek, Radek Pelanek, 2010)

• Collected a dataset of 2000 games through puzzle websites. Data included moves and time per move

Some known metrics do not work well for Sokoban

• Hill-climbing heuristic - Measure distance of each box from its goal position
• Means-end analysis
• State space size
  • No significant correlation with human solving time
• Shortest paths
  • Low correlation with human solving time
  • Correlation increases if you only count the number of counterintuitive moves (= moves that go against hill-climbing heuristic)
• 2 decomposition
  • Minimum "switches" between groups out of all possible decomposition
  • Best correlation with human solving time
• Box changes
  • Minimum "switches" between individual boxes
  • Second best correlation with human solving time

State space of Sokoban is a directed graph G = (V, E) with game states V and edges (box moves) E. Initial state = s~0~

• State s is "live" if a connection to final state s~0~ exists. Otherwise "dead".
• Random walk: choose random s~i+1~
• Optimal walk: choose s~i+1~ that is closer to the goal

Observations from data:

• Each puzzle has 4 boxes and similar size but solving times vary between one minute and one hour
• Humans spend little time in dead states
• Humans speed up once they get closer to the goal

Computational model of human Sokoban

• Weighted combination of random and optimal walk
• Next state is chosen from the following probability distribution:
  • 0 if dead state
  • current distance from goal if the distance increases
  • current distance from goal + bonus if the distance decreases

Problem Decomposition

• Humans find it easier to solve problems if they can be decomposed into several subproblems
• Formalization: Group 4 boxes into groups of 2 or 4. Measure, how many times one has to switch between the groups in the optimal solution

The Procedural Generation of Interesting Sokoban Levels (Joshua Taylor, 2015)

TODO https://digital.library.unt.edu/ark:/67531/metadc801887/m2/1/high_res_d/dissertation.pdf