|Gui Checkers | Download | Source | About | Programming Info | Bitboard Tutorial | Back to Programs Page|
| Gui Checkers v1.05+, last updated Mar 16th, 2006
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.)
You're welcome to mail me comments/bug reports/suggestions.
|Why I've released the source code:
Last Released Version:
78 KB ):
See details on the endgame database uncompression here. It is only partially my code.
In Progress Version:
GuiCheckSource110.zip ( 556KB ) :
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.
The results of automated matches using 3 move openings, thinking at 2 seconds per move, are below. I used only the endgame databases that came with the main download, no extras. Opening books for Cake & King's Row were set to "best moves." Cake and Simple are available for free at Martin's Page. KingsRow is available at Ed Gilbert's Page.
It's of note that the Gui 1.00+ Opening book was generated by training against these programs in the these same conditions, so that probably skews results a bit unfairly in Gui's favor. Different conditions (time controls/computers/endgame dbs/book options) might not do as well.
This section was written much earlier, and now the source code is much more
complicated. Someday I might make a simpler/weaker version of the source that
is very basic to help beginners.
The Source Demonstrates:
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.
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:
and when your program plays a stupid move, remember, it's only a game =)
Back to Programs Page