Rolling Stone solver

From Sokoban Wiki

(Difference between revisions)
Jump to: navigation, search
m (→Screenshot Rolling Stone)
(→Screenshot Rolling Stone: Menu structure)
Line 34: Line 34:
[[File:Rolling Stone XSokoban1.png]]
[[File:Rolling Stone XSokoban1.png]]
 +
 +
 +
= Menu structure =
 +
 +
== Main menu ==
 +
 +
{| class="soko-table"
 +
!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
 +
|-
 +
|}
 +
 +
== Show menu ==
 +
 +
{| class="soko-table"
 +
!Command          || Function
 +
|-
 +
|D  || Hist of man-distances
 +
|-
 +
|S  ||  Hist of stone-distances
 +
|-
 +
|X  || Hist of X-distances
 +
|-
 +
|C  || Print Conflicts prev search
 +
|}
 +
 +
== Options menu ==
 +
 +
{| class="soko-table"
 +
!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
 +
|}

Revision as of 10:43, 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:

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
num kind Solve Maze
A Set Abort Node Count
VIRT] Set Abort time
C a b kind Test a to b in screen
num kind Print Maze
L a b kind All 90 Lower Bounds
N num Set PosNr with num
XX-YY move from num to num
X [lrud]* move center for xdist
Z Show Menu
O Options Menu
Q Quit Program

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
Retrieved from "http://sokobano.de/wiki/index.php?title=Rolling_Stone_solver"
Personal tools