Rolling Stone solver
From Sokoban Wiki
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:
Contents |
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
| Command | Function |
|---|---|
| S nam\num kind | Solve Maze |
| A | Set Abort Node Count |
| T sec [REAL\VIRT] | Set Abort time |
| C a b kind | Test a to b in screen |
| P nam\num kind | Print Maze |
| L a b kind | All 90 Lower Bounds |
| N num | Set PosNr with num |
| M num-num\XX-YY | move from num to num |
| X [lrud]* | move center for xdist |
| Z | Show Menu |
| O | Options Menu |
| Q | Quit Program |
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.
The command "S test.sok" loads the puzzle "./test.sok" and tries to solve it.
Show menu
| Command | Function |
|---|---|
| D | Hist of man-distances |
| S | Hist of stone-distances |
| X | Hist of X-distances |
| C | Print Conflicts prev search |
Options menu
| Command | Function |
|---|---|
| E | Examine all settings |
| H [on/off] | HashTable on/off |
| D [on/off] | deadlock det. movegen on/off |
| Z [on/off] | deadlock2 det. movegen on/off |
| R [on/off] | areasearch on/off |
| S [on/off] | deadsearch on/off |
| N [on/off] | pensearch on/off |
| W [on/off] | scan search on/off |
| J number | node limit for pattern searches |
| K [on/off] | minimization on/off |
| Y [on/off] | limit patterns on/off |
| m [on/off] | lazy maximization on/off |
| X [on/off] | store tested on/off |
| P number | Switch Pattern DBs on/off (0-7) |
| M [on/off] | LB manpos on/off |
| C [on/off] | LB conflict on/off |
| d [on/off] | Dynamic distances on/off |
| T [on/off] | Tunnel Macro on/of |
| G [on/off] | Goal Macro on/off |
| U [on/off] | Cut Goal Macro on/off |
| A [on/off | eXtended Distance on/off |
| L k m d | Local Cut (k,m,d), -1 -1 turns off |
| B [on/off | Auto Set Local Cut Parameter |
| V [s] [h] | Overestimation scaling factor and h-scaling |
| F [on/off] | Assume dead on/off |
| O number | Set Move order index (0-off) |
General command
| Command | Function |
|---|---|
| ? | Help command. Displays availible menu options |
| < | Back (quit) |
