Implementation of a Simple Checkers Game Study Tool

Checkers is a game that is easy to learn but hard to master. It requires hours of concentrated study. There are some free Checkers software available on the Web. However, it seems to us that none of them allows easy study of arbitrary game positions, such as the Famous Positions from the U.S. Checkers Federation. In this article, we describe how to design and implement a text-based checkers study program. Most of the time we just follow our intuition with simpleness and correctness in mind. We will see how much intuition can guide us throughout the process. Efficiency is not a goal because the program is used for solitary study only. However, please do contact us if you find a much simpler way to implement the program. We use Perl as the implementation language because it is very easy to construct multi-level data structures with Perl.

Since the program is simple, we don't use any object orientation techniques. However, we don't exclude the possibility of moving to OO style when it helps to manage the complexity should we have more complex requirements.

Before writing any functions, let's briefly describe the notations used in Checkers. The pieces are put in the black squares and the black ones are at the lower three rows and the white ones upper three rows. The positions are numbered from 1 to 32, left to right, top to bottom. So in the beginning, white pieces occupy positions 1-12 and black ones 21-32. We also number the columns 1-8 from left to right and rows 1-8 from top to bottom and use the (row, column) notation as an alternative way to record a piece's location. For example, black piece 9 can be recorded as (3, 2) alternatively.

In the beginning, all the pieces in one side can only move toward the other side. They cannot move backward. However, once they reach the end of the other side, they are promoted to kings and can move both forward and backward.

Since this is a text-based program, we use x to denote an ordinary black piece and X a black king. Similarly, o denotes an ordinary white piece and O a white king. We also use - to denote that a position is empty. So in the beginning, the board looks like this:

   1 2 3 4 5 6 7 8
 1   o   o   o   o  (1-4)
 2 o   o   o   o    (5-8)
 3   o   o   o   o  (9-12)
 4 -   -   -   -    (13-16)
 5   -   -   -   -  (17-20)
 6 x   x   x   x    (21-24)
 7   x   x   x   x  (25-28)
 8 x   x   x   x    (29-32)

Board representation

At this time, we only consider 8x8 board size. However, it can be extended to other sizes as well. We use hash reference variable $board to store all the information about a board:

$board->{size}: Size of the board. Default is $BOARD_SIZE whose value is 8.
$board->{pieces}: This is a reference to an array that records for a position (numbered from 1 to $BOARD_SIZE*$BOARD_SIZE/2) where there is any piece on it. It can take one of the following values: $NO_PIECE, $BLACK_NORMAL, $BLACK_KING, $WHITE_NORMAL and $WHITE_KING.

That's all the information we want to track for a board so far. Accordingly we can define the following functions that manipulate a board.

init_board: This function accepts a size parameter and initialize the board with white pieces on the top and black ones on the bottom.
empty_board: This function accepts a board parameter and empties the board so there is no piece left. This function is useful when you want to start with an empty board and position pieces one by one.
print_board: This function accepts a board parameter and prints the board. You need this function to see what the board looks like after one move. This function also needs two helper functions which do the conversion between piece number (1-32) and piece position in row and column pairs, e.g. (1, 2) and (8, 7). The two functions are named get_piece_number_from_row_col and get_row_col_from_piece_number.
init_board_with_file: This function accepts two parameters: One is the size of a board, the other is the filename which records locations of all the pieces. Although there are standard formats out there, such as the Portable Draughts Notation, for simplicity we just invent a new format as follows:
```
W: 3, 32k
B: 18k, 19k
```
This states that there is a normal white piece at position 3, white king at 32, two black kings at 18 and 19. The board looks like this:
```
    1 2 3 4 5 6 7 8
1     -   -   o   -    4
2   -   -   -   -      8
3     -   -   -   -    12
4   -   -   -   -      16
5     -   X   X   -    20
6   -   -   -   -      24
7     -   -   -   -    28
8   -   -   -   O      32
```
save_board_to_file: This function accepts two parameters: One is a board, the other is a filename. It then writes information about the board to the file using the simple notation we used above. This is useful when we need to record a board's position for later study.
copy_board: This function accepts a board parameter and returns a copy of it. This is useful when we need to evaluate what the board looks like after a move. This will become clearer when we implement the moves.

Now we are ready to implement moves/jumps. There are two types of moves in Checkers. One is normal move that doesn't involve capturing any piece of the opposite color. The other is jump that captures at least one piece of the opposite color. We use normal move and jump to different the two cases. When we state "move," it means either type. There are two things we need to note.

One is that before a piece becomes a king, it cannot move backward. Second, once a piece becomes a king, the move stops. Here we use the variant from the U.S. Checkers Federation.

Similar to board, We use hash reference variable $move to store all the information about a move:

$move->{type}: This can be $NORMAL_MOVE or $NORMAL_JUMP. The former doesn't capture any piece of the opposite color while the latter does.
$move->{start}, $move->{end}: These record the starting and ending positions of the piece that moves.
$move->{steps}: This is a reference to any array that lists all the intermediate steps, excluding the starting and ending positions. For normal moves, the array is empty. For jumps, it includes captured pieces too.
In the following illustration, the black piece 23 can jump to position 7. So the steps variable for this jump is [19, 16, 11].
```
   1 2 3 4 5 6 7 8
 1   -   -   -   -  (1-4)
 2 -   -   -   -    (5-8)
 3   o   -   o   -  (9-12)
 4 -   -   -   -    (13-16)
 5   -   o   o   -  (17-20)
 6 -   -   x   -    (21-24)
 7   -   -   -   -  (25-28)
 8 -   -   -   -    (29-32)
```
$move->{board}: This records what the board looks like after the current move.
$move->{final}: If this exists and is 1, then it means this is final and there is no more move or jump from here. The reason is that the piece has reached the opposite end and is crowned.

Knowing the $move structure, we can describe some functions that manipulate the moves.

copy_move: This accepts an move as the argument and returns an independent copy of it. Please note that this should be a deep copy in that all references should be dereferenced and copied.
get_all_moves: This is the top level function that accepts a board and a piece number and returns all legitimate moves. We follow the rule that if there is a legitimate jump that captures at least one piece, then no normal move that does not capture any piece is allowed. Then we have two separate functions that return the jumps and normal moves respectively described below.
get_next_move_neighbors: This is the helper function used by the get_all_moves to return those normal moves that do not capture any piece. Implementation of the function is quite straightforward. First we get the list of immediate neighbors of the given piece. For example, for piece 23, we should return a list of (18, 19, 26, 27). This is done by the get_neighbor_pieces helper function which returns the same neighbors for a given piece regardless of the current board configuration.
Once we get the list of neighbors, we can iterate through them to see whether the given piece can move into that position. Clearly if that position is occupied, then we cannot move over there. We cannot move either if the current piece is not a king and the direction is not towards the opposite side. We use a helper function is_move_direction_allowed($board, $piece, $next) to do the check.
If we can move to that position and that position is the final row in the opposite direction, we should also crown the piece and mark the move as final.
get_all_next_jumps: This is the helper function used by the get_all_moves to return those jumps that capture at least one piece. Implementation of this function is probably the most difficult for such tool.

The requirement is that given a board and a piece, we need to find all those eligible jumps. This is in fact a tree traversal problem. Once we do one step in the jump, then we face the same problem again but with less pieces. Recursion is the most natural way to implement it and you can check our article Programming Problem: Find All Tree Paths to see how to solve a simplified version of the current problem with recursion.

We first need to implement a helper function that gets all the one-step jumps for a given board and piece. The function is named get_next_jump_neighbors in our code. Its implementation is very similar to that of get_next_move_neighbors. We need to check the neighbors of current piece and see if we can jump over it. If so, then we return all the eligible jumps.

Now the function get_all_next_jumps can be implemented like this. It first calls the get_next_jump_neighbors to see if there is any one-step jumps. If there is none, then it returns none too. Otherwise, we iterate through all the one-step jumps. If the jump is final, then it is eligible and we just add it to the final list of jumps we need to return. If the jump is not final, then we call the get_all_next_jumps function again with the board after the current one-step jump and the ending position of the jump. This returns all the jumps which starts from the current one-step jump's ending position and can be multi-step. Then we need to merge the one-step jump with these partial jumps. The code looks like the following:
```
foreach my $partial_jump (@$partial_jumps) {
	my $newjump;
	$newjump = copy_move($jump);
	$newjump->{end} = $partial_jump->{end};
	push @{$newjump->{steps}}, $jump->{end};
	push @{$newjump->{steps}}, @{$partial_jump->{steps}};
	$newjump->{board} = copy_board($partial_jump->{board});
	push @alljumps, $newjump;
}
```
Afterwards, we can just return all the jumps we've obtained so far.

Now we need to glue all the above together so users can interact with the study tool. First we define a function move_piece that accepts a board, a starting position and an ending position and then return the move if it is eligible. For the time being, we just assume that a starting position and an ending position can identify a move uniquely. So we can just call the get_all_moves function with the given board and the starting piece, and then we can iterate through all the moves and return the one that has the same ending position as the given one.

It is very trivial to implement a loop that reads user input and then process it accordingly. We can define q or Q to quit the tool, p or P to print the current board, s <filename> or S <filename> to save the current board to the specified file. Otherwise, a user can specify a move in the format of <start>-<end> and then we can call the move_piece function to check whether the move is eligible and if so update and print the board.

You can download the Perl script for studying the Checkers game and the sample Checkers position file and adapt it to your need.

Back to articles on development