The puzzle game of Sokoban has been fascinating to me since I was a child. It is played on a rectangular grid. Each square may be empty ( ) or contain a wall (#), a box ($), the pusher (@) , a box on a goal (*) or the pusher on a goal (+).
The player controls the pusher, where a single step is either up (u), down (d), left (l) or right (r). The pusher can push single boxes if the square behind is empty or a goal (indicated by uppercase letters in the notation). Wall squares are forbidden for both the pusher and boxes.
The number of boxes equals the number of goal squares, and the aim is to push all boxes to a goal square. The game is mathematically interesting as it is computationally very hard (PSPACE-complete) and indeed, there are very challenging problems already on pretty restricted grid sizes. Common metrics on the solutions are the number of moves and the number of pushes. (Often enough, there is no solution which is both move- and push-optimal.) For human intuition, push-optimality is easier to grasp than move-optimality.
I have been trying to improve my understanding of move-optimality. Let me start with a very easy example.
###
###@#
# #
## $ #
#. #
######
Many people will start to approach the box in a straight move, resulting in the 8-move solution ddLulDrdL. However, it can be done in 6 moves by dlDrdLL. Why does the second approach result in a shorter solution? The reason is that one should avoid unnecessary changes of direction while pushing a box around, since each such change involves two "empty" moves to relocate the pusher. The first solution has two direction changes, while the second one has only one, so consequently the first solution takes two more moves than the second one.
Now look at the following only slightly more involved example.
########
# @ ..#
# $ ###
# $ #
# #
######
Most people will solve this box by box, which might result in the 25-move solution lldRRdrUluRRlldddlUUluRRR or llddRRdrUUluRRllddlUluRRR (note that for the second box, we pick the path minimizing the direction changes as learnt in the first example). However, with a further switch of the pushed box, a 23-move solution can be found llddRUluRRRRldddlUUluRR.
I'm struggling to find a satisfactory understanding why that results in a shorter solution. The best thing I can come up with is something like "it is costly to get behind the boxes, so when doing that investment, try to get done as many things as possible from that spot". However, this argument is somewhat diffuse and it is not hard to design a level where the same reasoning won't result in an improvement.
Can anyone give some better higher-point-of-view intuition/explanation of the improvement? Is there some useful metric/invariant (like the number of direction changes in the first example)?
EDIT: Let me try to give an alternative formulation of what I'm hoping for: From example 2, I got the vague understanding that in certain situations it may be helpful to push different nearby boxes "in one sweep" towards the goal squares. But most of the time I have no idea if in the end it will actually make a difference or not. So I'm looking for better insight or some heuristic which allows me to get a higher confidence of the final outcome.
Since you have the moves codified by strings, and you need a way to rank these strings of same length in a way to compare which one is "easier" as game, I think a good metric could be using the Kolmogorov Complexity for these arrays, since will gives a non-arbitrarily way to weight how difficult they are as a game, thinking here, in ranked them on how hard would be to memorize each of them string to use them as "cheat codes", for example, on an imaginary game of PS1 (yes, I am old hahaha), remember a string of 6 movements R-L1-L-U-R1-L1 is harder than U-D-U-D-U-D.