From Sokoban Wiki

Revision as of 15:02, 21 March 2024

The Rolling Stone Sokoban solver is a significant milestone in the field of automated Sokoban puzzle solving. Developed at the University of Alberta by Andreas Junghanns and Jonathan Schaeffer, it laid the groundwork for many modern solvers.

Here's a breakdown of Rolling Stone's key aspects:

Algorithm

Rolling Stone utilizes the Iterative Deepening A* (IDA*) algorithm as its core search strategy.

IDA* is an iterative deepening search algorithm that combines the efficiency of depth-first search with the optimality guarantees of A* search.

It starts by searching for a solution with a limited depth and gradually increases the depth limit until a solution is found or it's proven that no solution exists within that depth.

To improve search efficiency, Rolling Stone incorporates several enhancements described in various papers.

Rolling Stone's approach paved the way for further advancements in Sokoban solver design. Many modern solvers build upon its core principles.

It demonstrated the effectiveness of combining general search algorithms with domain-specific enhancements for efficiently solving Sokoban puzzles.

Further information can be found in the papers or on the website of Rolling Stone.

How to compile Rolling Stone

Carlos Montiers has published a source code that has been adapted so that it can also be compiled with modern operating systems and compilers. In this way, Rolling Stone can still be used today.

This is the link to his repository: Carlos Montiers Rolling Stone

Screenshot Rolling Stone

Rolling Stone can only be used from the console.

This is an example output of the solver when solving puzzle "XSokoban 1"

Menu structure

Main menu

The command "S 1" loads the puzzle "./screens/screen.1" and tries to solve it.

The command "S 1 test" loads the puzzle "./screens/test.1" and tries to solve it.

Show menu

Options menu

General command