Solver Statistics

From Sokoban Wiki

Revision as of 05:47, 9 April 2019 by Briandamgaard (Talk | contribs)
Jump to: navigation, search

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

There are different solver types:

  1. Solvers which just try to find any solution
  2. Solvers which try to find push optimal solutions
  3. Solvers which try to find push optimal solutions with best moves
  4. Solvers which try to find move optimal solutions
  5. Solvers which try 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.


Contents

Statistics for Various Level Sets

Solver Statistics - Solved Levels
Collection Author Levels BoxSearch Takaken YASS JSoko Sokolution
Aymeric Aymeric du Peloux 282 282 282 282 282 282
BoxWorld Various Authors 100 87 98 94 82 98
Grigr2001 Evgeny Grigoriev 100 93 94 93 91 95
Grigr2002 Evgeny Grigoriev 40 37 37 38 34 40
GrigrSpecial Evgeny Grigoriev 40 39 40 40 39 40
Holland David Holland 81 56 65 59 55 65
Kenyam Set A Kenya Maruyama 52 48 50 51 45 52
Microban David W. Skinner 155 155 155 155 155 155
Microban II David W. Skinner 135 134 134 135 135 132
Sasquatch David W. Skinner 50 22 36 26 28 36
Sasquatch II David W. Skinner 50 16 33 20 18 32
Sasquatch III David W. Skinner 50 14 22 13 12 25
Sasquatch IV David W. Skinner 50 27 37 30 25 35
Sasquatch V David W. Skinner 50 30 36 29 25 37
Sasquatch VI David W. Skinner 50 30 32 25 26 38
Sasquatch VII David W. Skinner 50 30 31 26 25 40
SokEvo Lee J Haywood 107 107 107 107 107 107
SokHard Lee J Haywood 163 163 163 163 158 163
Sven Sven Egevad 1623 1170 1384 1251 1147 1432
XSokoban Thinking Rabbit, ... 90 42 86 84 71 80
Y.M. Auto Yoshio Murase 52 52 52 52 52 52
Y.M. Handmade Yoshio Murase 54 54 54 52 52 53
Sokoban Perfect Thinking Rabbit 306 66* 261 188 188 233
Sokoban Revenge Thinking Rabbit 306 76* 244 194 171 214
Total 4036 2830 3533 3207 3023 3536
* = Results for BoxSearch have been done with "moves/pushes" solving method, 
not with "any solution" method, which is much better. The results will be updated
as soon as the better results are available.

Statistics for Push-Optimal Solvers

Solver Statistics - Push-optimal Solutions
Collection Author Levels Junghanns Pereira et al. JSoko Sokolution
XSokoban Thinking Rabbit, ... 90 50 28 31 38
Total 90 50 28 31 38

GroupEffort Test Suite

The 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.

Solver Statistics - GroupEffort Test Suite
Collection Levels GroupEffort Sokolution Takaken JSoko YASS
Small Set 200 196 (a)(c) 200 (a) 192 (b) 180 (b) 191 (b)
Large Set 2851 1566 (a)(c) 2471 (a) 2462 (b) 2165 (b) 2260 (b)
Total 3051 1762 2671 2654 2345 2471

(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) =================================
Many thanks to minglw for doing the solver tests for the sets: Sokoban Perfect and Sokoban Revenge.
Sokolution Copyright (C) 2016 by Florent DIEDLER E-mail: fdiedler2000@gmail.com Web site: http://codeanalysis.fr/sokoban/
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/
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/
Kenyam Set A Copyright (C) 2000-2006 by Kenya Maruyama E-mail: rmckenyam@hotmail.com Web Site: http://www.geocities.jp/rmcsokoban/soko/skrmc_a.htm
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
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
Box World Copyright (C) 1998 by Jeng-Long Jiang E-mail: unknown Web Site: unknown
Sokofan Copyright (C) 2005-2007 by Eric Leung E-mail: eleung2@hotpop.com Web Site: unknown
Sokoban YASC Copyright (C) 2007 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
Trademarks ==========
Company names, brand names and product names are trademarks or registered trademarks of their respective holders.
Contact =======
E-mail: sokoban@online.de
Personal tools