6.034 Artificial Intelligence - Recitations, fall 2004 online slides on games

Next: Example Previous: Example

Alpha-Beta Pruning

Typically can only look 3-4 ply in allowable chess time

Alpha-Beta pruning simplifies search space without eliminating optimality by applying common sense - if one route allows the queen to be captured, and a better move is available, don't search further down bad route. If one route assume stupid move by opponent, ignore that route.

                *   MAX

            *       *  MIN
          /  \    /  \
         2    7  1    No need to
		      look here!

     Maintain [alpha, beta] window at each node during depth-first search
     alpha = lower bound on max value, change at max levels
     beta  = upper bound on min value, change at min levels