The Alpha Beta Procedure

The Alpha Beta Procedure

Alpha beta pruning is a search algorithm that improves the efficiency of minimax algorithm by reducing the number of nodes to be evaluated a tad in the search tree. The minimax procedure explores all the nodes of the search tree, where as alpha beta pruning (using branch and bound techniques) ignores all those nodes that are worse that the nodes evaluated so far. As a result, lot of searching effort is saved. An important characteristic of alpha beta pruning is that it returns the  same solution  as minimax algorithm would have returned. Moreover, it ignores (prunes or cuts off) those nodes (branches) that does not influence the final solution 

Consider that in a game tree, there exist a node 'i' such that a player has choice to move to 'i'. The alpha beta pruning procedure finds out whether the player has a better choice 'b' either at the parent n or at any other node above this level. If a better choice 'b' exists then alpha beta procedure prunes node of 'i' because we have a better choice than 'i' and therefore 'i' is not expanded or evaluated. This results in faster searching. 

The alpha beta pruning algorithm maintains two variables '∝' and 'β' for each node that is being examined. The variable '∝' will store the value of the best possible move we can make that we have found so far. On contrary, the variable 'β' will store the value  of the best possible move of our opponent can make, that we have computed so far. 

At any node, if the value of '∝' becomes greater than or equal to the of value of (∝ > β), then it implies that our opponent's best move will make our position more worse and hence we will prune this move  (i.e., this branch is not at all evaluated further). 

Algorithm: Alpha beta (Player, board position, ∝, β). 

STEP 1: Check the current board position for game completion state. If game over, return the winner.

STEP 2: Set, SUCCESSOR = All possible (legal) moves (nodes) the player can make in the current board position. 

STEP 3: If player is 'max' then, 

                For each node in SUCCESSOR perform the following, 

• Set, Score = Alpha_beta (opponent, SUCCESSOR, ∝, β). 

This is a recursive call. 

• If Score > ∝ , then ∝  = Score. 

This means we have found a better move (node). 

Therefore, update the value of ∝  to new value. (i.e., score)

• If ∝ > β then, return ∝ 

    This is the cut off' step. Since ∝ ≥ β, it means if we move to this node, our situation will become worsed. Therefore, we will not expand this node, rather we will prune it. 

STEP 4: If player is 'min' then 

For each node in SUCCESSOR perform the following, 

• Set, Score = Alpha_beta (opponent, SUCCESSOR, ∝, β), 

            This is recursive call. 

• If Score < β then set β = Score. 

            It means opponent has found a better worse move 

• If ∝  > = β then, return β,

            This is a cut off step. Since ∝ ≥ β we will return β because this is player min's move. 

Example: Consider the game of tic-tac-toe in which two players (max and min) make moves alternately such that 'max' will always try to move to a node (in the game tree) which has high value where as 'min' will try to move to a node with-minimum value. Consider a trivial 2 ply game tree for tic-tac-toe given in Fig.

Fig: An Example Tree for Tic-tac-toe Game

The alpha beta procedure will search the given game tree as follows,

STEP 1: The initial value of ∝ and β of the root node will be set to -∞ and +∞ respectively. Then, the first leaf node is expanded, that gives value '5'. Since, 'M1' is a 'min' node its 'β' value is set to 5. 

STEP 2: The second leaf node is generated, which has the value 18, since 18 > min would avoid this move. Therefore, 'β' value of M1 will remain same i.e., 5. 

STEP 3: The third leaf node of 'Ml' will be generated, which has the value 11. Again 11 > 5 and hence 'min' would not move here, consequently, the 'β' value will be unchanged. Since node 'Ml' is explored completely its '∝' value and its parent's (i.e., root) '∝' values are both set to 5. 

STEP 4: The first leaf node of `M2' is generated. Its utility (β) Is founded as '5' which is equal to the '∝' value of its parent (i.e., node 'S') ∝ == β. Therefore, the exploration of other leaf node of 'M2' is pruned.

STEP 5: The first leaf node 'M3' is generated. Its utility (β) is 1, which is greater than '∝' (i.e., ∝ > β). Therefore, the exploration of other leaf nodes of 'M3' are pruned.

The minimax algorithm would have explored the whole game tree to search the best strategy. However, alpha_beta pruning algorithm have reduced the number of nodes to be evaluated. Moreover, it is observed that alpha_beta pruning will reduce the exponential complexity of minimax algorithm to half.