Heiner's solver

From Sokoban Wiki

Revision as of 23:50, 30 November 2010

I'm Heiner, and have written a "brute force" sokoban solver. Here I want to tell about it.

How it started

The "initial ignition" was an idea about "deadlocks", i.e. their detection. Somewhere I had seen a hand written list of small patterns, used for deadlock detection. That appeared to me to be the wrong way. And I had an idea how to compute a certain class of deadlocks from basic principles. So I started to write a simple sokoban solver in Tcl. That was in 2007.

Later (still in 2007) I changed to ANSI-C, since Tcl wasn't fast enough, any more, and also used too much memory... my method needs large amounts of memory.

But the Tcl prototype was a good exercise to prepare the C program.

Legend

The terms I currently use, may be a bit non-standard. I found this Wiki in late 2010, and start to recognize that others use different words. While I have not switched, this is what I used up to now:

• actor: the moving "man", the warehouse keeper, the "@"
• packet: the moved objects (some say "box"), the "$"
• harbor: the packet destinations, the "."
• configuration: a complete description of a situation: location of actor and of all the packets

The basic solver method

I use the most simple method, not specific to sokoban. We have a starting configuration, a terminal configuration, and a definition of legal moves, which allows writing a function which maps any configuration to the set of legal successors.

This setup is enough for writing a simple puzzle solver, that searches for the shortest solution path.

We have a collection of pairs (configuration, distance), e.g. implemented as a hash table. We enter the pair (start-config, 0). Then, for increasing distance d, from all entries with distance d we generate all immediate successors, and those, which are not yet known, are entered with distance d+1. Each new entry is checked, whether it is the seeked for terminal configuration.

Once the terminal configuration is entered, we can stop the above, and extract a shortest solution path, starting with the terminal configuration, and searching for an immediate predecessor with a distance 1 smaller, and so on.

What is a "move"

I choose a "move" to be an arbitrary actor walk followed by exactly 1 push action. That way I generate push-optimal solutions. I could have chosen to make every small step of the actor a "move", and would get move-optimal solutions. The drawback would be to need much greater distances, and to generate much more configurations.

Counting pushes instead of moves appeared to me to be the most natural measure. Your mileage may vary.

Solving forward

The above description is the forward method. It is the most natural thing to do, but it is not the only way, not even the best one...

Solving backwards

The attentive reader already noted, that the solution path extraction already needs an inverse move generator, generation immediate predecessor configurations. For sokoban this is not really hard to write.

Why shouldn't we start with the terminal configuration, and generate their predecessors, until we find the initial configuration? Nothing can stop us, it is a perfect mirror image of the above method, except... we do NOT generate the exact same set of configurations.

I did some experiments, and learned, that often the backward method generated less configurations than the forward method, but not always.

While contemplating how to decide for the best of both, I found a third method...

Solving mixed