                      l i b c h e c k e r s - 1 . 0 6

                                    by

		            A d a m   M c K e e


OVERVIEW
==============================================================================

The recent match between Deep Blue and Gary Kasparov inspired me to dig up
a Checkers engine I wrote a couple of years ago.  I cleaned up the engine a
bit, improved it in a couple of ways, wrote a simple text-mode Checkers game
that uses it, and now I present it to you.  I hope that many people will be
able to read and understand the source code, so that they may understand the
relatively simple techniques that are used to get computers to play games like
Checkers and Chess convincingly well.  For instructional purposes, it is
better to study a Checkers engine than a Chess engine.  This is because
Checkers is a very simple game (as far as the rules are concerned), and 
therefore one may concentrate on the most basic techniques that can actually
be applied in the creation of engines to play a variety of games (including
Chess).  For instance, after mastering the source code for this engine, it
would not be a big deal to transform it into a simple Chess engine.


ABOUT THE ENGINE
==============================================================================
It's 1100 lines of code, and you have to be a pretty good player to beat it.
Here's what the engine does:

	o Min-max, with alpha-beta pruning
	o Selective deepening (extend the search when interesting stuff is
	  happening such as captures or checkers being KINGed).
	o Iterative deepening (continually search deeper until a time limit
	  has expired).  If you read the code carefully you will find that
          iterative deepening is used to take better advantage alpha-beta
          pruning.
	o A few simple heuristics.

Here's what it doesn't do:

	o Parallelism.
	o Move database.

The number of possible board configurations in Checkers is actually small
enough to permit a "solution" of Checkers, so that the computer could actually
play a perfect game every time.  If you want to add in code to manage a move
database, this is a very do-able task, and would eventually result in an
un-beatable engine.


Min-max and alpha-beta pruning
==============================================================================
Min-max is a very simple and popular way to do AI for game-playing.  The
basic idea is as follows:

	There are two players in the game with opposite intentions.  I.e.
	each player intends to preserve his own well-being, and bring about
	the other player's downfall.  To represent this struggle in the
	machine, we regard one player as wanting to *maximize* the value of
	the game state, and the other player as wanting to *minimize* the
	value of the game state.  I.e. if we represent a black checker as
	being of value 100, and a white checker as being of value -100, then
	obviously Black will want to maximize the value of the board (which he
	accomplish by capturing White pieces and by avoiding the capture of
	his own pieces).  White, in turn, wants to minimize the value of the
	board (by capturing Black pieces and avoiding the capture of his own
	pieces).

For example, suppose the engine is trying to decide what move Black should
make in a given board configuration.  It will do this by trying out each of
Black's possible moves to see which one holds the most promise (the one that
*maximizes* the value of the board).  "Trying out" a move is a matter of
making the move, and then seeing how well the other player can do, given this
new board configuration.  For example, Black will make a move, then call
white() to see what White can make of it.  White will do basically the same
thing Black does to determine what its best move is, except that it is trying
to *minimize* the value of the board.  So, White will generate a list of
possible moves, and then try out each one to see how well Black can do with
it.  As I hope you are starting to see, this is a recursive process.  In the
engine code you will find two functions black() and white() that simulate the
behaviour of each player.  As you might expect, these functions are mirrors
of each other -- the only differences between black() and white() are due to
the fact that Black and White have different goals.  These two functions
could have been merged into one, at a slight performance penalty.

Alpha-beta pruning is a relatively simple optimization that is used to avoid
wasting time searching irrelevant parts of the tree.  The premise for it is
very simple.  Suppose that Black has already determined that by making a
certain move, he can get the value of the board up to +300.  But Black
continues to evaluate more moves, in the hopes of doing even better than this.
So Black makes another move, then calls white() to see what White can make of
it.  White evaluates some moves, then finds a move that yields a score *lower*
than +300.  At this point, White's search can be safely abandoned because Black
will *never* allow this board position to occur.  Why is that?  Black has
*already* determined that he can get a score of +300 by making a certain move.
The only reason that Black would make a different move is if he could do even
better by making that move.  Black would never pass up a move that will allow
him to get +300, in favor of a move that will allow White to obtain a score
lower than this!  Alpha-beta pruning is a very nice optimization, and I have
taken pains in the engine to make excellent use of it.


BUGS
==============================================================================
It doesn't handle the end-game very well -- it manages a good defense, but
has trouble closing out the game even when it has a solid material advantage.
Heuristics are probably the answer to this problem.  Ideas?


CONCLUSION
==============================================================================
I hope you have fun with it and learn from it.  Please let me know if you have
any ideas to improve it, or if you have found a bug.

	-- Adam McKee		<amckee@poboxes.com>
