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