• GuiCheckers105.zip (743 KB): The zip file includes:
  guicheckers.exe, the checkers program with a graphical user interface.
  guicheck.dll, the same checkers engine, in a format that can only be run by CheckerBoard.
  opening.gbk, the opening book, it contains a database of opening positions to play into.
  database.jef, an endgame database for 2v2 pieces or fewer.
  gui105help.htm, a short help file with details about using the program.

Mar 16th, 2006: I recompiled the GuiCheckers v1.05 with profile-guided optimizations, making it 15% faster. It now reports itself as v1.05+. (May now require Win98 or later.)
Nov 26th, 2005: The v1.05 .exe only worked in WinXP. This is now fixed, it should work in Win95 and later.
Nov 25th, 2005: Surprisingly, my endgame databases have always been slightly zany. Probably didn't matter much. The database in the downloads is now hopefully correct.

You're welcome to mail me comments/bug reports/suggestions.

Version History:

• v1.05: Added a bitboard representation on top of the current program. This has resulted in a speed increase of 50%-100% (varies with position.) Also now you can start and stop the search at any time, and the information updates regularly. Slight changes to the search extensions. Slight evaluation changes. A few adjustments to the opening book.
• v1.00: This is the first version to have an opening book, having a book yielded much better results in test matches. The GUI now supports PDNs, along with other smaller changes. No changes of note to the search or evaluation.
• v0.99: The engine is definitely stronger and the GUI has been updated with more options. The evaluation and search have been improved, and I corrected a few bugs. I made my own endgame database for 4-pc and less endings.
• v0.90, v.80, v.75.... older versions, changes not logged.

• GuiCheckers100.zip :   version 1.00 Download includes opening book and endgame databases
• guiCheckers.exe :   version 0.90 Checkers program with a graphical user interface. 
• guicheck.dll :    version 0.90 Engine. This can only be run by CheckerBoard.

• My primary reason for releasing source code has always been so that others can look at it, as a learning tool, or just out of curiosity.
• I also think some interesting projects are possible by starting from this source and altering or expanding it.
• Just remember if you use/modify my source code, commercial distribution is prohibited, and free distribution is allowed but must clearly acknowledge it uses code from this web page.
• My favorite project suggestion is to convert Gui Checkers to play different checker variants instead of only English/American rules. This is something I was considering myself, but never got to.
• You could port Gui Checkers to other platforms.
• Convert the program completely to bitboards, and drop the sq array from the structure. If done right this will make the program faster, since it won't have to copy the sq data.
• You could use the source in academic Artificial Intelligence related projects.
• You could try making the program stronger. Unfortunately it is rather difficult to accurately measure strength as a great number of games against multiple opponents is required, and I don't know of any committed independent testers for checkers like there are in chess.

Last Released Version:

GuiCheckSource105.zip ( 78 KB ):

• This is the full cpp source code for everything. Includes code for the windows gui, opening book, and endgame database.
  ( Note: The book and database themselves are only in the program download. )
• The project files are for MSVC 2005.
• If you have an earlier version or different compiler you'll have to set it up on your own. guicheckers.cpp is the only cpp file compiled, all other files are included from it. However you'll also have to add the bitmaps / icon / resource files.
• The engine .dll file for checkerboard can also be compiled from this code by setting the target for your compile to a .dll. For this you only need add the guicheckers.cpp file to the project.

See details on the endgame database uncompression here. It is only partially my code.

In Progress Version:

GuiCheckSource110.zip ( 556KB ) :

• There is no opening book, it hasn't been generated yet. That's why this version is categorized as in progress.
• This version include's support for Ed Trice's 6-piece endgame databases. If want to generate them you should run checkers_db6_builder.exe in the database directory. They will take up 842 Megabytes and give the exact value for the important 6-piece or less endings.
• This version is entirely bitboard, and therefore faster than 1.05
• Note the working directory should be set to the base directory (the one with database.jef) and not the src directory.

Older Versions:

GuiCheckSource99.zip ( 15 KB ):
Source code for the 0.99 engine for CheckerBoard. This source does not include the graphical user interface, or the endgame databases. The game-playing engine is under 1000 lines of code, but includes some advanced techniques. The 0.99 source doesn't use bitboards, so movegen is simpler but slower.
GuiCheckSource90.zip: version 0.90 source code. For the complete win32 GUI version.
GuiCheckSource.zip:  version 0.80 source code. For the complete win32 GUI version
checkers.cpp : Old ASCII version C++ source file (800 lines)

This is based on an older checkers playing program that I made in three days originally, plus 3 more days to get the first GUI version, new move generation, better search and cleaner code. It was made to be a demonstration of game-programming techniques, but has grown since then. I no longer keep track of time spent on this program. Newer features are forward-pruning, improved GUI, and a checkerboard version. It helped a lot that I've made other game playing programs, and I was able to borrow and adapt some code. The source is downloadable, so if you're interested in game playing programs, and want to see source code for some techniques used in strong game playing programs, download it and look it over. Sometime I'll try to make the source simpler to read. I've heard checkers has an average branching factor of about 3, because all jumps are forced. So this program can search around 16 ply ahead plus a few extra ply for extensions and quiescence search of jumps, (on an AMD 1.4 ghz, in 3 seconds), or over 24 ply when there are fewer checkers, or fewer moves, and not many kings. 

There of course may be bugs (in the game playing AI, or the GUI) due to inadequate testing, and not enough debugging. When programming game playing programs, it's important to include as much search and debugging information as possible.

In checkers.txt, you'll find an interview I did for the Checker Maven which contains some additional info.

Playing Strength:

Its play is strong enough to beat me, but that's not saying much. I think it's quite strong overall, but may make some dubious positional moves, and even at full strength it occassionally has trouble making progress in won games. It's probably stronger in searching than in evaluating, since I don't know much about checkers. I'm have no clue what the results would be against a serious checkers player (eg. someone who plays in professional checkers tournaments.) Against the much more common casual player or novice, I think it will usually win, or sometimes draw. Use Menu->Options->Beginner to weaken the play significantly.

The Source Demonstrates:

• Recursive minimax search with
• Alpha Beta Pruning
• Iterative Deepening
• Transposition Table (Hash Table).
• Quiescence Search

Alpha Beta is a technique for greatly reducing the number of moves searched to get the exact same result. It's fairly simple to implement, and necessary for reaching deep search depths. Imagine searching 2 ply (your move, then your opponent's move.)You play move #1, you look at all your opponent's responses, and find his best response leads to you being up 3 points. So now you know you can get at least 3 points, and you store this value. Then you try move #2, and find your opponent's first response leads to you only being up 1 point. Therefore for you can stop searching(cut-off) this move, because you already know it's irrelevant. (The score for move #2 will be less than or equal to 1, and you know the score for move #1 is equal to 3) This strategy can be applied to every level of the search.

Alpha Beta makes it possible to reach up to almost twice the search depth (if optimal,) by searching the same number of positions. It is optimal if any time a player has one or more moves good enough to cause a cut-off, one of these moves is searched first. Therefore to get the most out of alpha-beta, you have to try to predict the best move for the player to move, and try this move first.

Iterative Deepening means starting with shallow searches before running a deeper search. (e.g. searching 8 ply, then 10 ply, then 12 ply, then 14 ply etc...) At first this sounds like a silly thing to do. Since of search size growth is exponential, the final search will probably take the vast majority of the search time, but still, why do that extra shallow searching? There are a couple of reasons. One is for move ordering. The transposition table stores the best moves from previous depths, which are usually good predictors for the best moves for higher depths, and thus actually cut down on the number of nodes searched. The other reason is that it's almost essential for timed games. You want the computer to move in a certain time, but you also want it to search as deep as possible in that time. When time runs out, you can just have the computer play the best move from the deepest depth fully searched. An even better way would be to use the best move from the depth currently being search. Since the best move from the previous depth should always be searched first, you know that this move will either be the same move as the previous depth, or a better move.

A Quiescence Search is almost completely necessary in a game like checkers or chess, where the evaluation is based greatly on material pieces. A quiescence search means searching certain board positions further before evaluating the board. Imagine trading a piece with the opponent, for instance you allow him to jump a checker of yours, because on the next move you can double jump him, and come out a piece ahead. If we stopped searching right after the first jump, the computer would evaluate that position as a piece ahead for it, instead of a piece behind, and that's a major problem! Therefore we only evaluate the board in positions where no jumps are possible. Quiescence searches in chess can be more complicated, because there are almost always captures possible, so it takes longer to just search them all.

A Transposition Table is a table in memory that stores information about board positions previously searched. A plain Alpha-Beta search function will search any board it receives, but this is wasteful if it has already encountered and searched this board before in another branch of the search. If there are more than one sequence of moves that leads to the same board position, (for instance, a checker can reach the same square in 2 moves by advancing left, then right, or right first, then left,) these positions will be encountered more than once in the search. The transposition table, implemented as a hash table, stores information about each position searched. The search function will also check each position searched to see if it is present in the transposition table, and if it is, retrieve: the depth to which it was searched, the best move from this position, the value, and whether this value was or within the alpha beta window (and thus an exact value,) higher, or lower. This information can either save you from searching the position altogether, or help to reduce the number of nodes searched.

Some tips for creating strong game playing programs:

Include as much debugging and search info as possible! Here are some things you should include in your program:

• Display the evaluation value returned (sounds like something everybody would do to me now, but my first game playing program actually didn't do this.) Also it should be able to display the evaluation value for the board as it is set up currently, and probably even the individual components of the evaluation function that create the final value.
• The number of nodes searched, search depth, time of search, and number of nodes searched per second. You'll want to check these numbers to make sure your optimizations and search enhancements are working.
• Display the principal variation (The expected moves for each side up to the depth searched) or even better, have it so the computer can be set to principal variation play (the search gets 1 ply shallower for each ply played) and there you can see where it's getting values for each move.
• Make it so you can turn on and off features that you are testing out, or those that may affect the search (such as the transposition table.) For example, if you introduce a new move ordering heuristic, this way you can test it against the old program to see how much better (or maybe worse) it works.
• Saving and Loading games. When things go wrong, and surely they will, you want to be able to save the position, so you can change the program, or the evaluation function, and load up and test out the position again.

• Use incremental updates of evaluation features (or most any other features that change with the board.) For example, instead of looking over the entire board and adding up values for each piece, you just update a material value in the board structure any time a piece is removed from the board or upgraded.
• Use lookup tables for anything you can. Try to find out what you can precompute ( for generating moves, or evaluating the board, etc.) and precompute it.
• Use a decent compiler. I use Microsoft Visual C/C++ 6.0 (Professional Edition, there's a cheaper non-optimizing version), which creates executables sometimes twice as fast as the last compiler I used.  (Watcom C/C++ 10.0, but the Watcom compiler is almost 8 years older, and was good for when it came out.)

and when your program plays a stupid move, remember, it's only a game =)

Links:
For more comprehensive information on checkers programming see: http://www.fierz.ch/strategy.htm
My own article: Using Bitboards with Checkers