From Sokoban Wiki

Revision as of 12:38, 21 March 2024 (view source) Matthias Meger (Talk | contribs) m (→Show menu) ← Older edit		Revision as of 12:38, 21 March 2024 (view source) Matthias Meger (Talk | contribs) m (→Main menu) Newer edit →
Line 41:		Line 41:
	{| class="soko-table"		{| class="soko-table"
-	!Command         || Function	+	!Command           || Function
	|-		|-
-	|S nam|num kind   || Solve Maze	+	|S nam|num kind   || Solve Maze
	|-		|-
-	|A   || Set Abort Node Count	+	|A                 || Set Abort Node Count
	|-		|-
-	|T sec [REAL|VIRT]   || Set Abort time	+	|T sec [REAL|VIRT] || Set Abort time
	|-		|-
-	|C a b kind || Test a to b in screen	+	|C a b kind       || Test a to b in screen
	|-		|-
-	|P nam|num kind   || Print Maze	+	|P nam|num kind   || Print Maze
	|-		|-
-	|L a b kind   ||  All 90 Lower Bounds	+	|L a b kind       ||  All 90 Lower Bounds
	|-		|-
-	|N num   || Set PosNr with num	+	|N num             || Set PosNr with num
	|-		|-
	|M num-num|XX-YY  || move from num to num		|M num-num|XX-YY  || move from num to num
	|-		|-
-	|X [lrud]*   || move center for xdist	+	|X [lrud]*         || move center for xdist
	|-		|-
-	|Z   || Show Menu	+	|Z                 || Show Menu
	|-		|-
-	|O   || Options Menu	+	|O                 || Options Menu
	|-		|-
-	|Q   || Quit Program	+	|Q                 || Quit Program
	|-		|-
	|}		|}

---

Revision as of 12:38, 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 1 Algorithm 2 How to compile Rolling Stone 3 Screenshot Rolling Stone 4 Menu structure 4.1 Main menu 4.2 Show menu 4.3 Options menu 4.4 General command

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