Alpha-Beta Pruning

ALPHA-BETA pruning is a method that reduces the number of nodes explored in

Minimax strategy. It reduces the time required for the search and it must be restricted so

that no time is to be wasted searching moves that are obviously bad for the current player.

The exact implementation of alpha-beta keeps track of the best move for each side as it

moves throughout the tree.

We proceed in the same (preorder) way as for the minimax algorithm. For the MIN

nodes, the score computed starts with +infinity and decreases with time. For MAX

nodes, scores computed starts with -infinity and increase with time.

The efficiency of the Alpha-Beta procedure depends on the order in which successors of a

node are examined. If we were lucky, at a MIN node we would always consider the nodes

in order from low to high score and at a MAX node the nodes in order from high to low

score. In general it can be shown that in the most favorable circumstances the alpha-beta

search opens as many leaves as minimax on a game tree with double its depth.

Alpha-Beta algorithm:

The algorithm maintains two values, alpha and beta, which represent the minimum

score that the maximizing player is assured of and the maximum score that the

minimizing player is assured of respectively. Initially alpha is negative infinity and

beta is positive infinity. As the recursion progresses the "window" becomes smaller.

When beta becomes less than alpha, it means that the current position cannot be the

result of best play by both players and hence need not be explored further.

Pseudocode for the alpha-beta algorithm is given below.

evaluate (node, alpha, beta)

if node is a leaf

return the heuristic value of node

if node is a minimizing node

for each child of node

beta = min (beta, evaluate (child, alpha, beta))

if beta <= alpha

return beta

return beta

if node is a maximizing node

for each child of node

alpha = max (alpha, evaluate (child, alpha, beta))

if beta <= alpha

return alpha

return alpha