The problem with mini max search is that the number of game states it has to examine is exponential in the number of moves. Unfortunately, we cant eliminate the exponent, but we can effectively cut it in half. The trick is that it is possible to compute the correct mini-max decision without looking at every node in the game tree that is, we can borrow the idea of pruning in order to eliminate large parts of the tree from consideration. The particular technique we will examine is called alpha – beta pruning. When applied to a standard mini-max tree, it returns the same move as mini-max would, but prunes away branches that cannot possibly influence the final decision.

• The steps are explained in figure 6.5. the outcome is that we can identify the mini-max decision without ever evaluating two of the leaf nodes.

• Let the two un evaluated successors of node C. in figure 6.5. have values X and Y and let Z be the minimum of X and Y. the value of the root node is given by

MINI MAX-VALUE (root) = max(min (3,12,8), min(2,x,y) min

= max (3, min (2, x, y), 2)

= max (3, 2, 2) where Z $\leq$ 2

= 3

In other words, the value of the root and hence the mini-max decision re independent of the values of the pruned leaves X and Y.

Stages in the calculation of the optimal decision for the game tree.

Alpha-beta pruning can be applied to trees of any depth and it is often possible to ? entire sub-trees rather than just leaves.

The general principle is this: Consider a node n somewhere in tree (see figure 6), such that player has a choice of moving to that node. If player has a better choice. M either at the parent node of n or at any choice. Point further up, then n will never be reached in actual play. So once we have found out enough about n (by examining some of its descendants) to reach this condition, we can pursue it.

Figure, Alpha beta pruning : The general case, If m is better than n for player, will never get to n in play.

Alpha-beta pruning gets its name from the following two parameters that describe bounds on the backed up values that appear anywhere along the path:

$\alpha$ = The value of the best (i.e. highest value) choice we have found so far at any choice point along the path for MAX.

$\beta$ = The value of the best (i.e. lowest value) choice we have found so far at any choice point along the path for MIN.

Alpha-beta search updates the values of $\alpha$ and $\beta$ as it goes along and prunes the remaining branches at a node (i.e., terminates the recursive call) as soon as the value of the current node is known to be worse than the current $\alpha$ and $\beta$ value for MAX or MIN respectively. The complete algorithm is given in figure 6.7.

The effectiveness of Alpha-beta pruning is highly dependent on the order in which the successors are examined. Example: In figure 6.5 ( e ) and ( f ), We could not prune any successors of D at all because the worst successors were generated first. If the third successor had been generated first, we would have been able to prune the other two. This suggest that it might be worthwhile to try to examine first the successors that are likely to be best.

Algo $\leftarrow$ $\beta$

function ALPHA – BETA – SEARCH (State) returns an action.

inputs: State, current state in game.

V $\leftarrow$ MAX – VALUE (State, - $\infty$ + $\infty$)

return the action in SUCCESSORS (State) with value.

function MAX – VALUE (State, $\alpha$, $\beta$) returns a utility value

$\alpha$ , the value of the best alternative for MAX along the path to state

B, the value of the best alternative for MIN along the path to state

if TERMINAL – TEST (State) then return UTILITY (State)

V $\leftarrow$ - $\infty$

for a, s in SUCCESSORS (State) do

V $\leftarrow$ MAX (V, MIN-VALUE (S, $\alpha$, $\beta$ ))

if V $\leq$ $\beta$ then return V

$\alpha$ $\leftarrow$ MAX ($\alpha$, V)

return V.

function MIN-VALUE (State, $\alpha$, $\beta$) returns a utility value.

inputs: State, current state in game.

$\alpha$, the value of the current state in game.

$\beta$, the current state in game.

if TERMINAL – TEST (State) then returns UTILITY (State)

V $\leftarrow$ + $\infty$

for a, s in SUCCESSORS (State) do

V $\leftarrow$ MIN (V, MAX-VALUE (S, $\alpha$, $\beta$))

if V < $\alpha$ then return V

$\beta$ $\leftarrow$ MIN ($\beta$, V)

return V

Figure 6.7 $\alpha - \beta$ Search algo.

Apply $\alpha - \beta$ pruning on example given in figure 2 considering first node as MAX.

Apply $\alpha - \beta$ pruning on following example considering first node as MAX.