Solvers - joric/sokoban GitHub Wiki

YASS

YASS (Yet Another Sokoban Solver) is a GUI Sokoban with many features. Works with YASC (Yet Another Socoban Clone). It is truly great and solves 16x10 maps instantly.

Output notation uses 8 characters. The symbols "lurd" (lowercase) indicate the movement of the player to the left, up, right, down. The symbols "LURD" (in uppercase) indicate that the player pushes the box left, up, right, down.

YASS-WASM

This is YASS (Yet Another Sokoban Solver) 2.151 by Brian Damgaard, ported to WebAssembly (by me).

See YASS solver directory for details (it is used in this game as a WASM binary).

  • Added "-inline" option (YASS does not support stdin just yet)
  • TODO: either add stdin support or dll calls support in wasm loader

Usage

YASS.exe -inline <space-separated level data>

e.g.

YASS.exe -inline " ##### " " # # " " ### $### " " # $ # " "### # ## ######" "# # ##$ # ..#" "# $ $ $ ..#" "##### ### # ..#" " # @ ######" " ####### "

Output: the last string either contains moves or "Level not solved" if no solution:

rruuRRRRurDlllllddlllluuRRRRRRRRllllllllllulldRRRRRRRRRRRllluuulllulDDDuulldddrRRRRRRRdrUluRRlldlluuullluurDllddddrrrruuulLLulDDDuulldddrRRRRRRRdrUluRdllluulDuullldddrrRRRRurDldR

(lowercase means "move", uppercase means "push")

Running in a browser (you can use a worker to run asynchronously):

<!DOCTYPE html>
<html>
<head>
<script src="js/YASS_loader.js"></script>
<script>
let level = [
'    #####       ',
'    #   #       ',
'  ###  $###     ',
'  #  $    #     ',
'### # ##  ######',
'#   # ##$ #  ..#',
'# $   $   $  ..#',
'##### ### #  ..#',
'    #  @  ######',
'    #######     '
];
//rtl.showUncaughtExceptions=true;
rtl.argv = ["YASS", "-inline", ...level];
rtl.callback = result => {
  console.log(result);
}
rtl.run();
</script>

Build

There are no WASM binary releases, you need LLVM 12.0.1 and FPC 3.2.2 to build cross-compiler from source.

Prerequisites:

git clone https://gitlab.com/freepascal.org/fpc/source.git fpc
cd fpc

:: build wasm compiler
set path=d:\lib\FPC\3.2.2\bin\i386-win32;%path%
set path=d:\lib\llvm\bin;%path%
make clean all OS_TARGET=wasi CPU_TARGET=wasm32 BINUTILSPREFIX= OPT="-O-" PP=fpc

:: install
mkdir d:\lib\fpcwasm
make crossinstall OS_TARGET=wasi CPU_TARGET=wasm32 INSTALL_PREFIX=d:\lib\fpcwasm PP=fpc

:: build YASS.wasm
set path=d:\lib\fpcwasm\bin\i386-win32;%path%
ppcrosswasm32.exe YASS.pas

Then you need a bootstrap js code to load your .wasm, it's usually a Pascal program processed with pas2js.

I've used fpc_wasm example and replaced Wasm1.wasm with YASS.wasm.

You also need to implement args_get and args_sizes_get to pass arguments to a program (see WASM_loader.js).

References

Other solvers

Festival

Festival is a Sokoban solver written by Yaron Shoham. It is based on the novel FESS search algorithm (presented in CoG 2020). Festival is the first program that solves all 90 levels of the XSokoban benchmark. It's slower than YASS.

Also this page has a bunch of solvers, including Prolog Solver Generator (that's really slow):

Papers

The main breakththrough is using IDA* (Iterative Deepening A*) instead of a simple A*.

Benchmark

Using YASS solver (the best one) on Ryzen 7 5800H, timer resolution is ~16 ms

--------------------------------------------------------------------------------
                               Level  Pushes    Generated    Generated      Time
  No  W  H                      Name            Positions       Pushes        ms
--------------------------------------------------------------------------------
   1 16 10                   level 1      59           84           92        16 
   2 16 10                   level 2      77          639          780        16
   3 16 10                   level 3      95         1293         1655        16  
   4 16 10                   level 4     121          680          799        16 
   5 16 10                   level 5      16           50           51        32  
   6 16 10                   level 6     105          389          452        32  
   7 16 10                   level 7      85         1799         2436       576
   8 16 10                   level 8      84       668323      1153231      3680
   9 16 10                   level 9     190         6382         7899        16   
  10 16 10                  level 10      75          102          112        16  
  11 16 10                  level 11      55        23710        41982        64  
  12 16 10                  level 12     170         4210         5219        16
  13 16 10                  level 13      99         1020         1217        16 
  14 16 10                  level 14     162         1860         1989        64  
  15 16 10                  level 15     103        32297        70002        64  
  16 16 10                  level 16     104         6724        15417        32  
  17 16 10                  level 17     125         4347         5124        48  
  18 16 10                  level 18     133        27647        37066        64  
  19 16 10                  level 19      98          464          561        16  
  20 16 10                  level 20     165         4887         5657       128   
--------------------------------------------------------------------------------
  20    20 solved, 0 failed    Total    2121       786907      1351741     5000+
--------------------------------------------------------------------------------
⚠️ **GitHub.com Fallback** ⚠️