Peg solitaireis a well-known board game with a long history. Today, the most common version of the game is played on a board with 33 holes that are arranged in cross-like shape as shown in
Fig. 6.1. At the start of the game, every hole except for the one in the center contains a marble or a wooden peg, and the goal is to find a sequence moves that inverts the board so that only a single peg in the center remains.
Figure 6.1 Peg solitaire. The goal is to remove all pegs from the board so that only the one in the center remains.
The only allowed move in peg solitaire is to jump one of the pegs over an adjacent peg into a hole. The peg that was jumped over is removed from the board and creates a new hole, so each move transforms a vertical or horizontal arrangement of the form “XXO” (two pegs
and one hole) into “OOX” (two holes and one peg). Since each jump removes one peg, every valid solution requires exactly 31 jumps. The question is: Are there any solutions? If yes, how many? And how do we find them?
Let’s start with a simple problem: How do we store the state of the game? One solution is to enumerate the board as shown in Fig. 6.2 and represent the positions of pegs or holes as sets of integers. For example, the set of all
valid positions on the board can be represented by the following set:
In the starting configuration, there is a peg in every hole except the one in the center, so the corresponding set consists of all valid positions except the 24th:
Likewise, the final state of the game has a single peg in the center and therefore has the set representation \(\{ 24 \}\). At the start of the game, the only possible move is to jump to the empty hole in the center, and the only four pegs that can jump there are the ones at positions 10, 22, 26, and 38; the set
of pegs that can be moved can be written as \(\{ 10, 22, 26, 38 \}\).
Figure 6.2 Numbering scheme for pegs. To simplify index computations, the 16 positions in the corners are also enumerated.
One advantage of this representation is that every such set can be stored very compactly a sequence of 49 bits in which the \(k\)th bit indicates whether there is a peg at position \(k\). (Of course, set of holes can be represented in the same way.) The term bitboard is often used for the resulting data structure. We collect a few basic functions for working with these bitboards in a class called PegBoard, which is outlined in Listing 6.1. We start by defining three constants: FULL_BOARD is the set of all valid positions on the board, INIT_PEGS is the initial configuration of pegs, and FINAL_PEGS is the desired final configuration of pegs.
Listing 6.1ch6 / PegBoard
public class PegBoard {
public static long FULL_BOARD = Bits.range(2, 5) | Bits.range(9, 12)
| Bits.range(14, 35) | Bits.range(37, 40) | Bits.range(44, 47);
public static long INIT_PEGS = FULL_BOARD & ~Bits.bit(24);
public static long FINAL_PEGS = Bits.bit(24);
// ...
}
How can we perform a single jump in this representation? Assume we are given the current position of all pegs as a bit set board and two integers peg and hole that indicate which peg to move into which hole. With our numbering scheme, we can compute the index
mid of the peg that is jumped over by averaging peg and hole. The resulting board is obtained by removing the two pegs at peg and mid and adding a new peg at hole; alternatively, we can flip the corresponding three bits using
a single exclusive OR operation, as shown in Listing 6.2.
Listing 6.2ch6 / PegBoard
public static long jump(long board, int peg, int hole) {
int mid = (peg + hole) / 2;
return board ^ Bits.bits(peg, mid, hole);
}
We now come to the main advantage of using bit sets to store sets of board positions, namely the ability to use bit operations to modify all set elements at once. Consider the problem of moving individual pegs or groups of pegs. We can move a single peg to the right or left by adding \(\pm 1\) to its index
and up or down by adding \(\pm 7\). If the positions of multiple pegs are stored in a bitboard, we can move them all at once by shifting the bit pattern by \(\pm 1\) or \(\pm 7\) places!
This trick works for most but not all positions on the board. For example, if you try to move the peg at position 21 to the left by subtracting 1, you end up with position 20 on the opposite side of the board. In general, we have to be careful with positions on the boundary of the board.
Fortunately, bitboards give us an easy way to handle this special case as well: All we have to do is remove the problematic positions before performing the bit shift. For example, we can safely move a bitboard to the left if we first remove the positions on the left boundary,
which can be done by subtracting the set \(\{2, 9, 14, 21, 28, 37, 44\}\). The left() function in Listing 6.3 implements
this operation, using the expression board & ~BOUNDARY_LEFT to compute the set difference of board and BOUNDARY_LEFT. If p is a set of positions on the board, left(p) is the set of positions to the left of p and left(left(p)) the set of positions two steps left of p.
In a similar manner, we can define functions right(), up() and down() that move game boards in the other three directions. For the implementation of right(),
we replace the right shift with a left shift and remove bits on the opposite boundary. Moving the board up and down can be accomplished by shifting the bitboard 7 places to the left or right. In this case, it isn’t possible for bits to wrap around to the opposite side of the
board, so can simply remove invalid positions from the bitboard after shifting the bits.
We can use these four functions to define more advanced operations on bitboards. For instance, given a set of positions, the set of all neighboring positions on the board is the union of positions obtained by moving in the four possible directions:
If positions contains just a single bit, neighbors() computes its direct neighbors:
But if multiple bits are set, it returns the union of all direct neighbors:
That’s the main benefit of bitboards: They make it possible to express many computations involving sets of positions using just a handful of bit operations.
Computing Possible Moves
We can also use bitboards to quickly compute the set of pegs that are currently movable, that is, the set of pegs that are two places away from a hole with another peg between them. Let’s start with a single direction first: Given a set pegs that contains all pegs that are currently on the board,
which subset of these pegs can jump to the left?
First we compute the subset of pegs that have another peg to their left. This is obviously the same as the subset of pegs that are to the right of another peg, which we can compute by moving all pegs to the right and computing the intersection with the original pegs:
It’s helpful to mentally translate expressions of the form pegs & X into “pegs that have some property X.” Here, the mental translation is “pegs that are to the right of another peg.”
We can use the same idea to compute the set of pegs that are to the right of a hole. The set of holes can be computed by subtracting pegs from FULL_BOARD, which effectively inverts the current board:
By combining the two expressions we obtain the set of pegs that are to the right of a peg that is to the right of a hole — in other words, the set of pegs that can jump to the left.
In the same way, we can compute the sets of pegs that can jump in any of the three other directions, and the union of these four sets gives us the set of all pegs that can be moved:
This expression can be simplified further by “factoring out” the common term “pegs &”. This is possible because the bit operators ‘|’ and ‘&’ satisfy distributive laws similar to those of addition and multiplication; see Exercise 6.2. This gives us the final expression for the subset of movable pegs:
Another problem can be solved in almost the same way: Given a single peg on the board, how can we determine where it can jump to? To test whether the peg can jump in a particular direction, we simply check whether there is first another peg and then a hole in that direction. Repeat this for all four
directions and you have the list of possible moves. Alternatively, we can again use bit operations to determine all possible destinations in one go. If position is a bit set that contains just the peg we are interested in, we can compute the set of reachable holes using an
expression that is almost identical to the one we used to compute the set of movable pegs:
This expression moves position in all four directions, keeping only those positions that have another peg at distance 1 and a hole at distance 2. The result is a bit set containing all holes that are reachable from position. (If position doesn’t contain a single peg but an arbitrary subset of pegs, the expression returns the union of all reachable holes.)
As you can see, the bit expressions for movablePegs and reachableHoles are almost identical, so we factor out the common part that computes the reachable positions that are one jump away, which gives us the function reachablePositions() shown in Listing 6.4. Using this function, we can then easily compute the set of pegs that are currently
movable and the holes that are reachable from a set of positions. The set of movable pegs is simply the subset of pegs that are one jump away from a hole (movablePegs()), and the set of reachable
holes is the subset of holes that are one jump away from the positions of interest (reachableHoles()).
Listing 6.4ch6 / PegBoard
// Compute all positions that can be reached from the positions
// in 'start' by jumping over an adjacent peg.
static long reachablePositions(long pegs, long start) {
return down(pegs & down(start))
| up(pegs & up(start))
| right(pegs & right(start))
| left(pegs & left(start));
}
// Compute the subset of 'pegs' that are movable.
public static long movablePegs(long pegs) {
long holes = FULL_BOARD & ~pegs;
return pegs & reachablePositions(pegs, holes);
}
// Compute the set of holes that can be reached from the pegs in 'start'.
public static long reachableHoles(long pegs, long start) {
long holes = FULL_BOARD & ~pegs;
return holes & reachablePositions(pegs, start);
}
Figure 6.3 An intermediate game state in peg solitaire.
Using these two functions, we can now analyze a given game state and determine all possible moves. For example, consider the game state shown in Fig. 6.3. To compute the possible moves for this state, we first call movablePegs() to obtain the positions of all pegs for which any move exists, and then use reachableHoles() to determine the eligible target positions for each of them:
The first number in each row is the position of a movable peg, and the list of numbers in square brackets are the holes this peg can reach in a single jump. For example, the pegs at positions 20 and 32 can both jump to the holes at positions 18 and 34, whereas only a single move is
available for the pegs at positions 9 and 16.
Exercises
Exercise 6.1.What does the following expression compute, when board is a bit set of peg positions?
reachableHoles(board, movablePegs(board))
\(\star \) Exercise 6.2. Prove the following distributive laws that hold for arbitrary bit patterns \(A\), \(B\), and \(C\):
Exercise 6.3. The following image shows a variation of peg solitaire that is played on a triangular board:
As before, pegs are removed by jumping over adjacent pegs, but now there are six directions of movement.
a) Find a solution to the board shown above.
b) Explain how to store this board using bits and how to compute all legal jumps.
Exercise 6.4.Connect 4 is a two-player game that is played on an upright board that consists of 7 columns and 6 rows. Both players
start with 21 tokens of a certain color, say white for the first player and black for the second, and take turns dropping tokens into the columns of the board. The first player to complete a vertical, horizontal, or diagonal line of four tokens wins the game. Figure 6.4 shows a game state in which the white player has won after eight moves.
Explain how to represent the game state using bitboards and how to quickly determine whether there are four identically colored tokens in a line somewhere on the board.
Figure 6.4 A game state of Connect 4. The white player has just won by completing a diagonal line of four tokens.
