Alpha Beta Pruning:
In Minimax Procedure, it seems as the static evaluator must be used on each leaf node. Fortunately, there is a procedure that reduces both the tree branches that must be generated and the number of evaluations. This procedure is called Alpha Beta pruning which “prunes” the tree branches thus reducing the number of static evaluations.
The idea for alpha-beta search is simple: rather than searching the entire space to the ply depth, the alpha-beta search proceeds in a depth-first fashion. Two values, called alpha and beta, are created during the search. The alpha value, associated with MAX nodes, can never decrease, and the beta value, associated with MIN nodes, can never increase, Suppose a MAX node’2 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. Similarly, 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.
To begin the alpha-beta search, we descend to full ply depth in a depth-first fashion and apply our heuristic evaluation to a state and all its siblings. Assumes are MIN nodes. The maximum of these MIN values is then backed up to the parent (a MAX node, just as in minimax). This value is then offered to the grandparent of these MINS as a potential beta cutoff.
Next, the algorithm descends to other grandchildren and terminates the exploration of their parent if any of their values are equal to or larger than this beta value. Similar procedures can be described for alpha pruning over the grandchildren of a MAX node.
Two rules for terminating search, based on alpha and beta values, are;
- Search can be stopped below any MIN node having a beta value less than or equal to the alpha value of any of its MAX ancestors.
- Search can be stopped below any MAX node having an alpha value greater than or equal to the beta value of any of its MIN node ancestors.
- Start at C. Descend to full-ply depth and assign the heuristic to a state and all siblings (MIN 2,3). Back up these values to their parent node (MAX 3).
- Offer this value to the grandparent (A), as its beta value. So, A has beta=3. A will be no larger than 3.
- Descend to A’s other grandchildren. Terminate the search of their parent if any grandchildren are >= A’s beta. Node B is beta-pruned, as shown because its value must be at least 5.
- Once A’s value is known, offer it to its parent (C) as its alpha. So C has alpha=3. C will be no smaller than 3.
- Repeat this process, descending to C’s great-grandchildren (O) in a depth-first fashion. D is alpha-pruned because no matter what happens on its right branch, it cannot be greater than 0.
- Repeating on E, E is alpha-pruned because its beta value (2) is less than its parent’s alpha value (3). So no matter what happens on its right branch, E cannot have a value greater than 2.
- Therefore C is 3.