Moves vs. Pushes
From Sokoban Wiki
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:
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!
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).
There are also some secondary 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.