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

Examples

• Typical-case example (average branching factor reduced by about a third)
  
  
• Best-case example (average branching factor reduced by over a half)

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