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