Solver Statistics

From Sokoban Wiki

(Difference between revisions)
Jump to: navigation, search
m (→Solver Statistics)
m (Reverted edits by Matthias Meger (Talk) to last revision by Briandamgaard)
Line 312: Line 312:
| [[SolverStatistics-takaken-SvenEgevad        |    1384  ]]
| [[SolverStatistics-takaken-SvenEgevad        |    1384  ]]
| [[SolverStatistics-yass-SvenEgevad          |    1251  ]]
| [[SolverStatistics-yass-SvenEgevad          |    1251  ]]
-
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1180   ]]
+
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1147   ]]
| [[SolverStatistics-sokolutionv3.1-SvenEgevad | '''1432''']]
| [[SolverStatistics-sokolutionv3.1-SvenEgevad | '''1432''']]
Line 364: Line 364:
|    2880      <!-- Takaken      -->
|    2880      <!-- Takaken      -->
|    2680      <!-- YASS        -->
|    2680      <!-- YASS        -->
-
|    2571      <!-- JSoko        -->
+
|    2538     <!-- JSoko        -->
-
| '''2939'''  <!-- Sokolution  -->
+
-
 
+
-
|}
+
-
 
+
-
== 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.
+
-
 
+
-
{| class="soko-table"
+
-
|-
+
-
! colspan="7" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- The header                                                                                  -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- bgcolor="#f1efe5" align="center"                <!-- standard format of all rows -->
+
-
| width = "115" align="left" | Collection
+
-
| width =  "80" |                                                        Levels
+
-
| width =  "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
+
-
| width =  "80" | [http://codeanalysis.fr/sokoban/                        Sokolution]
+
-
| width =  "80" | [http://www.ic-net.or.jp/home/takaken/e/soko/index.html Takaken]
+
-
| width =  "80" | [https://sourceforge.net/projects/jsokoapplet/          JSoko]
+
-
| width =  "80" | [https://sourceforge.net/projects/sokobanyasc/          YASS]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Small Set                                                                                    -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
+
-
| 200
+
-
| 196 (a)(c)
+
-
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
+
-
| [[SolverStatistics-Takaken-GroupEffort-Small-Set    |    192 (b)    ]]
+
-
| [[SolverStatistics-JSoko-GroupEffort-Small-Set      |    180 (b)    ]]
+
-
| [[SolverStatistics-YASS-GroupEffort-Small-Set      |    191 (b)    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Large Set                                                                                    -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
+
-
| 2851
+
-
| 1566 (a)(c)
+
-
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | '''2471''' (a) ]]
+
-
| [[SolverStatistics-Takaken-GroupEffort-Large-Set    |    2462 (b)    ]]
+
-
| [[SolverStatistics-JSoko-GroupEffort-Large-Set      |    2165 (b)    ]]
+
-
| [[SolverStatistics-YASS-GroupEffort-Large-Set      |    2260 (b)    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Total                                                                                        -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right" bgcolor="#f1efe5" align="right"
+
-
| align="left"| Total
+
-
|    3051      <!-- Total levels -->
+
-
|    1762      <!-- Group Effort -->
+
-
| '''2671'''  <!-- Sokolution  -->
+
-
|    2654      <!-- Takaken      -->
+
-
|    2345      <!-- JSoko        -->
+
-
|    2471      <!-- YASS        -->
+
-
 
+
-
|}
+
-
 
+
-
(a): Time limit: 5 minutes &nbsp;&nbsp;&nbsp;  (b): Time limit: 10 minutes &nbsp;&nbsp;&nbsp;  (c): Best GroupEffort solver configuration
+
-
 
+
-
Sokoban solvers are programs that solve sokoban levels. There are many programs available that can solve Sokoban levels (see [[Links#Sokoban Solvers |Sokoban solvers]]).
+
-
 
+
-
There are different solver types:
+
-
# Solvers which just try to find any solution
+
-
# Solvers which try to find push optimal solutions
+
-
# Solvers which try to find push optimal solutions with best moves
+
-
# Solvers which try to find move optimal solutions
+
-
# 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 ([[Links#Sokoban Solvers |Optimizers]]).
+
-
 
+
-
To get an impression of what levels are solvable by which solver here are some statistics.<br />
+
-
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.
+
-
 
+
-
{| class="soko-table"
+
-
|-
+
-
! colspan="9" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels
+
-
 
+
-
<!-- Header -->
+
-
|- bgcolor="#f1efe5" align="center"
+
-
| width="115" align="left" |      Collection
+
-
| width="160"  |                Author
+
-
| width=" 70"  |                Levels
+
-
| width= "80"  | <span class="plainlinks">[https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Junghanns]</span>
+
-
| width=" 80"  |                BoxSearch
+
-
| width= "80"  | <span class="plainlinks">[http://www.ic-net.or.jp/home/takaken/e/soko/index.html                Takaken]</span>
+
-
| width=" 80"  | <span class="plainlinks">[https://sourceforge.net/projects/sokobanyasc/ YASS]</span>
+
-
| width=" 80"  | [[JSoko Solver    | JSoko]]
+
-
| width=" 80"  | <span class="plainlinks">[http://codeanalysis.fr/sokoban/ Sokolution ]</span>
+
-
 
+
-
<!-- ---------------------------------------------------------------------------------------------- -->
+
-
<!-- XSokoban. "Collection, author, levels, Junghanns, BoxSearch, Takaken, YASS, JSoko, Sokolution" -->
+
-
<!-- ---------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5" | [[Solver Statistics - XSokoban - Thinking Rabbit & Various Authors| XSokoban ]]
+
-
| align="left"                                                | Thinking Rabbit, ...
+
-
|                                                                  90
+
-
| <span class="plainlinks">[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 54]</span>
+
-
|                                                                  42
+
-
| [[SolverStatistics-takaken-ThinkingRabbit-XSokoban          | '''86''' ]]
+
-
| [[SolverStatistics-yass-ThinkingRabbit-XSokoban            |    84    ]]
+
-
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban            |    71    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-ThinkingRabbit-XSokoban  |    80    ]]
+
-
 
+
-
|}
+
-
 
+
-
{| class="soko-table"
+
-
|-
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
+
-
|- bgcolor="#f1efe5" align="center"
+
-
| width="115" align="left" | Collection
+
-
| width="160"              | Author
+
-
| width=" 70"              | Levels
+
-
| width=" 80"              | <span class="plainlinks">[https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Junghanns]</span>
+
-
| width=" 80"              | <span class="plainlinks">[http://www.ijcai.org/Abstract/16/100 Pereira et al.]</span>
+
-
| width=" 80"              | <span class="plainlinks">[http://sourceforge.net/projects/jsokoapplet/ JSoko]</span>
+
-
| width=" 80"              | <span class="plainlinks">[http://codeanalysis.fr/sokoban/ Sokolution ]</span>
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5" | XSokoban
+
-
| align="left"                  | Thinking Rabbit, ...
+
-
|                90
+
-
|                <span class="plainlinks">[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]</span>
+
-
|                [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
+
-
|                <span class="plainlinks">[https://www.sokoban-online.de/jsoko/solver-statistics/ 31 ]</span>
+
-
|                [[SolverStatistics-Sokolutionv3.01-ThinkingRabbit-XSokoban-Push-Optimal | '''38''' ]]
+
-
 
+
-
|}
+
-
 
+
-
== 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.
+
-
 
+
-
{| class="soko-table"
+
-
|-
+
-
! colspan="8" | Sokoban Solver Statistics - Large Test Suite - Solved Levels
+
-
 
+
-
<!-- Header -->
+
-
|- bgcolor="#f1efe5" align="center"
+
-
| width="115" align="left" |      Collection
+
-
| width="160"  |                Author
+
-
| width=" 70"  |                Levels
+
-
| width=" 80"  |                BoxSearch
+
-
| width= "80"  | <span class="plainlinks">[http://www.ic-net.or.jp/home/takaken/e/soko/index.html                Takaken]</span>
+
-
| width=" 80"  | <span class="plainlinks">[https://sourceforge.net/projects/sokobanyasc/ YASS]</span>
+
-
| width=" 80"  | [[JSoko Solver    | JSoko]]
+
-
| width=" 80"  | <span class="plainlinks">[http://codeanalysis.fr/sokoban/ Sokolution ]</span>
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Aymeric du Peloux. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution" -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"          | [[Solver Statistics - Aymeric | Aymeric]]
+
-
| align="left"                            | Aymeric du Peloux
+
-
|                                              282
+
-
|                                            '''282'''
+
-
| [[SolverStatistics-takaken-Aymeric      | '''282''' ]]
+
-
| [[SolverStatistics-yass-Aymeric          | '''282''' ]]
+
-
| [[SolverStatistics-jsoko-AymericduPeloux | '''282''' ]]
+
-
| [[SolverStatistics-sokolution-Aymeric    | '''282''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Grigr2001. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"        -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                    | [[Solver Statistics - Grigr2001 - Evgeny Grigoriev| Grigr2001]]
+
-
| align="left"                                      | Evgeny Grigoriev
+
-
|                                                        100
+
-
|                                                        93
+
-
| [[SolverStatistics-takaken-Grigr2001              |    94    ]]
+
-
| [[SolverStatistics-yass-Grigr2001                  |    93    ]]
+
-
| [[SolverStatistics-jsoko-EvgenyGrigoriev-Grigr2001 |    92    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Grigr2001      | '''95''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Grigr2002. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"        -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                    | [[Solver Statistics - Grigr2002 - Evgeny Grigoriev| Grigr2002]]
+
-
| align="left"                                      | Evgeny Grigoriev
+
-
|                                                        40
+
-
|                                                        37
+
-
| [[SolverStatistics-takaken-Grigr2002              |    37    ]]
+
-
| [[SolverStatistics-yass-Grigr2002                  |    38    ]]
+
-
| [[SolverStatistics-jsoko-EvgenyGrigoriev-Grigr2002 |    34    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Grigr2002      | '''40''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- GrigrSpecial. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"      -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                        | [[Solver Statistics - GrigrSpecial - Evgeny Grigoriev| GrigrSpecial]]
+
-
| align="left"                                          | Evgeny Grigoriev
+
-
|                                                            40
+
-
|                                                            39
+
-
| [[SolverStatistics-takaken-GrigrSpecial              | '''40''' ]]
+
-
| [[SolverStatistics-yass-GrigrSpecial                  | '''40''' ]]
+
-
| [[SolverStatistics-jsoko-EvgenyGrigoriev-GrigrSpecial |    39    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-GrigrSpecial      | '''40''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Holland. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"          -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"            | [[Solver Statistics - David Holland| Holland]]
+
-
| align="left"                              | David Holland
+
-
|                                                81
+
-
|                                                56
+
-
| [[SolverStatistics-takaken-Holland        | '''65''' ]]
+
-
| [[SolverStatistics-yass-Holland            |    59    ]]
+
-
| [[SolverStatistics-David Holland-Holland  |    55    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Holland | '''65''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Microban. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"          -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                  | [[Solver Statistics - Microban - David W. Skinner| Microban]]
+
-
| align="left"                                    | David W. Skinner
+
-
|                                                      155
+
-
|                                                  '''155'''
+
-
| [[SolverStatistics-takaken-Microban            | '''155''' ]]
+
-
| [[SolverStatistics-yass-Microban                | '''155''' ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-Microban | '''155''' ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Microban    | '''155''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Microban II. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"      -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                    | [[Solver Statistics - Microban II - David W. Skinner| Microban II]]
+
-
| align="left"                                      | David W. Skinner
+
-
|                                                        135
+
-
|                                                        134
+
-
| [[SolverStatistics-takaken-Microban-II            |    134    ]]
+
-
| [[SolverStatistics-yass-Microban-II                | '''135''' ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-MasMicroban | '''135''' ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Microban-II    |    132    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"        -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                  | [[Solver Statistics - Sasquatch - David W. Skinner| Sasquatch]]
+
-
| align="left"                                    | David W. Skinner
+
-
|                                                      50
+
-
|                                                      22
+
-
| [[SolverStatistics-takaken-Sasquatch            | '''36''' ]]
+
-
| [[SolverStatistics-yass-Sasquatch                |    26    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-Sasquatch |    28    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch    | '''36''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch II. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"      -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                      | [[Solver Statistics - Sasquatch II - David W. Skinner| Sasquatch II]]
+
-
| align="left"                                        | David W. Skinner
+
-
|                                                          50
+
-
|                                                          16
+
-
| [[SolverStatistics-takaken-Sasquatch-II            | '''33''' ]]
+
-
| [[SolverStatistics-yass-Sasquatch-II                |    20    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-MasSasquatch |    18    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch-II    |    32    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch III. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"    -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                      | [[Solver Statistics - Sasquatch III - David W. Skinner| Sasquatch III]]
+
-
| align="left"                                        | David W. Skinner
+
-
|                                                          50
+
-
|                                                          14
+
-
| [[SolverStatistics-takaken-Sasquatch-III            |    22    ]]
+
-
| [[SolverStatistics-yass-Sasquatch-III              |    13    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchIII |    12    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch-III    | '''25''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch IV. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"      -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                    | [[Solver Statistics - Sasquatch IV - David W. Skinner| Sasquatch IV]]
+
-
| align="left"                                      | David W. Skinner
+
-
|                                                        50
+
-
|                                                        27
+
-
| [[SolverStatistics-takaken-Sasquatch-IV            | '''37''' ]]
+
-
| [[SolverStatistics-yass-Sasquatch-IV              |    30    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchIV |    25    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch-IV    |    35    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch V. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"      -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                    | [[Solver Statistics - Sasquatch V - David W. Skinner| Sasquatch V]]
+
-
| align="left"                                      | David W. Skinner
+
-
|                                                        50
+
-
|                                                        30
+
-
| [[SolverStatistics-takaken-Sasquatch-V            |    36    ]]
+
-
| [[SolverStatistics-yass-Sasquatch-V              |    29    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchV |    25    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch-V    | '''37''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch VI. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"      -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                    | [[Solver Statistics - Sasquatch VI - David W. Skinner| Sasquatch VI]]
+
-
| align="left"                                      | David W. Skinner
+
-
|                                                        50
+
-
|                                                        30
+
-
| [[SolverStatistics-takaken-Sasquatch-VI            |    32    ]]
+
-
| [[SolverStatistics-yass-Sasquatch-VI              |    25    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchVI |    26    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch-VI    | '''38''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sasquatch VII. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"    -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                      | [[Solver Statistics - Sasquatch VII - David W. Skinner| Sasquatch VII]]
+
-
| align="left"                                        | David W. Skinner
+
-
|                                                          50
+
-
|                                                          30
+
-
| [[SolverStatistics-takaken-Sasquatch-VII            |    31    ]]
+
-
| [[SolverStatistics-yass-Sasquatch-VII              |    26    ]]
+
-
| [[SolverStatistics-jsoko-DavidWSkinner-SasquatchVII |    25    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-Sasquatch-VII    | '''40''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- SokEvo. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"            -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"      | [[Solver Statistics - SokEvo - Lee J Haywood | SokEvo]]
+
-
| align="left"                        | Lee J Haywood
+
-
|                                          107
+
-
|                                        '''107'''
+
-
| [[SolverStatistics-takaken-SokEvo    | '''107''' ]]
+
-
| [[SolverStatistics-yass-SokEvo      | '''107''' ]]
+
-
|                                        '''107'''
+
-
| [[SolverStatistics-sokolution-SokEvo | '''107''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- SokHard. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"          -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"              | [[Solver Statistics - Lee J Haywood | SokHard ]]
+
-
| align="left"                                | Lee J Haywood
+
-
|                                                  163
+
-
|                                                '''163'''
+
-
| [[SolverStatistics-takaken-SokHard          | '''163''' ]]
+
-
| [[SolverStatistics-yass-SokHard              | '''163''' ]]
+
-
| [[SolverStatistics-jsoko-LeeJHaywood-SokHard |    158    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-SokHard  | '''163''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Sven. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"              -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"              | [[Solver Statistics - Sven Egevad | Sven ]]
+
-
| align="left"                                | Sven Egevad
+
-
|                                                  1623
+
-
|                                                  1170
+
-
| [[SolverStatistics-takaken-SvenEgevad        |    1384  ]]
+
-
| [[SolverStatistics-yass-SvenEgevad          |    1251  ]]
+
-
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1180  ]]
+
-
| [[SolverStatistics-sokolutionv3.1-SvenEgevad | '''1432''']]
+
-
 
+
-
<!-- ---------------------------------------------------------------------------------------------- -->
+
-
<!-- XSokoban. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"            -->
+
-
<!-- ---------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5" | [[Solver Statistics - XSokoban - Thinking Rabbit & Various Authors| XSokoban ]]
+
-
| align="left"                                                | Thinking Rabbit, ...
+
-
|                                                                  90
+
-
|                                                                  42
+
-
| [[SolverStatistics-takaken-ThinkingRabbit-XSokoban          | '''86''' ]]
+
-
| [[SolverStatistics-yass-ThinkingRabbit-XSokoban            |    84    ]]
+
-
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban            |    71    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-ThinkingRabbit-XSokoban  |    80    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Y.M. Auto. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"        -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                              | [[Solver Statistics - Y.M. Auto - Yoshio Murase| Y.M. Auto ]]
+
-
| align="left"                                                | Yoshio Murase
+
-
|                                                                  52
+
-
|                                                                '''52'''
+
-
| [[SolverStatistics-takaken-YoshioMuraseAutogenerated        | '''52''' ]]
+
-
| [[SolverStatistics-yass-YoshioMuraseAutogenerated            | '''52''' ]]
+
-
|                                                                '''52'''
+
-
| [[SolverStatistics-sokolutionv3.01-YoshioMuraseAutogenerated | '''52''' ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
<!-- Y.M. Handmade. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution"    -->
+
-
<!-- -------------------------------------------------------------------------------------------- -->
+
-
|- align="right"
+
-
| align="left" bgcolor="#f1efe5"                          | [[Solver Statistics - Y.M. Handmade - Yoshio Murase| Y.M. Handmade ]]
+
-
| align="left"                                            | Yoshio Murase
+
-
|                                                              54
+
-
|                                                          '''54'''
+
-
| [[SolverStatistics-takaken-YoshioMuraseHandmade        | '''54''' ]]
+
-
| [[SolverStatistics-yass-YoshioMuraseHandmade            |    52    ]]
+
-
| [[SolverStatistics-jsoko-YoshioMurase-Handmade          |    52    ]]
+
-
| [[SolverStatistics-sokolutionv3.01-YoshioMuraseHandmade |    53    ]]
+
-
 
+
-
<!-- -------------------------------------------------------------------------------------------------------- -->
+
-
<!-- Total solved levels by solver. "Collection, author, levels, BoxSearch, Takaken, YASS, JSoko, Sokolution" -->
+
-
<!-- -------------------------------------------------------------------------------------------------------- -->
+
-
|- bgcolor="#f1efe5" align="right"
+
-
| align="left" | Total
+
-
|
+
-
|    3272      <!-- Total levels -->
+
-
|    2553      <!-- BoxSearch    -->
+
-
|    2880      <!-- Takaken      -->
+
-
|    2680      <!-- YASS        -->
+
-
|    2571     <!-- JSoko        -->
+
| '''2939'''  <!-- Sokolution  -->
| '''2939'''  <!-- Sokolution  -->
Line 1,139: Line 707:
| [[SolverStatistics-takaken-SvenEgevad        |    1384  ]]
| [[SolverStatistics-takaken-SvenEgevad        |    1384  ]]
| [[SolverStatistics-yass-SvenEgevad          |    1251  ]]
| [[SolverStatistics-yass-SvenEgevad          |    1251  ]]
-
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1180   ]]
+
| [[SolverStatistics-jsoko-SvenEgevad-Sven    |    1147   ]]
| [[SolverStatistics-sokolutionv3.1-SvenEgevad | '''1432''']]
| [[SolverStatistics-sokolutionv3.1-SvenEgevad | '''1432''']]
Line 1,178: Line 746:
|    3375      <!-- Takaken      -->
|    3375      <!-- Takaken      -->
|    3021      <!-- YASS        -->
|    3021      <!-- YASS        -->
-
|    2905     <!-- JSoko        -->
+
|    2872     <!-- JSoko        -->
| '''3390'''  <!-- Sokolution  -->
| '''3390'''  <!-- Sokolution  -->
|}
|}
-
 
-
== Disclaimer ==
 
-
 
-
Sokoban
 
-
=======
 
-
<br>
 
-
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
 
-
<br>
 
-
License
 
-
=======
 
-
<br>
 
-
Redistribution and use of the Sokoban Solver statistics are permitted
 
-
provided that the following conditions are met:
 
-
<br>
 
-
* 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.
 
-
<br>
 
-
Credits (in no particular order)
 
-
================================
 
-
<br>
 
-
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
 
-
<br>
 
-
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
 
-
Copyright (C) by David Holland
 
-
E-mail: unknown
 
-
Web site: unknown
 
-
<br>
 
-
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
 
-
<br>
 
-
Grigr2001, Grigr2002 and GrigrSpecial level sets
 
-
Copyright (C) by Evgeny Grigoriev  (aka GRIGoRusha)
 
-
E-mail: grigr@yandex.ru
 
-
Web site: http://grigr.narod.ru/
 
-
<br>
 
-
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
 
-
<br>
 
-
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/
 
-
<br>
 
-
Sven level set
 
-
Copyright (C) 2007 by Sven Egevad
 
-
E-mail: sven.egevad@telia.com
 
-
Web Site: unknown
 
-
<br>
 
-
Sokoban Perfect and Sokoban Revenge level sets
 
-
Copyright (C) 1989, 1991 by Thinking Rabbit
 
-
Web Site: https://sokoban.jp/
 
-
<br>
 
-
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
 
-
<br>
 
-
BoxSearch
 
-
Copyright (C) 2007 by Ge Yong
 
-
E-mail: notabdc@hotmail.com
 
-
Web site: unknown 
 
-
<br>
 
-
JSoko
 
-
Copyright (C) by Matthias Meger
 
-
E-mail: JSoko@online.de
 
-
Web site: http://www.sokoban-online.de
 
-
<br>
 
-
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
 
-
<br>
 
-
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/
 
-
<br>
 
-
Sokoban YASC
 
-
Copyright (C) 2001-2019 by Brian Damgaard
 
-
E-mail: BrianDamgaard@jubii.dk
 
-
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
-
<br>
 
-
YSokoban
 
-
Copyright (C) 2007 by George Petrov
 
-
E-mail: YGP@WriteMe.com
 
-
Web Site:  http://ygp.orgfree.com/sokoban.html
 
-
<br>
 
-
XSokoban
 
-
Copyright (C) by Andrew Myers
 
-
E-mail: andru@cs.cornell.edu
 
-
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
-
<br>
 
-
Sokofan
 
-
Copyright (C) 2005-2007 by Eric Leung
 
-
E-mail: eleung2@hotpop.com
 
-
Web Site: unknown
 
-
<br>
 
-
Sokolution
 
-
Copyright (C) 2016-2019 by Florent DIEDLER
 
-
E-mail: fdiedler2000@gmail.com
 
-
Web site: http://codeanalysis.fr/sokoban/ 
 
-
<br>
 
-
Trademarks
 
-
==========
 
-
<br>
 
-
Company names, brand names and product names are trademarks
 
-
or registered trademarks of their respective holders.
 
-
<br>
 
-
Contact
 
-
=======
 
-
<br>
 
-
E-mail: sokoban@online.de
 
== Disclaimer ==
== Disclaimer ==

Revision as of 16:28, 24 April 2019

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

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 71 80
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 38

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.

Sokoban Solver Statistics - Large Test Suite - Solved Levels
Collection Author Levels BoxSearch Takaken YASS JSoko Sokolution
Aymeric Aymeric du Peloux 282 282 282 282 282 282
Grigr2001 Evgeny Grigoriev 100 93 94 93 92 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
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
Total 3272 2553 2880 2680 2538 2939

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.

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

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
Grigr2001 Evgeny Grigoriev 100 93 94 93 92 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
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
Sharpen Sven Egevad 153 34 76 43 46 84
SokEvo Lee J Haywood 107 107 107 107 107 107
SokHard Lee J Haywood 163 163 163 163 158 163
Sokoban Perfect Thinking Rabbit 306 146 261 188 188 233
Sokoban Revenge Thinking Rabbit 306 148 244 194 171 214
Sven Sven Egevad 1623 1170 1384 1251 1147 1432
Y.M. Auto Yoshio Murase 52 52 52 52 52 52
Y.M. Handmade Yoshio Murase 54 54 54 52 52 53
Total 3947 2839 3375 3021 2872 3390

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/


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


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
Retrieved from "http://sokobano.de/wiki/index.php?title=Solver_Statistics"
Personal tools