By Liquid Nitrogen Overclocking CEO, Ed Trice

Many of us learned to play the game of checkers at a very young age. The rules are fairly straightforward. Setting up the board to play takes no time at all. And, most likely, we all played fairly quickly without too much thought, until our opponent starting winning!

I did not "rediscover" the game's hidden complexities until the year I turned 30, when I decided to write a program that could play the game of checkers. Since I had already written a strong chess program 11 years earlier, I thought making a killer checkers program would be easy. Boy was I wrong!

Throughout the course of designing the software (which turned into a major hobby spanning over 10 years) I talked to 3 different World Champions via email and game playing servers on the internet (Don Lafferty, Ron King, and Alex Moiseyev). In 2004, one of them showed up at my house the week before Christmas to play checkers with me, and against one of the strong endgame databases I had worked on with colleague Gil Dodgen. The reigning checkers World Champion was given one of the hardest positions to win featuring just seven pieces: 4 against 3. He would make a move against the checkers database, which had already computed every possible result for this endgame. The program retrieved the information, and tried, repeatedly, to force the human World Champion into positions that would take even longer to win. By defending the losing side in this fashion, the database was able to draw by virtue of disallowing the win. The World Champion could not make progress, despite the fact that the position was actually winable.

In fact, the position was so treacherous, even other checkers programs could not find winning paths either. I published a paper on these findings, which you can download here. It turns out, even as late as 2005, computer programs could not find ways to win an endgame that could be won featuring as few as 4 pieces against 3 in the game of checkers. The solution to the win that Gil Dodgen and I published still stands today as being correct, and nobody has come close to finding a position that requires more moves to win than this one. That position, with red to move and win, is shown below.



Red to move will win after both players have made a total of 253 moves.

It is plain to see that the red checker on the left is under attack by the white checker, so it must move out of the way immediately, or else it will be jumped. After red makes this move, the same white checker will be able to go between the red king and the red piece that just moved. There is no way for red to stop this piece from becoming a white king. White will have 3 kings, and red has just one king. Even worse, the sole red king is trapped in the corner, with no way to "rescue" it should white decide to just hold it in place. Two of the red checkers will have to fight to crown, come back to rescue their trapped king, and then work on crowning the remaining checker, which white will have heavily guarded.

From a strategic standpoint, the strongest tournament checkers players understand these goals. However, the tactics along the way are just too deep from this position, and the perfect play checkers database prevails.

Once 64-bit technology arrived on the scene for personal computing, I again took a look at creating even larger checkers endgame databases. Dr. Jonathan Schaeffer of the University of Alberta had solved the game of checkers on April 29, 2007, rekindling my interest. You can read more about checkers being solved here at the University of Alberta website.

Dr. Jonathan Schaeffer's checkers-playing monster, which he named Chinook, was capable of searching far enough ahead from any checkers position that it would always encounter a pre-computed solution in the endgame that could not be avoided. The endgame databases in the Chinook program comprise 39,271,258,813,439 positions (over 39 trillion). While there are 500,995,484,682,338,672,639 possible positions in the game of checkers, since jumps are forced when they arise during the course of play, the endgame database is ultimately inescapable. Schaeffer's "forward solver" and "proof tree" were able to collide with his endgame database, even from the very beginning of the game, therefore the game was "solved".

It was after checkers was solved that I stumbled upon something interesting in the world of 64-bit computing. There were some fascinating properties of 64-bit structures that were just waiting to be applied to the game of checkers.

If you use the standard notion that most checkers players use, you will encounter certain "boundaries" that do not align "conveniently" on each side of the board that make move generation more complicated. For example, when moving a checker diagonally to the right, sometimes the destination is 3 squares away from the source square, and sometimes it is 4 squares away. Moving left is either 4 or 5 squares away from the source. Sometimes a destination that is 3 squares away from a source square does not even correspond to a valid move on the board, etc. The diagram shown below will help clarify this a bit.



Shown above is the "typical" layout shown in just about every book on the game of checkers. The diagrams are usually black and white, and the top of the board is where the dark pieces are placed. But, the side with the dark pieces will move first in the game of checkers, unlike chess, where white always moves first.

The squares are numbered 1-32 from the top-left to bottom-right. In the position shown, black could make the moves 4-8 or 1-6 safely. The move 5-9 would result in that black checker being jumped by the white king on square 14. Notice how the "number of squares moved" is either 4 (in the case of 4-8 and 5-9) or 5 (for 1-6). If black were to play the move 1-6, you can see that the next move for that checker could either be 6-9 (a difference of 3) or 6-10 (a difference of 4). But not every "difference" of 3, 4, or 5 would represent a valid move. You can see that from square 11, the movement of 3 squares, 11-14, does not represent a legal move in the game of checkers. You could argue that from that entire row, the legal moves are displacements of either 4 or 5 squares. But what about 12-17? The difference is 5, but from square 12, that is an illegal move also.

All of these factors complicate the process of writing a move generator, which must "handle the exceptions" with blocks of code surrounded by "if" statements. Each of these if "branch points" slow down the code, and make the move generator less efficient. However, using 64-bits, there was a way to represent the squares so that no "movement" of a piece would ever go "off the board" or "teleport" to an illegal destination. There is no need to wrap "if" statements around the code since moving to the right is always the same number of "squares" away, as are moves to the left. While this does not sound earth-shattering, the result was that a fully-functioning move generator could be written with only about 50 lines of code (reduced from about 190 lines of code using 32-bits). And, in the world of computing, fewer instructions = faster execution time.

The board layout that I used with 64-bits is shown below.



At first glance, such an enumeration scheme does not make any sense, but to a computer program, it is the ideal layout to play the game of checkers.

Look at square 1 on the board. Notice that all of the squares to the upper-right of it differ by 9: 1,10,19,28,37,46,55,64. That is one of the two directions a red (or black) checker at the bottom of the board can move. So, if your move generator uses a bitboard, all you have to do is shift (>>) the bits 9 bits "up" to higher placement in the register, and you can generate every move to the upper-right simultaneously. There are some other details that programmers will readily understand, but, the important thing is, there is no need to check to see if pieces "slid" onto illegal/impossible destinations using this board layout.

Now look at square 17. You can see every square to the upper-left differs by 1: 17,18,19,20,21 are all the squares in that direction. In fact, if you look at the entire board, EVERY movement to the top-left is to a square 1 greater than the source square. Any movement to the upper-right is an increase of 9 from any square on the board as well. For pieces moving in the other direction, the squares decrease by the same amount.

The boundaries are such that moving by the same amount will never allow a piece to "fall off the board." Look at square 31. Notice if you "add 1" to it, which would represent a continued movement to the top-left, you would get "32," which is a square not on the board. The code in the move generator would not recognize this as a legal destination automatically, so it is not possible to "generate a move" in that direction. Likewise from square 54, there is no "+9" counterpart, so there is no movement to the upper-right that is "legal." You can verify that in the other direction, the same is true. There is no decrease in the square numbers that will allow a piece to slide off the board from top to bottom.

What about jumps and multiple jumps? They are handled properly as well. Look at square 28. Suppose a checker on that square could jump a piece on square 37 and land on square 46? That represents a "jump" of 18. Any squares on the board that differ by 18 are legal jumps to the right (from the perspective of the bottom of the board). Any squares that differ by 2 are legal jumps to the left. You can see it is not possible for square 55 to jump in either top direction. There is no square 57 (indicating a jump to the left) and no square 73 (indicating a jump to the right). From the top of the board, the left and right are obviously reversed. Square 56 can jump to the square 54, a difference of 2 squares, and this is "to the right" as you look at the board. Likewise, square 38 can jump to square 20, and this jump looks like it is "to the left."

Such a bitboard makes the C-code for the legal move generator extremely simple. See the image below (you may have to click on it to zoom in with your browser).



Because of the brevity of the source code, this move generator runs very fast. The time it takes to complete on any given system is a direct measure of the computer's processing power. Shorter execution times means the core on which it ran is faster than a CPU core that reported a longer execution time. This makes it an ideal benchmarking application.