Rolling Stone solver

From Sokoban Wiki

Jump to: navigation, search

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"

File:Rolling Stone XSokoban1.png


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)
Personal tools