DHolland S2
From Sokoban Wiki
Revision as of 18:08, 26 March 2010
Section 2. Heuristics
=========
The maze
Given a Sokoban position, the "maze" is defined as the walls and rooms of the position (where all the boxes and the man are removed); thus it is uniquely determined by the puzzle and does not depend on the variation (the pushing of the boxes).
Box removal
As has been noted before, a Sokoban puzzle may become trivial if one box is removed, without giving any clue as to how to solve the original position. However, certain kinds of dependencies may be specified by looking at positions with boxes removed. This technique can be useful in many heuristic methods.
Here is one example.
Boundary box removal
In the previous section I discussed corrals, one-way-systems and circuits (in increasing order of accessibility). In a general position perhaps with multiple corrals, one could try removing boxes in an attempt to reduce the number of corrals, convert one-way systems to circuits, and increase the number of circuits. As with free space, it may be "good enough" to find one way to do this without finding all possible ways, and thus to find lower bounds. Of course, it is normally a trivial matter to reduce a position with n corrals to one with a single corral by removing n-1 boundary boxes, and it might not seem that this generates any useful information. But if one takes into account neighbours of boundary boxes, it may be necessary in some areas of a corral to remove more than one box to reduce the number of corrals, so there could still be useful information to be gained: here one would first look for boundary boxes with empty push-squares in two (or more) different corrals. When considering a subtask such as trying to find a variation which merges two adjacent corrals, it is meaningful to have a numerical estimate of the minimum number of ""essential" boxes which has to be relocated to do this, especially when making use of previous estimates of the number of free spaces in each corral. Of course, an actual variation to merge two adjacent corrals might move a lot more than the (more precisely, a) "essential" boundary box separating the two corrals. It also might change the shape and identity of the two corrals substantially, affecting other corrals. Even so, it might still be helpful in a search broken into subtasks to match up such numbers to help identify subtasks which are potentially easily performed. If a corral and its neighbour both have at least one free space, and there are boundary boxes with empty push squares in both corrals, the potential to merge the two corrals (in either direction) is there, and it is more likely to be possible, all things being equal, than if neither corral has free space. Thus, the box-removal data can potentially be useful in ordering subtasks based on estimated likelihood of success.
Reverse search box removal
Ideally, from a given solved position (with given man access) we'd like to pull out the boxes and distribute them evenly all over the position so that there is only one corral and every box is potentially pushable (so, not still frozen on a goal). It would be even better if there were multiple circuits, so the likelihood of the puzzle becoming trivial (assuming some random sprinkling of start positions for the boxes also with only one corral) is relatively large.
To expand on the previous section's discussion of free space, we can make estimates of the free space in the maze and within the given solved position. We can also consider matching the number of free spaces in each room with the number of start squares in that room, so that we are aiming to produce a position, in reverse mode, which is "near" to the start position of the puzzle in the approximate sense in that there are the same number of boxes in each room.
Naturally, in the solved position or the start position or intermediate positions, there may be multiple corrals, and no circuits, so this ideal situation may not arise. But it could still be useful to make an estimate of how far away from this ideal situation we are in the following sense.
First try pulling a single box at a time; it may be that we can reach one of the distributed free space squares. If there are multiple different rooms in the maze we might consider it a success to pull the box away from a packed goal room and into an empty room, thereby spreading out the boxes more than they are in the solved position. More generally, we'd like to match up more closely the numbers of start squares all over the maze with the numbers for the current corral, and the number of potentially movable (pullable or pushable) boxes.
To get to a single corral, we could try removing (as few boxes as possible) from the start position; we could also compare with the data based on the number of free spaces within the maze - even if the start position has multiple corrals, it might be that we can quickly identify a set of "spread out" box squares in the maze for which there is a single corral. This gives us (one or more) estimates of how many boxes we can fit into a spread out arrangement with only one corral.
Now consider again pulling out a single box at a time from the solved position. We may be able to reach a previously identified start square of one of the boxes or a square with the box now on one of the "spread out" box squares with a single corral (even though the current position with one box pulled out may not have a single corral). But the box may not reach one of our targets; if not, we can make a note of its "pull access" (the generalisation to pulls of the push access). Perhaps we can re-designate a target within the push access to satisfy the same conditions. If not, we can then consider it to be interfering with our ideal situation, so we remove this box. By applying this approach successively, removing the box if we can't reach a target, or redesignate a target appropriately, we get an estimate of how close to our "spread out" arrangement we can get in the simplest possible fashion, with successive moves of a single box.
We then attempt to reinstate the removed boxes into "parked" squares (one of the squares within the pull access) with the least amount of interference with pulling out the other boxes. Ideally, we'd like to pull the offending boxes to a parked square, carry on pulling the other boxes out to the previously identified squares, and intersperse moves pulling the offending boxes from the parked squares to their designated targets.
Any time we are successful with some part of this program, we get potentially useful information about parts of the original subtask (pull out all boxes to spread out squares) that we can easily manage. Even when we fail, we have potentially useful information about how difficult the original subtask was.
Reverse search corral merging
In many of the XSokoban puzzles, the goals are within a single room, and many of the boxes are frozen. There may be more than one corral in the solved position, or pull access restrictions may restrict the rooms, or squares within rooms, to which the boxes can be pulled. These conditions may of course change dynamically as boxes are pulled out.
In the case of more than one corral in the solved position, it may not be obvious which corral the man should start in. We can first start pulling out boxes according to the above suggestions; however with multiple corrals we may end up pulling out a group of boxes into one corral, and then failing to move out more boxes as that corral fills up and we haven't opened access to the boxes in another corral.
But we can still use the information we obtained about how many boxes we dragged out; we can compare it with the minimum number of boxes we need to remove from the solved position so as to open man access to another corral. This is another box-removal heuristic. It is analogous to the description of "essential" boxes to open up corrals in the previous section (though with many boxes frozen on goals the number of "essential" boxes to remove may be much larger).
In some cases, the corral to start in can be simply determined by the maximum number of boxes we were able to pull out; the more the better. But in general, having got the estimate, we have to recast our subtask of dragging boxes out to "spread out" squares by preferentially dragging out "essential" boxes. With many frozen boxes, there might be many different candidates for "essential"; so it might be helpful to make a dynamic count of the minimum number of boxes we can remove to merge the corrals, so we can at least tell if we are making obvious progress to merging by pulling out a particular box.
Reversible moves
In establishing "spread out" squares for boxes, we can first aim for "reversible" arrangements. Here, if a box can reach one of the "spread out" squares, then it can reach any of the others and vice versa, either pushing or pulling that single box with all other boxes (apart from those not moved yet from their goals) removed. This is obviously complicated by mazes with push and pull access restrictions, so we'd have to split our arrangements up into sections according to whether those areas are reachable or not. The point of reversible arrangements is that, if we can pull a box out to one such square, we can pull it out to any one, and there is a likelihood of the reversible property being maintained even when we pull out a second box. Thus, if the pulling out of the first box conflicted with the second, we could move the first box on to another "spread out" square to try to remove this conflict. And we could use the reversible property to change the order of moving up boxes; maybe to get the fourth box out we need to get the third box out, then move up the first and second, then move up the third to clear a route for the fourth. There will be an element of "follow the leader" whereby the second box follows the first around until we find an arrangement which doesn't conflict with pulling out the third box, and so on. We are aiming to locate an "easy win" whereby several boxes can be spread out without interfering with each other. Once again, we don't need to find all ways of doing this, one is "good enough".
Identifying any such "easy win" is useful even if it only applies to a limited number of boxes. To generalise, we can try pulling out our boxes, and if they are not amenable we can delete them to see if they facilitate an easy win with following boxes. This then provides motivation to try to find a way to "park" the obstructive box so as to facilitate the easy win. The idea is to divide up the boxes into groups with easy wins and obstructions. We try to solve obstruction problems with exhaustive searches (to some limit) but we severely limit search for easy wins. In some sense, we're trying to divide up the solution into "easy bits" and "hard bits" with exhaustive searches for the hard bits and heuristically limited searches for the easy bits. Progress is indicated by a successful subtask. Failure requires a reassessment of priorities in the whole search method. Having lower bounds available on the amount of free space, the number of boxes in a particular area with a reversible arrangement, etc, can help the program assign a likelihood of success to a subtask, which helps with decision-making; both with decisions whether or not to pursue a search to solve a subtask and what to do after an initial failure - if the task is low probability we might want to abandon it and try to restructure our solution without it, but if it is high probability we might try searching more deeply. The likelihood of success could then be adjusted by how much search effort has been put into it already.
Generalised deadlock detection
External corrals are usually tested for deadlock by seeing if they can be opened up (reduced to single corral) with the rest of the boxes removed. Since boxes on goals may not necessarily need to move again, the criterion is broadened to pushing out a box which is not on a goal (apologies if the science of deadlock detection is more advanced than my brief description of it here). This should work well in simple cases where boxes put on goals immediately become frozen and cannot move again. But when this is not the case, stacking order restrictions may dictate that a box put on a goal which is not frozen may only be parked there temporarily, to later move, perhaps to another goal. This is not taken into account in conventional deadlock detection since stacking order restrictions are not included. But suppose that a reverse search has uncovered stacking order restrictions and succeeded in pulling the boxes out to a single-corral, spread out position; in a search broken into chunks (so not exhaustive) it would be useful to generalise deadlocks to take into account discovered stacking order restrictions. This is done simply by testing the position for boxes on goals and comparing against the stacking order restrictions; these might take the form of putting goals into groups which are ordered, so that all the goals in one group have to be "finally stacked" (with boxes that then never move again) before the goals in the next group are then finally stacked, and so on. Thus, if the last group have not all been stacked, we regard all goals outside this group as temporary parking positions for boxes which may have to move again; thus we can generalise deadlock detection by clearing these goals from corrals being searched for deadlock (provided they are not occupied by frozen boxes, which would be regarded as a deadlock. The assumption here is that the frozen goal would have been included in the last group if meant to be finally stacked.). There may be a further generalisation of stacking order restrictions to take into account particular box groups as well as goals, when the push access restrictions are such that not all the boxes can reach all the goals at various stages of stacking; so it then might be vital not to stack a goal with a particular box as that one has to reserved since another box cannot later be used to reach another goal otherwise. I'm not sure how to include that in generalised deadlock detection, or if it needs to taken into account elsewhere in the search. Also note that, where a solved position has multiple corrals, we can run forward searches to "synchronise" with a different stacking order for each corral (when found). Linking the forward and reverse searches this way (which is effectively doing a lot of pruning in the global tree with regard to stacking moves) may substantially increase the chances of solving the puzzle, with the usual drawback of relying on heuristics that may not be effective for all puzzles. Remember the N factorial which describes the number of unordered stacking moves.
