Solver Statistics

From Sokoban Wiki

Revision as of 16:23, 24 April 2019 by Matthias Meger (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

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:

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

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	1180	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	2571	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