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.



Counting the play by both sides, red will win after 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 were 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 19 lines of code (reduced from about 150 lines of code using 32-bits). And, in the world of computing, fewer instructions = faster execution time.

Because of the nature of the actual bit patterns used in the endgame database's move generator that I wrote, and the other instructions that are carried out as the database solver iterates, the program can be used as an excellent benchmarking tool. It is single-threaded, uses almost exclusively integer-based calculations, exercises a good portion of the entire CPU's instruction set, and it should scale linearly as CPU speeds are throttled higher. The program is completely deterministic, so every CPU should get the same exact results every time (but, of course, faster processers will finish more quickly than slower ones).

Having said all of that, I should mention that this program uses a so-called forward move generator to solve the 2- through 6-piece databases. That is, it visits every position on each pass over the database, it makes legal moves of the pieces, and sees if it can improve on any of the information. It tries to resolve positions that are unknown, win positions faster that are wins, and make moves to postpone losses for as long as possible for positions that are lost. As it solves the various piece configurations, on each pass, fewer and fewer positions are solved, until no more changes take place. THIS TECHNIQUE IS NOT USED TO SOLVE LARGER DATABASES.

When attempting to solve the 34,779,531,480 positions in the 7-piece database and the 406,309,208,481 positions in the 8-piece database, you need to use a REVERSE MOVE GENERATOR to alleviate the need to revisit every position in the hope of finding moves leading to more wins and losses. It works like this: You make 2 passes over the database, as you would normally, using your forward move generator to resolve positions. You store the "newly solved" positions in a buffer. Instead of passing over the entire database time and time again, you only need to visit the positions in your buffer. From each of those positions, you have information about whether the position is a win, loss, or draw. So, you look at the pieces for the side that did not make the move leading to the result (essentially, you "change sides".) Then, you execute "reverse moves", moving them backwards, one at a time. You pretend it is their turn to move from these newly constructed positions. Each of these positions MUST play into a position you just resolved from the prior pass! There is no escaping this fact. The beauty of this approach is that, even if you scanned every one of the positions in the entire database, the only positions that can be resolved on the next iteration are the ones generated by the move reversing process.

So why didn't I incorporate a reverse move generator into the 6-piece database solver used for the benchmark?

For 6 pieces, the resolution time would be too fast to be meaningful. The algorithm that is not as efficient makes for better benchmarking. Small performance differences in hardware will be amplified, and it is easier to see which computer is actually running faster. What good would it be for a program that runs in 5 minutes and 14 seconds on one machine but 5 minutes and 13 seconds on another machine? How much would you trust that 1 second gain? But on my forward move generator, with a running time of several hours, the difference would be several minutes or even longer. It reduces the "chance factor" and more confidently reports on the performance differences.

The program creates a "report.txt" file which includes all of the meaningful data generated during the run. The last line of this file reports the total time taken to solve the databases. A sample from one of the faster runs from early 2010 is shown below. Click on the picture to see a larger image of the report.



This report file is the most important part of the test. After you have run the benchmark, don't forget to send in this file! The report shows the longest wins from the various piece configurations that were solved, including data that is needed to verify that your run went successfully. If any of the counts are wrong, then something happened during the test on your machine, and the result is not valid.

So, hopefully now you have a more complete understanding of the benchmarking utility. You can always ask a question by getting a hold of us through the CONTACT information shown on each page.