16

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.

3 Answers 3

26

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

0
7

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 possibleTurnsn 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 possibleTurnsn, 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 possibleTurnsn with possible turns in this position

Definitions:

possibleTurnsx - 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.

1

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.

3
  • Brute force is not feasible if the maze is big. I am talking about mazes around 30 spots, and 3-4 diamonds / goals. As far as I can see the problem has to be divided in different steps, and is there where I have problems. 1. how to represent the state of the puzzle. 2. how to move between steps (the man can move in 4 directions). 3. how to decide the best next step (thats the hardest point). and then some sub problems like finding if you are on a deadlock.
    – Dr Sokoban
    Nov 21, 2010 at 11:41
  • That last step is what you can do with trial and error (brute force). It will take forever for a human to blindly try every direction, but for a computer that is no problem at all. Like I said before, you don't have to remember every step the man takes, but only the steps that move a box. The only thing you need to remember(to store) are the actual updated field after the last move, and for each step, the old and new position of the box that moved. All other data can be deducted by rolling back staps on you stack.
    – GolezTrol
    Nov 21, 2010 at 13:11
  • 1
    As for detecting deadlocks: you need to store some value for each field state. If the value is in your list of previous states, that means that that situation has occurred before, and you're in a loop. You can store a hash of the board, but maybe you can store the entire board as well. You can store the position of boxes in the field if you want. 10 boxes in a 256x256 field can be stored in only 20 bytes. If your fields are smaller, you can even compress this data a little. Even a stack of a million attempts 'only' takes 20MB to store, which is peanuts for any modern computer.
    – GolezTrol
    Nov 21, 2010 at 13:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.