Solver Statistics

From Sokoban Wiki

(Difference between revisions)
Jump to: navigation, search
(Large Test Suite)
(Large Test Suite)
Line 111: Line 111:
| [[SolverStatistics-jsoko-AymericduPeloux | '''282''' ]]
| [[SolverStatistics-jsoko-AymericduPeloux | '''282''' ]]
| [[SolverStatistics-sokolution-Aymeric    | '''282''' ]]
| [[SolverStatistics-sokolution-Aymeric    | '''282''' ]]
-
| [[SolverStatistics-festival-Aymeric      | 0 ]]
+
| [[SolverStatistics-festival-Aymeric      | 0         ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 125: Line 125:
| [[SolverStatistics-jsoko-EvgenyGrigoriev-Grigr2001 |    92    ]]
| [[SolverStatistics-jsoko-EvgenyGrigoriev-Grigr2001 |    92    ]]
| [[SolverStatistics-sokolutionv3-Grigr2001          | '''96''' ]]
| [[SolverStatistics-sokolutionv3-Grigr2001          | '''96''' ]]
 +
| [[SolverStatistics-festival-Grigr2001              |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 138: Line 139:
| [[SolverStatistics-jsoko-EvgenyGrigoriev-Grigr2002 |    36    ]]
| [[SolverStatistics-jsoko-EvgenyGrigoriev-Grigr2002 |    36    ]]
| [[SolverStatistics-sokolutionv3-Grigr2002          | '''40''' ]]
| [[SolverStatistics-sokolutionv3-Grigr2002          | '''40''' ]]
 +
| [[SolverStatistics-festival-Grigr2002              |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 151: Line 153:
| [[SolverStatistics-jsoko-EvgenyGrigoriev-GrigrSpecial |    39    ]]
| [[SolverStatistics-jsoko-EvgenyGrigoriev-GrigrSpecial |    39    ]]
| [[SolverStatistics-sokolutionv3-GrigrSpecial          | '''40''' ]]
| [[SolverStatistics-sokolutionv3-GrigrSpecial          | '''40''' ]]
 +
| [[SolverStatistics-festival-GrigrSpecial              |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 164: Line 167:
| [[SolverStatistics-David Holland-Holland  |    55    ]]
| [[SolverStatistics-David Holland-Holland  |    55    ]]
| [[SolverStatistics-sokolutionv3-Holland    | '''66''' ]]
| [[SolverStatistics-sokolutionv3-Holland    | '''66''' ]]
 +
| [[SolverStatistics-festival-Holland        |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 177: Line 181:
| [[SolverStatistics-jsoko-DavidWSkinner-Microban | '''155''' ]]
| [[SolverStatistics-jsoko-DavidWSkinner-Microban | '''155''' ]]
| [[SolverStatistics-sokolutionv3-Microban        | '''155''' ]]
| [[SolverStatistics-sokolutionv3-Microban        | '''155''' ]]
 +
| [[SolverStatistics-festival-Microban            |      0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 190: Line 195:
| [[SolverStatistics-jsoko-DavidWSkinner-MasMicroban | '''135''' ]]
| [[SolverStatistics-jsoko-DavidWSkinner-MasMicroban | '''135''' ]]
| [[SolverStatistics-sokolutionv3-Microban-II        | '''135''' ]]
| [[SolverStatistics-sokolutionv3-Microban-II        | '''135''' ]]
 +
| [[SolverStatistics-festival-Microban-II            |      0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 203: Line 209:
| [[SolverStatistics-jsoko-DavidWSkinner-Sasquatch |    31    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-Sasquatch |    31    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch        | '''37''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch        | '''37''' ]]
 +
| [[SolverStatistics-festival-Sasquatch            |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 216: Line 223:
| [[SolverStatistics-jsoko-DavidWSkinner-MasSasquatch |    20    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-MasSasquatch |    20    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-II        | '''33''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-II        | '''33''' ]]
 +
| [[SolverStatistics-festival-Sasquatch-II            |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 229: Line 237:
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchIII |    12    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchIII |    12    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-III      | '''25''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-III      | '''25''' ]]
 +
| [[SolverStatistics-festival-Sasquatch-III          |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 242: Line 251:
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchIV |    29    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchIV |    29    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-IV      | '''37''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-IV      | '''37''' ]]
 +
| [[SolverStatistics-festival-Sasquatch-IV          |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 255: Line 265:
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchV |    25    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchV |    25    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-V      | '''37''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-V      | '''37''' ]]
 +
| [[SolverStatistics-festival-Sasquatch-V          |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 268: Line 279:
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchVI |    28    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchVI |    28    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-VI      | '''37''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-VI      | '''37''' ]]
 +
| [[SolverStatistics-festival-Sasquatch-VI          |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 281: Line 293:
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchVII |    26    ]]
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchVII |    26    ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-VII      | '''40''' ]]
| [[SolverStatistics-sokolutionv3-Sasquatch-VII      | '''40''' ]]
 +
| [[SolverStatistics-festival-Sasquatch-VII          |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 294: Line 307:
| [[SolverStatistics-jsoko-SokEvo      | '''107''' ]]
| [[SolverStatistics-jsoko-SokEvo      | '''107''' ]]
| [[SolverStatistics-sokolution-SokEvo | '''107''' ]]
| [[SolverStatistics-sokolution-SokEvo | '''107''' ]]
 +
| [[SolverStatistics-festival-SokEvo  |      0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 307: Line 321:
| [[SolverStatistics-jsoko-LeeJHaywood-SokHard |    137    ]]
| [[SolverStatistics-jsoko-LeeJHaywood-SokHard |    137    ]]
| [[SolverStatistics-sokolutionv3-SokHard      | '''163''' ]]
| [[SolverStatistics-sokolutionv3-SokHard      | '''163''' ]]
 +
| [[SolverStatistics-festival-SokHard          |      0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 320: Line 335:
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1179  ]]
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1179  ]]
| [[SolverStatistics-sokolutionv3-SvenEgevad  | '''1443''']]
| [[SolverStatistics-sokolutionv3-SvenEgevad  | '''1443''']]
 +
| [[SolverStatistics-festival-SvenEgevad      |      0  ]]
<!-- ---------------------------------------------------------------------------------------------- -->
<!-- ---------------------------------------------------------------------------------------------- -->
Line 333: Line 349:
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban            |    67    ]]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban            |    67    ]]
| [[SolverStatistics-sokolutionv3-ThinkingRabbit-XSokoban    |    81    ]]
| [[SolverStatistics-sokolutionv3-ThinkingRabbit-XSokoban    |    81    ]]
 +
| [[SolverStatistics-festival-ThinkingRabbit-XSokoban        |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 346: Line 363:
| [[SolverStatistics-jsoko-YoshioMuraseAutogenerated          | '''52''' ]]
| [[SolverStatistics-jsoko-YoshioMuraseAutogenerated          | '''52''' ]]
| [[SolverStatistics-sokolutionv3-YoshioMuraseAutogenerated    | '''52''' ]]
| [[SolverStatistics-sokolutionv3-YoshioMuraseAutogenerated    | '''52''' ]]
 +
| [[SolverStatistics-festival-YoshioMuraseAutogenerated        |    0    ]]
<!-- -------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------- -->
Line 359: Line 377:
| [[SolverStatistics-jsoko-YoshioMurase-Handmade          |    52    ]]
| [[SolverStatistics-jsoko-YoshioMurase-Handmade          |    52    ]]
| [[SolverStatistics-sokolutionv3-YoshioMuraseHandmade    | '''54''' ]]
| [[SolverStatistics-sokolutionv3-YoshioMuraseHandmade    | '''54''' ]]
 +
| [[SolverStatistics-festival-YoshioMuraseHandmade        |    0    ]]
<!-- -------------------------------------------------------------------------------------------------------- -->
<!-- -------------------------------------------------------------------------------------------------------- -->
Line 372: Line 391:
|    2559      <!-- JSoko        -->
|    2559      <!-- JSoko        -->
| '''2960'''  <!-- Sokolution  -->
| '''2960'''  <!-- Sokolution  -->
 +
|      0      <!-- Festival    -->
|}
|}

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.


Contents

XSokoban Test Suite

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

Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels
Collection Author Levels Junghanns BoxSearch Takaken YASS JSoko Sokolution
XSokoban Thinking Rabbit, ... 90 54 42 86 84 67 81
Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
Collection Author Levels Junghanns Pereira et al. JSoko Sokolution
XSokoban Thinking Rabbit, ... 90 6 28 31 57

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.

Sokoban Solver Statistics - Large Test Suite - Solved Levels
Collection Author Levels BoxSearch Takaken YASS JSoko Sokolution Festival
Aymeric Aymeric du Peloux 282 282 282 282 282 282 0
Grigr2001 Evgeny Grigoriev 100 93 94 93 92 96 0
Grigr2002 Evgeny Grigoriev 40 37 37 38 36 40 0
GrigrSpecial Evgeny Grigoriev 40 39 40 40 39 40 0
Holland David Holland 81 56 65 59 55 66 0
Microban David W. Skinner 155 155 155 155 155 155 0
Microban II David W. Skinner 135 134 134 135 135 135 0
Sasquatch David W. Skinner 50 22 36 26 31 37 0
Sasquatch II David W. Skinner 50 16 33 20 20 33 0
Sasquatch III David W. Skinner 50 14 22 13 12 25 0
Sasquatch IV David W. Skinner 50 27 37 30 29 37 0
Sasquatch V David W. Skinner 50 30 36 29 25 37 0
Sasquatch VI David W. Skinner 50 30 32 25 28 37 0
Sasquatch VII David W. Skinner 50 30 31 26 26 40 0
SokEvo Lee J Haywood 107 107 107 107 107 107 0
SokHard Lee J Haywood 163 163 163 163 137 163 0
Sven Sven Egevad 1623 1170 1384 1251 1179 1443 0
XSokoban Thinking Rabbit, ... 90 42 86 84 67 81 0
Y.M. Auto Yoshio Murase 52 52 52 52 52 52 0
Y.M. Handmade Yoshio Murase 54 54 54 52 52 54 0
Total 3272 2553 2880 2680 2559 2960 0

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.

Sokoban Solver Statistics - Solved Levels
Collection Author Levels BoxSearch Takaken YASS JSoko Sokolution
Aymeric Aymeric du Peloux 282 282 282 282 282 282
Bruno Druille Bruno Druille 29 3 17 4 4 13
Disciple Crazy Monk 50 6 27 12 10 18
Grigr2001 Evgeny Grigoriev 100 93 94 93 92 96
Grigr2002 Evgeny Grigoriev 40 37 37 38 36 40
GrigrSpecial Evgeny Grigoriev 40 39 40 40 39 40
Holland David Holland 81 56 65 59 55 66
It's All Greek DrFogh 35 6 23 14 10 22
Kevin 1 Kevin B. Reilly 100 53 95 86 74 86
Kobus Theron Kobus Theron 107 74 106 91 71 105
Marcus Palstra Marcus Palstra 30 4 10 7 4 10
Master Head Master Head 45 19 44 37 36 39
Microban David W. Skinner 155 155 155 155 155 155
Microban II David W. Skinner 135 134 134 135 135 135
Numbers DrFogh 12 6 10 10 7 9
Sasquatch David W. Skinner 50 22 36 26 31 37
Sasquatch II David W. Skinner 50 16 33 20 20 33
Sasquatch III David W. Skinner 50 14 22 13 12 25
Sasquatch IV David W. Skinner 50 27 37 30 29 37
Sasquatch V David W. Skinner 50 30 36 29 25 37
Sasquatch VI David W. Skinner 50 30 32 25 28 37
Sasquatch VII David W. Skinner 50 30 31 26 26 40
Sharpen Sven Egevad 153 34 76 43 48 92
SokEvo Lee J Haywood 107 107 107 107 107 107
SokHard Lee J Haywood 163 163 163 163 137 163
Sokoban Perfect Thinking Rabbit 306 146 261 188 188 242
Sokoban Revenge Thinking Rabbit 306 148 244 194 170 229
Sokobet DrFogh 29 18 24 19 19 24
Sven Sven Egevad 1911 1416 1652 1520 1426 1726
XSokoban Thinking Rabbit, ... 90 42 86 84 67 81
Y.M. Auto Yoshio Murase 52 52 52 52 52 52
Y.M. Handmade Yoshio Murase 54 54 54 52 52 54
Total 4762 3316 4085 3654 3447 4132

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.

Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels
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) ================================
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
Personal tools