Sokoban solver, tips [closed]

Question

I have to do a Sokoban solver (http://en.wikipedia.org/wiki/Sokoban). Have you ever done one? I am searching for tips, not for code. Like "you may use the IDA* alg" or "I used that heuristic and it was quite good" or "I use that tech no avoid deadlocks".

Basically I want to write on a paper the strategy before writing any code.

Answer 1

I have written my Master's thesis on Sokoban algorithms. I aimed to provide a good overview on the techniques used in Sokoban solvers. It does not provide definite answers, but might provide a good starting point for someone interested in writing a Sokoban solver.

http://weetu.net/Timo-Virkkala-Solving-Sokoban-Masters-Thesis.pdf

Answer 2

Terms

field - the level, whole playing area of the current game.

position - a phase, set-up in the field.

final position - a position in which no turn is possible - either the goal or a deadlock.

box - same as crate.

Theory

Just a little bit of logic - it seems obvious but we'll use it in the implementation part.

So - about every game of Sokoban, we can say that it is one of these:

• solvable, unsolved - in the process of solving
• solvable, solved - the goal
• unsolvable, unsolved - if our implementation yields no results, and there are no more possible moves / combinations of moves

Now - a Sokoban game consists of turns that are:

• moves - the character can move in an area defined by walls and/or boxes, this area is smaller or equal (if not counting the walls, and there are no boxes) to the whole playing area - however, moving the character around the field makes no difference except score, which is irrelevant for the actual solution - let's ignore it for now
• pushes - pushing the boxes is much more important, and can potentially lead to our goal - solving the field - by pushing the boxes at their respective goals

A box can be:

• in-goal - most likely this box does not need to be moved, and some rules can prohibit a box from moving when at a goal position (very unusual)
• pushable - in 1 to 4 directions
• unpushable, not at goal
  • blocked by 2 walls - the current position is unsolvable no matter what
  • other - we will get to this box later - for now a crate stands in our way

Process

This is the step-by-step process we will use in solving (definitions underneath):

1. populate possibleTurns_n with every directly accessible push (pushable or in-goal) in the current position, with player at the current place
2. take the first item in possibleTurns_n, remove it and execute it
3. see if the current position:
   1. is final - goal - solved, do not do anything
   2. is final - deadlock - this turn led to a deadlock, don't populate it anymore, go back to 2. step, n stays the same
   3. is not final - increment n and populate possibleTurns_n with possible turns in this position

Definitions:

possibleTurns_x - a two dimensional array, or an array of arrays - the x defines the "depth" of the turns

n - in the beginning is zero, will be incremented in the execution of the algorithm above

Tips

Finally - the process above will leave you with a combination of turns that will leave to a solved position. Last thing to do is to use an algorithm like A* to determine the shortest route between these turns / pushes, to maximize the speed and score, minimize number of in-game turns.

Answer 3

You can create a brute force solver that tries to move your man in every possible direction. By using recursion (or a stack) you can track back your steps if a solution is not found.

A* probably won't do you any good, because you don't have to find your way through a maze, but also need to move the boxes. This means you may need to take a step back in the same direction you came from after moving a box. So for every step you need to evaluate all directions, including the one you came from. That is, unless you didn't move a box in the previous step.

[edit] You could use A* to make it a little smarter; to find a way from your current position to any of the positions you can move a box from. That would probably make your solution more efficient, because you won't have to track all positions inbetween, but only the positions from the last box you pushed to the next box you'll push.