Sokoban

Any topic that does not fit elsewhere
Post Reply
luke_g
Posts: 29
Joined: Sun Feb 17, 2008 9:52 am

Sokoban

Post by luke_g » Mon May 26, 2008 11:24 pm

Here's an interesting game I ran into which is hard for computers. It's a 1-player puzzle game, and humans can solve many problems that computers cannot. There doesn't seem to be a lot published recently (in English, at least), but I thought it was a good read.

Here's a PhD thesis about the game and single-agent searches:
http://www.cs.ualberta.ca/~games/Sokoban/papers.html

There is a wiki with some info beyond what's in the thesis:
http://sokobano.de/wiki/index.php?title=Solver

This is apparently the state-of-the-art solver, but I didn't see any explanation of the techniques.
http://www.ic-net.or.jp/home/takaken/e/soko/index.html

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Sokoban

Post by Rémi Coulom » Thu May 29, 2008 7:27 am

Yes, this is a very interesting problem.

I have started to study classical planning (with that book: http://www.laas.fr/planning/). I expect some plan-space techniques may apply, although it seems existing approaches to sokoban are usual state-space search.

Rémi

vintermann
Posts: 14
Joined: Wed Feb 13, 2008 11:03 am

Re: Sokoban

Post by vintermann » Thu May 29, 2008 10:26 pm

I have actually written a solver in Java that is marginally useful. It solves most of the small puzzles, such as David Skinner's Microban, and (unless I remember wrong) all of the machine-generated puzzles by Yoshio Murase. It didn't stand a chance at most puzzles in Skinner's Sasquatch collection, though.

It was just straightforward A* search (if I did it correctly!). Sokoban is equally easy to solve backwards (usually easier for human-made puzzles!) and I experimented with an approach that tried to solve the puzzle from both ends at the same time. But it wasn't nearly as good as A*.

darrencook
Posts: 2
Joined: Tue Oct 28, 2008 5:47 am
Location: Tokyo, Japan
Contact:

Re: Sokoban

Post by darrencook » Tue Oct 28, 2008 6:01 am

(I studied Sokoban about 10 years ago, focusing mainly on rules to safely narrow the search, but I didn't publish anything.)

Takaken's 86 out of 90 on the xsokoban set is incredible; as shown in Jonathan Schaeffer's papers the harder problems are orders of magnitude harder. So scoring 86 isn't just twice as clever as scoring 46 (which seems to be score of the other programs), it is millions of times cleverer!

There is some algorithm explanation here, but all in Japanese:
http://www.ic-net.or.jp/home/takaken/nt/soko/index.html

Has anyone tried applying monte-carlo techniques to Sokoban? There was a paper on how it was helping in another puzzle game ("SameGame") at CG2008 (Google for "Single-Player Monte-Carlo Tree Search").
Software Researcher/Developer
http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
open source dictionary/semantic network)
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Sokoban

Post by Rémi Coulom » Wed Oct 29, 2008 11:06 am

Hi Darren,

Welcome to the Game-Programming Forum.

I don't expect Monte-Carlo search would work for Sokoban. In Sokoban, a playout is either a success or a failure. As long as you do not find the solution, all playouts are failures, so there is no information you can get from them. As soon as you have a single success, then you have solved the problem. I don't believe this approach could beat classical algorithms.

Rémi

darrencook
Posts: 2
Joined: Tue Oct 28, 2008 5:47 am
Location: Tokyo, Japan
Contact:

Re: Sokoban

Post by darrencook » Wed Oct 29, 2008 11:32 am

Hi Remi,
You wrote, regarding failed playouts: "there is no information you can get from them".

(The below is all brainstorming...)

One piece of information is how close you were to a solution at the point you hit deadlock, either measured as "number of blocks in a goal position", or total Manhattan distance from a solved problem. Or how many moves it survived before hitting deadlock. Or some combination of both.

Or, even, use a special playout that is allowed to cheat when it gets into deadlock. Then problems always get solved, and we use a score like: number of moves + 10*number of cheats. (i.e. lower is better)

In sokoban you can work back from the solution to try and hit your current position. How about sending monte carlo un-playouts (play-ins?!) and measuring their score as the distance from the current position. (I think that idea is a bit crazy, but I thought I'd mention it in case it triggers a better idea by someone else.)

As yet another idea, the manhattan distance is often used as a quick heuristic. How about 100 random playouts of fixed depth 10 from a position and sum the score at the leaves, and use that as the guiding heuristic in a more traditional search algorithm.

----
Darren Cook, Software Researcher/Developer
http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
open source dictionary/semantic network)
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)
Software Researcher/Developer
http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
open source dictionary/semantic network)
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Sokoban

Post by Rémi Coulom » Thu Oct 30, 2008 6:14 pm

Yes, I understand you can try to measure something else besides just success or failure. But I don't expect it would work. I am not extremely familiar with Sokoban, but I suppose there may be problems where moving all blocks but one is easy, but solving the problem is very difficult (and requires a very different strategy).

Rémi

Post Reply