Moves vs. Pushes
From Sokoban Wiki
Revision as of 21:26, 18 January 2009
The main aim of the game of Sokoban is to solve a level - no matter how.
Advanced players aren't satisfied with just having solved a level.
Hence, they try to optimize their solutions. To recall here is the background of Sokoban:
The idea of the game is: A level represents a store room, where boxes appear to be randomly placed. A warehouse keeper has to push the boxes around the maze of the room so that, at the end, all boxes are on marked fields.
As in reality the task for the warehouse keeper isn't just to push the boxes to their designated positions. He, of course, tries to do his "job" with as little effort as is possible.
Jean-Pierre Martel describes this very beautifully:
You are a storeman and there is a job to do: bring all the boxes to the goals.
For me, what the storeman really wants is to find the best way to do this job. Because he knows that he has to do this job everyday and not only once.
Hence, he will try to optimize his job. The more he optimizes the parking of the boxes (the solutions) the more he will have free time to drink a cup of coffee, and chat with his mates :-)
If you just solve levels, it means that you don't really belong to the warehouse. You are an interim worker. You have come here just for one day, you unload the truck, park the boxes and leave for another mission.
On the other hand, if it's your warehouse, if this is your daily job, you want to love your warehouse. You want to know the personality and the secrets of your store. You want to know all the tricks which could improve your everyday work. You are the warehouse keeper and no one should be able to do what you can do in the time that you do it (... optimal solutions).
Moves vs. pushes
The effort for solving a level can be divided into two parts:
- moving to the correct position for pushing a box
- pushing a box
Here is an example level:
The player can push the box to the left, then run around to the other side and push the box to the goal. This results in a solution of 8 moves and 4 pushes.
The player (= the warehouse keeper) just has to move 8 times which is optimal for this level and therefore this is the solution which requires the least effort for solving the level.
However, in reality, pushing a box surely is more exertive as just moving to another place. Hence, it may make sense to go a long way around to push the box to the right immediately.
This will result in a solution of: 12 moves and 2 pushes.
Which solution is the better one ?
Well, in reality this depends on how much work it is to push a box and how much work it is to move. If one assumes that pushing a box is 10 times more work than to move then the solution with 2 pushes will be preferred. If a push of a box is nearly as exertive as a simple move than the 8 moves / 4 pushes solution will be preferred.
In reality there is some ratio of pushes and moves (1 push is worth 4 moves for example).
For the computer game Sokoban this is simplified. There are just two commonly used ratios:
- 1 push is worth ∞ moves
- 1 move is worth ∞ pushes
which results in these two types of solutions:
- Moves optimized solutions
- Push optimized solutions
From this it follows that the shown example level has two optimal solutions: One optimal moves solution and one optimal pushes solution.
Note: a ratio of 1 to ∞ doesn't mean that the other value is completely irrelevant!
Exmaple:
A solution of 20 moves / 4 pushes is a better solution for a level than 20 moves / 6 pushes
The parity of the pushes needed to solve a level is fix for a specific level. If there exists a solution for a level having 10 pushes then it is impossible to solve the level with an odd number of pushes, for example.
The parity of the moves is determined by the parity of the distance of the player's start position to the player's end position (the position of the player after the last push has been made for solving the level).
Secondary values
There are also some secundary values displayed in some programs. Here is a description of them.
- Box lines
- pushing a box one or more times in a specific direction result in a "box line". A box line starts with a push of a box and ends either by a move or by a push of another box.
- Box changes
- every time a new box (= another box than before) is pushed this value is increased. Attention: The first time a box is pushed in a level is counted as box change, too.
- Pushing sessions
- change from moving the player to pushing a box. This value is increased each time a box is pushed after a non-pushing player-move has been made.
- Player lines
- every time the player changes his direction when moving is counted as the begin of a new player line.
