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.
Here is an example of Alpha-Beta search
Alpha-Beta algorithmThe 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
