Heiner's solver
From Sokoban Wiki
(→Solving mixed) |
|||
| Line 119: | Line 119: | ||
May be everybody knew this already, | May be everybody knew this already, | ||
but for me it was a genuine invention. | but for me it was a genuine invention. | ||
| + | |||
| + | == Computing deadlocks == | ||
Revision as of 00:16, 1 December 2010
I'm Heiner, and have written a "brute force" sokoban solver. Here I want to tell about it.
Contents |
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. What cannot be changed by "playing the game", is not considered part of a configuration, but is stored elsewhere, e.g. walls and harbor locations.
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
In a sense this is very simple. We start solving forward and backwards, in separate collections (hash tables), one distance step at a time. And we check the new entries in one collection also against the other collection, and when we find a match, we have a solution, of minimal total distance.
Since these search trees tend to have much more entries for the larger distances, we now have used considerably less memory. That is quite important, since our method is clearly memory bound.
We still can improve this: instead of using a fixed alternation between forward and backward steps, we can do the next distance increasing step on that collection, where the front (the entries with the maximal distance) is smaller. The size of the front is a good (relative) estimate of the next front.
The extraction of a shortest solution path is not exactly trivial any more,
but it is not really hard, either.
Details are left as an exercise ;-)
That is what I currently use (Dec-2010). May be everybody knew this already, but for me it was a genuine invention.
