When I had journeyed half of our life’s way,
I found myself within a shadowed forest,
for I had lost the path that does not stray.
— Dante, The Divine Comedy1
In the previous chapter we discussed how breadth-first search can be used to traverse the nodes of a graph in the order of increasing distance from a particular starting node, and how a little bit of extra bookkeeping makes it easy
to construct the shortest paths from the start to every reachable node. In this chapter, we apply these ideas to the significantly more difficult problem of finding optimal solutions in the game Sokoban.
Sokoban is a computer game invented by Hiroyuki Imabayashi and originally published in Japan in the early 1980s. The Japanese word “Soko-ban” means warehouse keeper: your job as the player is to clean up a warehouse by moving crates to a their designated
positions. Figure 8.1 shows the first level of the original game, which we will refer to as “Level 1” in the following. The worker starts in the bottom center and must move the six crates in the left part of the level to the six target
positions, or goals, shown as blue diamonds in the right part. The worker can walk up, down, left, and right, and push (but not pull!) a single crate in the direction of movement. A level is solved once every crate is on one of the goal squares.
Figure 8.1 The first level of the game Sokoban, which we will refer to as “Level 1.” The player controls the worker shown in the bottom part of the level, and the objective is to push each of the crates to one of the goals in the right room. The
Sokoban tileset that was for create the images in this chapter were designed by Kenney (https://www.kenney.nl/assets/sokoban).
For most human players Level 1 poses only a mild challenge. After a bit of trial and error, it becomes apparent that there is basically only one possible opening move: The worker must first enter to top room from the right, clear a way to the left room, and then move the first crate to the goal area,
using a path similar to the one shown in Fig. 8.2. The remaining crates can then be transferred to the goal room one by one, by first moving them to the “hallway” that leads to the goal room and then pushing them to the right. With this
strategy, Level 1 can be solved in approximately 250 steps — and with a little effort, you may even be able to find the optimal 230-step solution.
Figure 8.2 The indicated path shows the steps that are necessary to move one of the crates to the goal area.
For computers, on the other hand, playing Sokoban is a serious challenge, for two main reasons. The first is that the number of potential solutions grows very quickly with the size of the level. In each step, the worker can move in up to four different directions, so the total number of possible paths tends to
grow exponentially with the number of steps taken. This is especially problematic because even small Sokoban levels require several hundred steps to solve. For example, the shortest solution of Level 1 takes 230 steps, and generating all possible paths of length 230 is an almost
impossible undertaking. Brute force alone is no match for Sokoban.
The second difficulty is that computers have a hard time distinguishing between good moves and bad moves. As human players, we constantly devise heuristics and strategies that allow us to limit the number of moves that we need consider at each step, which lets us disregard hundreds of moves (and
consequently millions of game states) that are theoretically possible but don’t seem promising to us. Since computers lack the ability to form ad-hoc strategies, trying all possible solutions is often the best thing they can do — which leads us back to the first point.
With that being said, implementing a simple Sokoban solver is both instructive and a lot of fun — even if the resulting program is still pretty basic and struggles with the more difficult levels.
Every Sokoban level is defined on a square grid and consists of walls, goals, crates, and the current position of the worker. The walls and goals are at fixed locations, but the worker and the crates can be moved horizontally and vertically. For simplicity, we assume that every level is a rectangle of
width \(w\) and height \(h\), which can always be achieved by extending the level with empty squares. In this way we can assign every square on the board a position between \((0,0)\) for the upper-left corner and \((w-1,h-1)\) for the lower-right corner. We put all the functionality for
working with such rectangular boards in a class called Board, which is outlined in Listing 8.1.
Listing 8.1ch8 / Board
// A rectangular board of fixed size.
public class Board {
private final int width, height;
public Board(int width, int height) {
this.width = width;
this.height = height;
}
// Is the given point inside the board?
public boolean isInside(int x, int y) {
return x >= 0 && x < width && y >= 0 && y < height;
}
// The size of the board.
public int height() {return height;}
public int width() {return width;}
// ...
}
We will use two different conventions for referring to squares on the boards. The first is to use a pair of coordinates so that \((0,0)\) refers to the upper-left square and \((w-1, h-1)\) to the bottom-right square. The second is to assign each square a unique index between 0 for the top-left corner
and \(w\cdot {}h-1\) for the bottom-right corner. The main advantage of using a single index instead of a pair of coordinates is that it lets us store individual positions in variables of type int and sets of positions in bit sets. We can convert
between coordinate pairs of the form \((x,y)\) and integer indexes using the following formulas:
\(\seteqnumber{0}{8.}{0}\)
\begin{equation*}
k = y\cdot w + x,\qquad y = \lfloor k / w\rfloor ,\qquad x = k \bmod w.
\end{equation*}
The Board class provides three methods for translating between integer positions and \((x,y)\) coordinates: index() computes the index of a position
from its coordinates, whereas getX() and getY() recover the coordinates from the index
(Listing 8.2).
Listing 8.2ch8 / Board
// Convert between coordinates and indexes.
public int index(int x, int y) {
return x + y * width;
}
public int getX(int index) {
return index % width;
}
public int getY(int index) {
return index / width;
}
To represent the four main directions on a rectangular board (up, down, left, and right), we define a nested type Direction inside Board that holds the corresponding offsets in the x- and y-direction (xOff and yOff) as well as a character charCode that serves as a shorthand for a particular direction (Listing 8.3). Four directions are predefined: UP, DOWN, LEFT, and RIGHT with the corresponding character codes ‘u’, ‘d’, ‘l, and ‘r’. In addition, we
define an array ALL_DIRECTIONS that contains all four directions.
Listing 8.3ch8 / Board
public record Direction(int xOff, int yOff, char charCode) {
}
// Predefined directions.
public static final Direction
UP = new Direction(0, -1, 'u'),
DOWN = new Direction(0, 1, 'd'),
LEFT = new Direction(-1, 0, 'l'),
RIGHT = new Direction(+1, 0, 'r');
public static final Direction[]
ALL_DIRECTIONS = {UP, DOWN, LEFT, RIGHT};
If we want to move a point with coordinates \((x,y)\) in a certain Direction, we simply add xOff to \(x\) and yOff to \(y\). We can define a similar operation that works with indexes instead of coordinates. The index
of the square \((x,y)\) is \(y\cdot w+x\), so moving to the left or right corresponds to decrementing or incrementing the index by 1, and moving up or down corresponds to subtracting or adding the level’s width. The moveIndex() method in Listing 8.4 implements this operation; it returns \(-1\) if the index cannot moved in the desired direction.
Listing 8.4ch8 / Board
// Move an index in the given direction.
public int moveIndex(int index, Direction dir) {
return isInside(getX(index) + dir.xOff(), getY(index) + dir.yOff())
? index + dir.xOff() + width * dir.yOff()
: -1;
}
// Return the direction that moves oldIndex to newIndex.
public Direction getDirection(int oldIndex, int newIndex) {
if (newIndex == oldIndex - width)
return UP;
if (newIndex == oldIndex + width)
return DOWN;
if (newIndex == oldIndex - 1)
return LEFT;
if (newIndex == oldIndex + 1)
return RIGHT;
return null;
}
A related method called getDirection() is defined in the same listing. It’s the inverse of moveIndex() in that it takes two adjacent positions on the board and computes the direction that takes us from the first to the second index. If oldIndex and newIndex aren’t adjacent, the method
returns null.
Storing Levels
Sokoban levels are conventionally specified using a text-based format in which each row of the level is encoded as a string of characters. For instance, Level 1 is represented as shown in the left part of Fig. 8.3. The space
character “␣” denotes an empty square, “#” a wall, “$” a crate, “.” a goal, and “@” is the worker’s initial position. Two additional characters, “+”
and “*”, are used in levels where either the worker or one of the crates starts on top of a goal square. The full list of characters and their interpretation is summarized in the right part of Fig. 8.3. We
will use this encoding for reading levels and printing them to the screen (Exercises 8.1 and 8.2 and ).
Since solving a Sokoban level typically involves generating and evaluating a large number of game states, we will use a more efficient internal representation for levels that is similar to the bitboards we used in our discussion of peg solitaire in Chapter 6. The main idea is to store the level as three sets of integers: one set each for the walls, the goals, and the crates. Since every position is a small integer between 0 and \(w\cdot {}h\), we can represent each of these sets as an array of \(w\cdot {}h\)
bits. For instance, the following small level
is represented using three bit sets of size \(6\times 4\):
The walls and goals are fixed, so the first two sets are constant, but the set of crates must be updated continuously as the game progresses. The position of the worker is stored separately.
Listing 8.5 shows the outline of a class called Level that we will use to represent Sokoban levels of a given width and height. (The BitSet class we use
to represent bit sets is described in Exercise 5.16.) Initially, the bit sets walls, goals, crates are empty and the worker’s starting position workerStart is set
to an invalid value. The constructor of Level takes the desired width and height as arguments and uses them to initialize the underlying Board.
Listing 8.5ch8 / Level
// Representation of Sokoban levels.
public class Level extends Board {
private final BitSet walls = new BitSet();
private final BitSet goals = new BitSet();
private final BitSet crates = new BitSet();
private int workerStart = -1;
private Level(int width, int height) {super(width, height);}
public BitSet walls() {return walls;}
public BitSet goals() {return goals;}
public BitSet crates() {return crates;}
public int workerStart() {return workerStart;}
// ...
}
To populate the level with objects, we define a method setCode() that takes one of the characters codes defined in Fig. 8.3
and updates the fields of Level accordingly (Listing 8.6). Notice that changing a single square may require changes to all three bit setsandworkerStart. To keep the number of special cases we have to consider to a minimum, we first clear all information associated with the square and then update the fields that are affected by the new character code. For instance, if charCode is ‘#’ we add a wall, and if it is ‘*’ we add both a goal and a crate.
Listing 8.6ch8 / Level
public void setCode(int x, int y, Character charCode) {
int index = index(x, y);
walls.remove(index);
goals.remove(index);
crates.remove(index);
if (workerStart == index)
workerStart = -1;
switch (charCode) {
case ' ' -> {}
case '@' -> workerStart = index;
case '#' -> walls.add(index);
case '.' -> goals.add(index);
case '$' -> crates.add(index);
case '+' -> {
workerStart = index;
goals.add(index);
}
case '*' -> {
crates.add(index);
goals.add(index);
}
default -> throw new IllegalArgumentException(
"Invalid character: " + charCode);
}
}
Exercise 8.1. Consider the text-based encoding of Sokoban levels described in Fig. 8.3. Implement a function Level.parse() that creates a new instance of Level from a list
of Strings in this format.