minimaxAB algorithm

/*
  alpha is the best score for max along the path to state
  beta  is the best score for min along the path to state
  
  returns VALUE of best operator
  need additional code to return operator
*/
int minimaxAB(state, player, depth, alpha, beta)
        if (depth == limit or state is terminal)
                return the static evaluation of state
        if (player is min)
                until all successors, s, are examined or alpha > beta
                        val=minimaxAB(s, max, depth+1, alpha, beta)
                        if (val < beta)
                                beta = val
                return beta
        if (player is max)
                until all successors, s, are examined or alpha > beta
                        val=minimaxAB(s, min, depth+1, alpha, beta)
                        if (val > alpha)
                                alpha = val
                return alpha

Using minimaxAB in a game playing program

Here is a top-down decomposition of a game playing program that you can use. The notation [State/Mi] represents the state after move Mi is applied to it.

Top Level
Let State <-- the initial game board
Let Player <-- Select who goes first
Let Level <-- Depth Limit

while State is not the end of game loop
     State <-- Make one move (State, Player)
     Player = Next Player


Make one move (State, Player)
     if Player is USER then
          Ask USER to enter a valid move, M
          State <-- Apply Move (State, M)
          return State
     else if Player is Me (Computer)
          M <-- Find Best Move (State, Player)
          State <-- Apply Move (State, M)
          Inform USER of move, M
          return State

Fine Best Move (State, Player)
     Let BestValue <-- -INFINITY
     Initialize PBV and Best Move to NULL

     Generate all possible moves for Player in State (M1, ..., Mb)
     Let BestValue <-- minimaxAB(State/M1, Next Player, 1, -INFINITY, +INFINITY)
     Let BestMove = M1

     for K = 2 through b loop
          PBV <-- minimaxAB(State/Mk, Next Player, 1, -INFINITY, +INFINITY)
          if PBV > BestValue then
                BestValue = PBV
                BextMove = Mk

     return BestMove

example graph

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

trace of algorithm on graph

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

successors B,C,D
  B
  minimaxAB(B,min,1,-inf,+inf)
  successors E,F,G

    E
    minimaxAB(E,max,2,-inf,+inf)
    successors L,M
      minimaxAB(L,min,3,-inf,+inf)
      returns 7
      alpha = 7
      minimaxAB(M,min,3,7,+inf)
      returns 6
    returns 7

    beta = 7

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

    G
    minimaxAB(G,max,2,-inf,7)
    successors P,Q
      minimaxAB(P,min,3,-inf,7)
      returns 2
      alpha = 2
      minimaxAB(Q,min,3,2,7)
      returns 3
      alpha = 3
    returns 3

    beta = 3
  returns 3
  alpha = 3

  C
  minimaxAB(C,min,1,3,+inf)
  successors H,I
 
    H
    minimaxAB(H,max,2,3,+inf)
    successors R,S
      minimaxAB(R,min,3,-inf,3)
      returns 0
      alpha = 0
      minimaxAB(S,min,3,0,3)
      returns -2
    returns 0
    
    beta = 0
    *** CUTOFF alpha>beta ***
  
  returns 0

  D
  ...