Solvers and Optimizers

2016-08-14

First came the Sokoban player. Then came the Sokoban solvers and the Sokoban optimizers.

A solver is a program that finds a solution for a Sokoban level.

An optimizer is a program that finds a shorter solution on the basis of a given solution.

Solvers

Probably the oldest solver is Rolling Stone, developed at University of Alberta, Canada, Department of Computing Science by Andreas Junghanns and Jonathan Schaeffer.

Other noticeable solvers has been developed by Joris Witt and David White. And the now discontinued webpages of Paul Voyer and Adolfo Ovalle contained online Java Sokoban solvers.

One more solver to mention is the solver developed by Ben Dogan for his Sokoban level design competition spring 2015. This solver is not available.

A simple solver was developed 2008 by Pavel Klavik from The Czech Republic. Pavel is probably more known as author of the Sokoban program Armageddon.

Today you probably only want to use the following three solvers:

The solver in Matthias Megers Sokoban program JSoko. The solver continuously gets developed and updated.
The solver YASS (Yet Another Sokoban Solver) in Brian Damgaards Sokoban program YASC. Also still further developed and updated. YASS is actually a plug-in that can be used in other Sokoban programs as well. An example is Jorit Wits Sokoban++.
The third solver worth mentioning is Takaken developed by Kenichiro Takahashi. Development stopped 2008 but the solver is still very effective and beats the two newer solvers big in certain areas. More about that later.

You will find a comprehensive test comparing the different solvers at Sokobano.de . The solvers tested was the last three mentioned and Boxsearch by Ge Yong. The website for Boxsearch is long gone and only found in The Internet Archive.

The solvertest was last updated 2013 and both JSoko and YASS are improved considerably since then.

Optimizers

You will find two optimizers: Again from Matthias Megers JSoko and YASO(Yet Another Sokoban Optimizer) from Brian Damgaard.

An informal test

Which solver and which optimizer are the best?

I decided to make a small test with the solvers YASS, Takaken and JSoko and with the optimizers YASO and JSoko.

First I solved the 10 levels in my collection “Numbers” with each solver. None of the solvers found a solution for “Four”. And all the solvers found solutions for the rest of the levels. Mostly within less than two minutes. JSoko took some time to solve “Seven” and “Eight”, but the job was done in due time. YASS had similar problems with “Zero”.

Then I let the optimizers try to find shorter solutions on the basis of the solutions found by the three solvers.

Results for the YASO optimizer:

	YASS		Takaken		JSoko
	Moves	Pushes	Moves	Pushes	Moves	Pushes
0	331/97	331/97	331/103	331/103	325/97	325/97
1	178/57	270/49	178/57	178/57	178/57	178/57
2	261/43	261/43	230/55	410/53	230/55	230/55
3	207/43	267/35	207/43	207/43	207/43	207/43
4	n/a		n/a		n/a
5	139/43	139/43	139/43	139/43	139/43	139/43
6	193/74	193/74	159/52	159/52	166/56	166/56
7	516/146	886/138	516/146	516/146	516/146	516/146
8	158/52	275/46	158/52	158/52	162/50	162/50
9	741/219	741/219	739/223	905/219	743/219	743/219

Results for the JSoko optimizer:

	YASS		Takaken		JSoko
	Moves	Pushes	Moves	Pushes	Moves	Pushes
0	339/107	359/99	339/101	363/99	331/103	331/103
1	186/51	190/49	180/51	190/49	182/53	192/51
2	261/43	261/43	298/49	310/47	292/51	310/47
3	213/35	213/35	271/61	277/59	211/39	215/37
4	n/a		n/a		n/a
5	139/43	139/43	151/45	153/43	202/61	202/61
6	206/58	209/54	183/50	187/48	192/62	193/54
7	524/144	554/136	520/141	554/136	522/140	556/136
8	205/50	223/46	193/62	195/60	188/50	188/50
9	759/221	767/215	759/219	759/219	743/221	761/215

Red= Best, Yellow= A tie.

Seems YASO is best at finding solutions with few moves and JSoko solutions with few pushes.

I used standard settings except for setting solving timeout to one hour. It might be possible to obtain better results with other settings.

Looking a little closer you will find the average results moves/pushes don’t differ very much. But not always. One remarkable difference is how YASO handles “Two”. 31 moves more with the YASS’ solution than the Takaken and JSoko solutions? Actually the basic solutions before optimization are quite different. YASS found a solution where the bottom of the level is solved first. Takaken and JSoco found a solution where the top of the level is solved first. In this case, as probably in most cases, the optimizer doesn’t find a new solution but optimizes the first found solution.

Didn’t check it out but in “Five” YASO obviously found the same optimization whatever the provided solution at first. And JSoko just as obivously didn’t do that.

All my basic solutions and optimizations can be downloaded here if you want a closer look.

The Original levels

I wanted to know if the latest versions of YASS and JSoko have improved from the Sokobano test 3 years ago. They have. Both solve several more levels. I just tested the results for XSokoban (The EASY Extended Original Collection).

Why EASY ? Well, the small changes made in level 37 and level 50 makes these levels easier solvable both to humans and solvers.

Takaken, YASS and JSoko find a solution for 37X (As in XSokoban).
YASS finds a solution for 50X.
None of the solvers find a solution for 37O and 50O (As in Original)

I will leave 37 for now and just show you 50:

Three differences that complicate matter. But what is important ?

Actually I tried changing the differences one by one in every possible combination (Eight including the XSokoban layout).

The result ?

Only the XSokoban layout is solved by YASS. (Didn’t try JSoko and Takaken)

Something interesting about a prequel to the final “Four:

Solving the layout at left took YASS a fraction of a second.
Takaken used 31 seconds.
JSoko surprisingly quit.

None of the solvers found a solution for the published “Four”. A human (me) hadn’t the slightest difficulty to go from the old layout to the new.

I presented this to Brian Damgaard. Might give some inspirations to future versions of YASS. The problem was known. I am looking forward to see if future versions of YASS crack this level.

Triumph of Takaken

Just played a little around with the solvers and by totally chance discovered this

Neither YASS or JSoko solved this old level of mine. Takaken needed 41 seconds.

Had to try another one of the same sort: A rather big not very complex level for humans but how about Sokoban solvers:

Same thing. Only Takaken succeeds.

Interesting!

Today the solvers perform better but how much?

Well, actually much better.

Back in the 90’es solving of the “extended XSokoban original” was the golden standard. And Rolling Stone was king of the solvers. As far as I know.

Not so anymore. The table below shows the results for the solvers tested at Sokobano.de plus the results for Rolling Stone 1998.

The list is updated wit the results for YASS (2.136) and JSoko (1.72). Compared to the results at Sokobano.de both YASS and JSoko find more solutions. Marked with red. Still no solver cracks Screen.29

Rolling Stone	Boxsearch	JSoko	Takaken	YASS
1 2 3 4 5 6 7 8 9 10 11 12 – – – – 17 – 19 – 21 – 23 – 25 26 – – – – – – 33 34 – – – 38 – 40 – – 43 – 45 46 47 – 49 – 51 – 53 54 55 56 57 – – 60 61 62 63 64 65 – 67 68 – 70 – 72 73 – 75 – – 78 79 80 81 82 83 84 – – – – – –	1 2 3 4 5 6 7 8 9 10 – – – – – – 17 – – – 21 22 – – – 26 – – – – – – – – – – – 38 – – – – 43 – – 46 47 – 49 – 51 – 53 54 55 56 – 58 59 60 – 62 63 64 65 – 67 68 – 70 – – – – – – – 78 79 80 81 82 83 84 – 86 – – – –	1 2 3 4 5 6 7 8 9 10 11 12 13 – 15 16 17 18 19 20 21 22 – – 25 26 27 28 – – – – 33 34 – 36 37 38 39 40 – 42 43 44 45 46 47 – 49 – 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 – 67 68 – 70 – – 73 – 75 76 – 78 79 80 81 82 83 84 85 86 87 – 89 –	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 – 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 – 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 – 67 68 – 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90	1 2 3 4 5 6 7 8 9 10 11 12 13 – 15 16 17 – 19 20 21 22 23 24 25 26 27 28 – 30 – 32 33 34 35 36 37 38 – 40 – 42 43 44 45 46 47 48 49 50 51 – 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 – 78 79 80 81 82 83 84 – 86 87 88 – –
52	52	71	86	79

Which solver and which optimizer are the best ?

The solvers you want to use are YASS, Takaken and JSoko.

And both YASO and JSoko optimizers.

If you don’t use all the tools you can’t always be sure you have got the optimal solution for a level. The solvers might find a solution, but not necessarily the best. And the optimizers usually only improve known solutions. They don’t find new solutions.

If you only used YASS you would think 262 was the moveoptimal result result for “Two”.
And if you didn’t use YASS you would think 47 was the pushoptimal result for “Two”.

Where to get the solvers and optimizers

Takaken – Website still works even if there has been no update since 2008.

YASS – Just download YASC

JSoko – Just download the program

Boxsearch – Get it here at Sokoban.dk. Website discontinued some years ago.

Rolling Stone – For the ones with a Unix/Linux computer and historical interest.

The skin? Nice. Isn’t it?

Digging deep into the files of Kohns Sokoban2 I rediscovered the original graphics and remade the skin with seamless bamboo walls, goals looking more like real Go and a little animation of course. Find the skin in common skin format here.