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:
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