Page 1 of 1


Posted: Mon May 26, 2008 11:24 pm
by luke_g
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:

There is a wiki with some info beyond what's in the thesis:

This is apparently the state-of-the-art solver, but I didn't see any explanation of the techniques.

Re: Sokoban

Posted: Thu May 29, 2008 7:27 am
by Rémi Coulom
Yes, this is a very interesting problem.

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


Re: Sokoban

Posted: Thu May 29, 2008 10:26 pm
by vintermann
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*.

Re: Sokoban

Posted: Tue Oct 28, 2008 6:01 am
by darrencook
(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:

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").

Re: Sokoban

Posted: Wed Oct 29, 2008 11:06 am
by Rémi Coulom
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.


Re: Sokoban

Posted: Wed Oct 29, 2008 11:32 am
by darrencook
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 (English-Japanese-German-Chinese-Arabic
open source dictionary/semantic network) (About me and my work) (My blogs and articles)

Re: Sokoban

Posted: Thu Oct 30, 2008 6:14 pm
by Rémi Coulom
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).