|6.034 Artificial Intelligence - Recitations, fall 2004 online slides on games|
Next: Example Previous: Example
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