Alpha-Beta Pruning
In computing the min/max value of a game tree node, we can skip ("prune") the evaluation of some of the children nodes using what is known as alpha-beta pruning.Let alpha be a lower bound for the value of a max node A, and let B be a child node of A. If the value v of a child of B is less or equal to alpha, then we can use v as a value for B and skip the rest of the children of B. This is called "alpha pruning". In the figure below, alpha = 20, and we can prune the rest of the children of C2, once the value of D is (recursively) computed.
Let beta be an upper bound for the value of a min node B, and let C be a child node of B. If the value v of a child of C is greater or equal to beta, then we can use v as a value for C and skip the rest of the children of C. This is called "beta pruning". Exercise: draw a figure similar the one below to illustrate beta pruning.
Last Revised 11/30/00