AlphaBeta Home Page

• Abstract
• Description on how the alpha-beta search works
• Animated version of alpha-beta search
• Static version of alpha-beta search

Abstract

Researchers in game playing have developed a class of search techniques called alpha-beta pruning to improve the efficiency of search in two person games. The idea for alpha-beta search is simple:-
 

1. Alpha-beta search proceeds in a depth-first fashion rather than searching the entire space to the ply depth.
2. Two values, called alpha and beta, are created during the search.
3. The alpha value, associated with MAX nodes, can never decrease, and the beta value, associated with MIN nodes can never increase.

Return to top.

Suppose a Max node's alpha value is 6. Then MAX need not consider any backed up value less than or equal to 6 that is associated with any MIN node below it. Alpha is the worst that MAX can score given that MIN will do its best. Similarily, if MIN has a beta value of 6, it need not consider any MAX node below it that has a value of 6 or more.

Return to top.

This image represents the overview of the animated version of alhabeta search.

Return to top.

This image represents the state of the static version of alphabeta search

Return to top.