Pruning duplicate positions
From Sokoban Wiki
Current revision as of 15:18, 13 July 2006
This is a detailed view on how to prune duplicate board positions during the search.
To detect duplicate board positions we have to store every board position reached during the solving process. The level stays the same during the solving process. The only level elements that change their positions are:
- the player
- the boxes
Hence, it suffices to store the positions of all boxes and the player position per board position.
If the solver doesn't searches for a moves optimized solution we can improve the duplicate check:
These two board positions have equal box positions but a different player position. Nevertheless, the board positions that can be created by pushing one box are exactly the same! Hence, these two board positions can be treated as being equal! In general, all board positions that have the same box positions can be treated as being equal when the player has the same access area. The player in the left board position can reach the position of the player in the right board position and therefore can do the same pushes as the player in the right board position.
With this in mind we could do the following when checking whether a board position has already been reached:
- check if there is a board position stored that has exactly the same box positions
- check if the player in this board position can reach the position of the player in the current board position
Do optimize performance it's better not to store the actual player position but an information about the area the player has access to. This can be done by storing the most top left position the player can reach, for example. In both board positions shown above the top most left position the player can reach is the same: it's the top left corner of the level.
The best way to store the information is to use a hash table.
