Solver Statistics

From Sokoban Wiki

Revision as of 20:05, 19 June 2020

Sokoban solvers are programs that solve sokoban levels. There are many programs available that can solve Sokoban levels (see Sokoban solvers).

There are different types of solvers:

1. Solvers trying to find any solution
2. Solvers trying to find push optimal solutions
3. Solvers trying to find push optimal solutions with best moves
4. Solvers trying to find move optimal solutions
5. Solvers trying to find move optimal solutions with best pushes

Usually, a solver is designed to just find any solution. If the solution is to be optimized an optimizer program can be used (Optimizers).

To get an impression of what levels are solvable by which solver, here are some statistics.
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

XSokoban Test Suite

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

Large Test Suite

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is meant to be a "Large Standard Test Suite" for Sokoban solver programs.

Download the entire test suite here or from www.sokobano.de.

Solver Statistics

The statistics shows the results for the leading Sokoban solvers for various level packs. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

GroupEffort Test Suite

The only reason for benchmarking the GroupEffort test suite is to show the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

Disclaimer

Sokoban
=======


Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan


License
=======


Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met: 


* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
  and/or other materials provided with the distribution.


Credits (in no particular order)
================================


CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown


dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown


Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown


Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev  (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/


SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: http://leehaywood.org/games/sokoban/


Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown


Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/


Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase 
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html


BoxSearch
Copyright (C) 2007 by Ge Yong
E-mail: notabdc@hotmail.com
Web site: unknown   


JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@online.de
Web site: http://www.sokoban-online.de


Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: http://www.ic-net.or.jp/home/takaken/e/soko/index.html 


YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
E-mail: BrianDamgaard@jubii.dk
Web site: http://sourceforge.net/projects/sokobanyasc/


Sokoban YASC 
Copyright (C) 2001-2019 by Brian Damgaard
E-mail: BrianDamgaard@jubii.dk
Web Site: https://sourceforge.net/projects/sokobanyasc/


YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site:  http://ygp.orgfree.com/sokoban.html


XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html


Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown


Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://codeanalysis.fr/sokoban/   


Trademarks
========== 


Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.


Contact
=======


E-mail: sokoban@online.de