From Sokoban Wiki

Current revision as of 20:17, 9 November 2015

Section 1. Ideas

The kind of solution

Here I am only concerned with solving a Sokoban puzzle via computer in any number of moves and pushes, not with optimising the solution (which can in any case be applied using an optimiser once a solution has been obtained). For simplicity, I neglect the number of "man" (or "pusher" for forward and "puller" for reverse) moves used, only considering the pushes of boxes, so I only care about the empty squares accessible to the man, rather than the particular squares he moves from in between pushing boxes. I also don't too much care about how many pushes are used in a solution: the greater concern is restricting the search tree by domain-specific knowledge so that a solution can be found at all in a reasonable amount of time and memory. This presents a departure from standard search techniques using an estimate of the number of pushes left to solve the puzzle. I prefer to break down the problem of solving a Sokoban puzzle into manageable "chunks" (subtasks): I would then only care about the total number of positions (pushes plus man access information) in the search tree for the individual chunk, plus of course the total number of chunks. Where possible it would be nice to be able to pre-assign the number of chunks to break the solution into before starting the search for individual chunks (which can be done to an extent with stacking ordering as we will see in the next three sections) so I can be aware of how many chunks I'm using; but in practice the chunks will have to be dynamically assigned as the search progresses. Thus, the search for a solution would fail if the tree for an individual chunk became too large or there were too many chunks (so the aggregate total of trees for all the chunks exceeded some limit) or too much time was used in the search. In a nutshell, I'm interested in restricted search, planning and heuristics.

Corral

A boxed-in area. There is always one corral or area containing the man, (the "man's corral", which may only be boxed in by walls) but there may be other corrals the man is outside (known as "external corrals").

Man access, push squares and push access

The man can move (without pushing boxes) to any empty square connected through adjacent squares horizontally or vertically (but not diagonally), which defines the "man access" within the man's corral. Conversely, if the man is just pushing a single box, there may be many similarly connected empty squares (with the direction of the push also included, so that the same square can occur more than once with the man pushing in different directions non-trivially if at some point in the box's journey it is on the boundary of an external corral). This collection of squares combined with push directions constitutes the "push access" for that box (the algorithm to compute it for a given push square (see below) of the box is well-known and I won't describe it here). But, it may well be that not all the man access squares even within the man's corral constitute positions the box can reach with the man pushing only that one box; walls or other boxes may get in the way, and prevent a push (either by physically blocking it or if the push leads to deadlock, see below) or require a change of direction, and due to external corrals the man may not have access when a change of direction is required. As a familiar example, if two rooms are joined by a bent tunnel one square wide, the man may travel along it but the box cannot get past one of the corners. As another example, in a square room with only one exit three squares wide at the exit, a box in the room on the wall near the exit can't be pushed inside the room by the man to the centre of the room; it first has to be pushed out of the room, and only if the man has access can it then be returned to the room where it can be pushed to the centre. Pushing the box inside the room to the exit creates a new external corral.

The four squares adjacent to a box horizontally or vertically are called the "push squares" of that box. If empty and accessible by the man, and if the opposite corresponding square is also empty, the box can of course be pushed away from the "push square" in a well-defined direction, hence the terminology. Of course, there is no guarantee that doing so would be a useful move. It might lead to an insoluble position, as in the next definition.

Deadlock

A position whereby some box can never reach a goal or some goal can not be reached by a box (or more generally from which it is impossible to solve the puzzle) is known as a deadlock. The simplest deadlocks are created by pushing a box onto a "dead" square, one from which it cannot be pushed to any goal (a precise definition and algorithm is given in Section 3). For example, the corner square of a room if it does not contain a goal is a dead square. Another simple example is where a box is pushed along a wall until it rests against another box on the same wall (with at least one of the boxes not on a goal). The two boxes are then "frozen" in that they can never be pushed anywhere else. The position is a deadlock since at least one of the two boxes is not on a goal and is frozen, so the puzzle cannot be solved. There are many generalisations of these examples; some corral deadlocks can be detected by a computer if an external corral is created in which an exhaustive search of the bounding boxes is unable to open up the corral (giving access to push those boxes in the corral which are not on goals). Whatever set of deadlock positions the computer program can detect are termed the "detectable deadlocks".

Open and boundary boxes

I propose an artificial subdivision of all the boxes within a given corral into those on the boundary, which have an empty push square not belonging to the given corral, and those in the open, which are the remainder. I envisage subtasks in which exhaustive search is performed on the boundary boxes but limited ("good enough") searches are performed on the open boxes. This may implicitly restrict the program to solving puzzles in which the subtasks can be subdivided in this way. There may also be ways of getting around this rigid subdivision using various heuristics, not to be described in this section. The definition may also need to be refined to take account of boxes adjacent to those on the boundary; are these to be considered boundary or open boxes, or a further category (for the purposes of the computer search)? This is similar to the situation in which restricted areas of the position, namely external corrals, are searched to check for detectable deadlocks in existing programs.

Stacking

Placing a box onto a goal is known as "stacking" the box, or just "stacking". This terminology is appropriate when the man is thought of as a warehouse-keeper moving crates around a warehouse to their correct destinations.

A "stacking move" for a box is a sequence of pushes of the same box which leads to that box being stacked (on a goal).

Free space

Intuitively, "free space" is empty squares that could be used to contain boxes but aren't being used at the moment. An experienced human solver immediately notes where corrals contain free space, and keeps it in mind when trying to solve some task which runs into trouble with deadlocks: maybe rearranging a few boxes first using the free space to pack them more tightly (but safely, without a deadlock) in one area will free up space elsewhere so that the original task (such as stacking a box, combining adjacent corrals or moving through a one-way system) can be achieved without deadlock.

Algorithmically, within each corral the empty squares that are not "dead" can be looped through, with an extra box being added (and then removed). If adding the box does not increase the total number of corrals, nor create a suitably restricted notion of detectable deadlock, (one not concerned with the fact that we now have more boxes than goals!) that is designated as a free square. It is then straightforward to decide whether or not a corral contains at least one free space. One can generalise by iterating the process once one free square is identified: however of course this would give only a lower bound on the free space assuming that an exhaustive search is not attempted. It is envisioned that exhaustive searches of the number of free squares to any depth in any corral are not attempted, due to time and memory overheads. It is heuristically more important to give a lower bound, obtained with a particular set of squares, perhaps chosen by some heuristic function not described in this section, than to attempt exhaustive search to get a precise limit and ideal arrangement. Obviously, this will depend on the overall size of the empty space within the corral; for particularly small corrals an exhaustive search may be used. The reason that mere lower bounds can be useful is that one can formulate subtasks (such as moving a boundary box onto a free space square) where it may not signify which particular square is used (or more precisely, there are perhaps several squares which could be used to similar effect, and it is "good enough" to find one of them). The general idea is that for some tasks it is "good enough" to find a particular solution, rather than all solutions. In practice, one may be limiting solving ability of the computer program to those problems where "good enough" solutions can be found for the subtasks.

In particular, in a corral with at least one free space square, one subtask could be to make your way to the neighbouring corral and push a boundary box onto a free space square, thereby combining two corrals into one corral and in principle simplifying the position. Any of the squares identified as free space for adding a single box will be good enough for this task (potentially; in practice some may lead to subtle deadlocks). The idea of making your way to a different corral than the man's brings up the next definition.

Navigable position

The simplest example of a navigable position is one where the man has access to all empty squares, so there are no corrals the man is outside. We say the position has only one corral (the man's). In principle the man can then move all the boxes which aren't frozen on goals. In practice, the man may need to move some other boxes out of the way first if they are blocking pushes of boxes, and some box pushes may of course be forbidden as they lead to (detectable) deadlocks, or worse, lead to currently undetected deadlocks.

The more significant generalisation of this is to positions with multiple corrals. To be navigable, a position must come with variations ("navigation variations") allowing the man to traverse around all of the corrals. In a simple puzzle, it might be possible to combine the man's corral with a neighbouring corral by moving some boxes, and iterate the process until only the man's corral is left and we are reduced to the simplest case of a navigable position. Naturally it is only useful to do this without creating a deadlock. One always has to bear in mind that deadlocks could arise that are undetectable by the program at the time (though which might be detected at a later stage). Some consideration should be given to backtracking when such belated deadlocks are detected, but I'm not addressing that problem in this section.

The next simplest case of a navigable position would be where the variations to traverse the corrals utilise "one-way systems", whereby the man opens up a corral by moving a box, or more generally several boxes, moves through to the new area opened up, possibly closing up access to some part of the original corral, and repeats the process of travelling successively through several adjacent corrals, until finally the man returns to the original corral. Ideally, a one-way system would return all the boxes to their original positions and move only one boundary box to traverse from one corral to the next (opening then closing the "doors") at each stage, so that the effect is that of the man "jumping" over boxes into neighbouring corrals in a loop. The more difficult and particularly the remaining unsolved XSokoban puzzles tend to use these kinds of one-way systems, which in combination with "free space" (see below) are a significant factor in increasing the size of the global search tree and introducing many subtle deadlocks with a conventional search.

Having a lot of free space without multiple corrals may lead to a very easy puzzle (though not necessarily if the rooms are carefully designed) but having a lot of free space with multiple one-way systems can actually lead to a difficult puzzle (in terms of computer solving at least) because the access problems created by the one-way systems along with the capacity to rearrange boxes in many arrangements in the free space, some of which may generate subtle undetectable deadlocks, means that there can be multiple solutions, which creates a problem for an exhaustive search, but also enormous areas of the tree with positions with similar features which may contain a subtle deadlock. In practice, as an experienced (human!) solver I would say that having several one-way systems, combined with numerous box-moving restrictions such as room entrances along a wall which don't allow push access of boxes to the whole room, and bent tunnels which only allow man access without allowing boxes push access, but allowing a certain amount of free space, can force a solution where several boxes may have to be painstakingly moved through many rooms a little at a time, all the time requiring one-way-systems to be navigated and access problems to be negotiated. In combination with free space and clever design, it may be required to shift several boxes from one room to another, in one arrangement, and then back again or to another room in another arrangement, before the stacking order requirements of the solution can be satisfied. Though the solution may not be unique, even an optimal solution may require a lot of this lengthy rearranging in stages, and the solutions may be well hidden in a forest of near-misses with subtle deadlocks. To my mind such problems almost demand a more sophisticated computer search where the problem is broken into manageable "chunks".

The basic plan of the unconventional search method proposed here is to trawl the global search for variations moving the man around one-way systems; this then allows a kind of pruning, by restricting the search to navigable positions. One can of course further break down the search for navigation variations to those allowing the man to traverse through neighbouring corrals. The intention is to split up the global search, whose tree may be very large, into a number of smaller more manageable searches for navigation variations, each of which may have a smaller tree. In more detail, exhaustive searches moving boxes on the boundaries of corrals may be combined with more limited (not exhaustive) searches moving boxes into free space. There may be many ways to pack boxes into free space to free up boxes elsewhere; it is not necessary to find all of them, only one that is "good enough" in that it creates no currently-detectable deadlock and solves the subtask required. The exhaustive global search is to be replaced with a number of more limited searches, some exhaustive but limited to boundary boxes and others limited (not exhaustive) and applying to (mainly) the man's corral open boxes.

Access circuits

Strictly speaking, there may be a simpler navigable position than the general one with only one corral. An arrangement of boxes and walls may be disconnected from the outside walls, allowing the man to roam all around its perimeter. Such an arrangement is an "(access) circuit"; the number of separate circuits is a topological invariant of a position (in particular, it is uniquely defined however and in whatever order you choose to count them). A circuit can of course also appear as part of a position with more than one corral. Circuits are particularly helpful for solving, in that a box can be temporarily stored at any reachable position on the boundary whilst not increasing the total number of corrals (though perhaps decreasing the number of circuits by one or more). Another advantage of circuits is that (speaking roughly) the man can push a box around near the circuit, and every time he has to change direction the circuit provides automatic access to the new push square, so it becomes relatively easy to store a box at almost any position on the boundary of the circuit. In other areas of the puzzle, without circuits or with multiple corrals, loss of access may occur when the direction to push the box in changes. Thus, it can be helpful to use a circuit to store a box that is blocking some other part of the puzzle, to help increase the amount of access at box changes of direction in a part of the puzzle with more limited access. This is another case where "good enough" variations may be found without searching through all possible variations. Naturally, having enough free space to generate a circuit can lead to a large conventional search tree, but in combination with multiple corrals, one-way-systems and clever room design can still lead to very difficult puzzles for a conventional computer search. A precise definition of circuits and an algorithm to compute them is given in Section 3.

Shuffling

This is a generalisation of a "stacking move" to navigable positions. It also generalises stacking by not necessarily putting a box on a goal, merely onto a square previously identified as helpful (such as matching a reverse search position, or a free space square).

If you can't actually put a box on a goal just moving that one box, (i.e. the goal is not in the push access of the box) then maybe you can utilise the navigability variations to move the box part way to the goal. For example, select a goal which is not covered by a box. Since the position is navigable, there is a variation moving the man to at least one corral neighbouring the corral containing this goal, and a variation where the man opens up the goal corral. One might try simply pushing a boundary box onto the goal once we reach the previous corral, which is the simplest generalisation of a stacking move.

However that might create a (potential or detectable) deadlock by messing up navigability, or simply be impossible as there is no stacking move available. Instead we use the directionality of the navigation variations: move the man into the goal corral, then push a (preferably open) box in the goal corral (if necessary) to clear up a space for the boundary box we want to stack. We then traverse the one-way system as before, pushing open boxes back into the space freed up by the last box moved, until we arrive in the corral containing the box we want to stack. Now there is a space for it to be moved into the goal corral freed up by the first box moved, without messing up the navigability (since we restricted ourselves to open boxes). It's a kind of game of musical chairs. Essentially you are vacating space by moving boxes "backwards" around the one-way system as you move, which still allows you to move the man forwards around the system. You can compare this with the procedure in a block-shifting puzzle like the 15 puzzle, whereby many blocks are moved to transfer the single empty square around the puzzle to where it is needed. It may take several stages for a box to reach a goal this way. I'm trying to give a common theme but in general the details of shuffling may be complex and require breaking into several subtasks.

This procedure may also be used when there is no one-way system, merely a corral access or circuit, where the variations necessary will generally be much simpler than in the situation with a one-way-system (where shuffling subtasks are by no means guaranteed to be possible). This is the original situation where the "shuffling" concept came into my mind. Even then there may be some restrictions, and if there is enough space to create more than one circuit that could make the shuffling process even simpler; as more access is granted, the position moves in the direction of one ideal for shuffling, whereby each shuffling move of a box can be achieved by pushing that single box alone. In the context of stacking boxes, this corresponds to the simplest possible type of puzzle whereby the puzzle can be solved with consecutive stacking moves. A very simple, fast shuffling algorithm (for single corral access and involving only single-box routes between fixed squares) is given in Section 3.

Shuffling (in the simpler case where stacking boxes is involved) is a technique for converting a navigable position into another navigable position with one more box on a goal (stacked). In a real sense you don't need a pre-computed goal area stacking order; you just look for shuffling variations which stack one box at a time (or in fact move a box a bit closer to being stacked in general). If you find that some previous stacking produces a deadlock, where some box can now not be stacked on any goal from its current position, this means backtracking and adding an order-related subtask for the box: it has to get moved from its current position to one where it will be able to stack somewhere after the stacking moves that produced the previous deadlock are performed. Example: a box on a wall near an entrance to a goal area which is man access only, the box can't be pushed in. To remove the box from the wall (due to the pattern of the rooms) the man has to use the goal area access, but the deadlock arises when boxes are stacked which block off this access. The solution is to move the box off the wall using the goal area access before blocking the access with stacking moves.

Obviously this approach can run into trouble with a proliferation of subtasks, especially if a lot of backtracking is necessary. Heuristics probably need to be used relating to when we give up trying to execute subtasks which are running into difficulty with a given position, and when we return to the global search to look for a "better" position. But in general, this idea that it doesn't much matter which box you stack so long as the position remains navigable is powerful, as it allows a "good enough" criterion. If, having tried to stack one box by shuffling all of the boundary boxes (or enough to be successful) you manage to stack one, that is "good enough" for it to be worthwhile sticking with this variation. Note that one would probably first try to stack the open boxes in each corral which contains goals, which would itself potentially free up space to stack boundary boxes or merge corrals. There is still the basic difficulty of an n factorial, where n is the number of goals, number of potential ways of stacking boxes, for each navigable position, so it would be helpful to try to apply goal area stacking algorithms, and generalisations to intermediate positions, to reduce this number, all the same!

Reverse search

The aim of a reverse search in this approach is to re-distribute the boxes, from a given solved position with the man in some corral, into a navigable position with the boxes "near" to a navigable position identified by the forward search (the current best candidate in terms of having stacked as many boxes safely as we can manage and avoided any stacking-order problems identified in the search). This involves identification of free space. Within each corral, we identify free space, trying to match up the number of forward box positions within each room which intersects with the corral. Since this process is not exhaustive, merely "good enough", the match may only be approximate rather than exact. We may have too few boxes in one room and too many in another, and the forward and reverse box positions may not match within a room. Since we can assign statistics of how many boxes are in the solved position in each room, we can simply note whether there is any improvement in matching up the numbers and positions (possibly with an ordering in which the number is most important, that would depend on the heuristic and algorithm details chosen). We can probably usefully subdivide the reverse search into a subtask searching for a navigable position, with the same or fewer corrals than the best position in the forward search, and then one trying to match up with the forward search.

Also note that we would have to keep track of information about the number of boxes frozen on goals in the forward search which limits which boxes may be moved in the reverse search.

The idea is, if there is improvement in the matching, the reverse variation leading to that situation is "good enough". We can then follow up with further subtasks, trying to redistribute the boxes so that more are stacked (by shuffling or open box stacking) and so that more are re-distributed (by shuffling) between rooms to match numbers and positions. One could assume these subtasks are applied to the forward search, since it is equivalent to try to match the forward search with the reverse search or vice versa. This potentially leads to a great improvement in terms of the size of the search tree with a conventional search which just explores the forward and reverse trees as far as it can, hoping for an exact match between the two. The latter is an all-or-nothing approach, you either solve it or you don't, whereas this approach is more incremental: the search can post forward and reverse positions and navigation variations and indicate how much progress has been made towards a solution. This also suggests the possibility of applying different heuristics to try to make as much progress as possible for a given puzzle wherever it is easiest to do so. A simple, fast algorithm to spread out boxes in accessible positions from a solved position is given in Section 3.

Disclaimer

I am not suggesting that this approach can solve arbitrarily large and complex Sokoban puzzles (which is probably impossible in general as Sokoban is PSPACE-complete); merely that it has the potential to vastly reduce the size of the total search tree in some medium and large puzzles, demonstrate (potentially!) meaningful progress towards a solution in a puzzle, and lead hopefully to complete solutions for all the XSokoban puzzles and many more.