# Minimax Search with Alpha-Beta Pruning

## Algorithm

 ALPHA-BETA(state, player, depth, alpha, beta) /*alpha is the best score for max along the path to state beta is the best score for min along the path to state*/ If the level is the top level, let alpha = -infinity, beta = +infinity If depth has reached the search limit, apply static evaluation function to state and return result If player is max:     Until all of state's children are examined with ALPHA-BETA or until     alpha is equal to or greater than beta:              Call ALPHA-BETA(child, min, depth+1, alpha, beta);              note result              Compare the value reported with alpha; if reported value              is larger, reset alpha to the new value      Report alpha If player is min:     Until all of state's children are examined with ALPHA-BETA or until     alpha is equal to or greater than beta:              Call ALPHA-BETA(child, max, depth+1, alpha, beta);              note result              Compare the value reported with beta; if reported value              is smaller, reset beta to the new value      Report beta

## Trace of the algorithm on the following tree

```
--------------A--------------         max
/              |              \
B               C               D       min
/  |  \          /   \           /   \
E   F   G       H      I         J     K    max
/ \  / \ / \     / \    / \       / \   / \
L M  N O P Q     R S    T U       V W   X Y   min
7 6  8 5 2 3     0 -2   6 2       5 8   9 2

First call (assume depth limit is 3):
ALPHA-BETA(A,max,0,-inf,+inf)

children B,C,D
B
ALPHA-BETA(B,min,1,-inf,+inf)
children E,F,G

E
ALPHA-BETA(E,max,2,-inf,+inf)
children L,M
ALPHA-BETA(L,min,3,-inf,+inf)
returns 7
alpha = 7
ALPHA-BETA(M,min,3,7,+inf)
returns 6
returns 7

beta = 7

F
ALPHA-BETA(F,max,2,-inf,7)
children N,O
ALPHA-BETA(N,min,3,-inf,7)
returns 8
alpha = 8
*** CUTOFF alpha > beta ***
returns 8

G
ALPHA-BETA(G,max,2,-inf,7)
children P,Q
ALPHA-BETA(P,min,3,-inf,7)
returns 2
alpha = 2
ALPHA-BETA(Q,min,3,2,7)
returns 3
alpha = 3
returns 3

beta = 3
returns 3
alpha = 3

C
ALPHA-BETA(C,min,1,3,+inf)
children H,I

H
ALPHA-BETA(H,max,2,3,+inf)
children R,S
ALPHA-BETA(R,min,3,-inf,3)
returns 0
alpha = 0
ALPHA-BETA(S,min,3,0,3)
returns -2
returns 0

beta = 0
*** CUTOFF alpha > beta ***

returns 0

D
...
```