Chinese Checkers uses alpha-beta tree searching in order to determine how to play its move. In simple terms this means the computer "thinks" if I make this move what move is the human player likely to make and then what would be my reply and then what position would I find myself in.

In order to determine how good a particular board configuration is the
program uses an ** heuristic** function. The heuristic function
says "the further my pieces are down to the end of the board the better
my position". This function returns an integer value. Better positions
return higher numbers and weaker positions return lower numbers. It is quite
a juggling act to get the heuristic function just right. In comparison
programming the alpha beta algorithm was easy.

Alpha beta is an optimization of the minimax algorithm. Here is minimax
for your convenience.
* Minimax* can be loosely summarized as follows:

The function is called from the top of the game tree: ie minimax(root)

function minimax (Node N of tree) If N is a leaf return the heuristic value of this node. for any successor Ni of N if Node N is a Min node return Min (minimax (N1), minimax(N2), ... ) if Node N is a Max node return Max (minimax (N1), minimax(N2), ... ) End For end function

The function is called as a-b (root, -infinity, +infinity)

function a-b (Node N, alpha, beta) If N is a leaf return the heuristic value of this node. For any successor Ni of N if node N is a Min node beta = Min (a-b (Ni, alpha, beta), beta) if alpha >= beta return beta if Node N is a Max node alpha = Max (a-b (Ni, alpha, beta), alpha) if alpha >= beta return alpha End For End Function

Back to Chinese Checkers Page

Back to my Home Page