Making a useful automatic solver for sokoban puzzles has been a project of mine for years. Now, I have many projects and little time, but this one I've worked hard at, many times, from many different approaches and in many different languages.
Returning to the language I know best (after all), Java, I have finally made a useful sokoban solver. It's possibly the most stupid solver I've written, it's basically a depth-first search, but it works. And it's generic! I have made a library which can take as input arbitrary puzzles, and do a depth-first search on the game tree. I have even made a (much) improved version, which needs some more info, but which can search from the end positions at the same time.
I used a simple labyrinth game to debug the interfaces. When it worked, I tried it out on a marbles/atomix type game - that was less useful, because although marbles is a reversible puzzle of the kind my library is designed for, any given state has quite a lot of predecessor states, and there are many possible end positions. Still, puzzles with three or four marbles were usually solved - eventually :-)
Sokoban, to my delight, was much easier. Even with no checking for dead squares (squares where a crate can never be safely placed), and just forward search, the first 11 puzzles in Yoshio's Autogenerated fell in seconds! David Skinner's Sasquatch, though, is a lot tougher. When I implemented dead squares checking, the first two fell easily enough, but after that... There are usually a lot of crates in handmade levels. I suspect I have to check dynamically for stuck crates to have a chance at those. But I haven't even implemented backwards search yet, so there is plenty of room for improvement!
It would seem sokoban is easier than marbles/atomix for the purposes of this search. On the other hand, I've tried to make sokoban solvers for years, so I've picked up a lot of tricks, like dead crate elimination. Perhaps there are such tricks for marbles/atomix too, but I couldn't think of any.
It's the java standard library which has made this possible for me. In particular the new generic collections in 1.5 (which Sun has decided to call 5.0 for PR reasons). Also, Stig Brautaset's Generic Game Tree Library has been an inspiration, although I haven't really looked at the code... I've just read about it and tried the examples.
In fact, this project has been so wildly successful (I only started it days ago!) that I want to make a generic alpha-beta-search game-tree library of my own, for java, as a school project. Threaded, so that the computer opponent can look forward when it's your turn to move, too. I don't know if Stig Brautaset's library is multithreaded, but I suppose that if I want to avoid charges of plagiarism I shouldn't look too closely at his source code anyway :-)
Comments are disabled because of spam. Instead, mail me at stud hials no with 020042 in front of the @. That one is for you too, Stig. (You do google your name occasionally, don't you? :-)
Posted by vintermann at September 14, 2005 12:47 PM