Artificial Intelligence


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


Alpha beta is an optimization of minimax. The result of using alpha beta should be the same as minimax but faster.

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

Please email me : g.reed@clear.net.nz