Alpha-Beta Pruning Lecture Notes

Introduction to Alpha-Beta Pruning

• Alpha-Beta pruning is an optimization technique for the minimax algorithm used in decision-making and game theory.
• It works by eliminating branches in the game tree that do not need to be examined because there already exists a better option.

Key Concepts

• Alpha: Maximum value found so far at any point along the path to the root for the maximizer.
• Beta: Minimum value found so far at any point along the path to the root for the minimizer.
• Pruning: Ignoring certain branches in the search tree that won't affect the final decision.

Step-by-Step Example

1. Initialization

   • Start with alpha = -∞ and beta = +∞.
   • Traverse the tree left first.

2. First Node Traversal

   • Set alpha = -∞, beta = +∞.
   • At the first child, which is a min node, update beta:
     • Compare left child (10) and right child (5).
     • Update beta = 5 (minimum of 10 and 5).
   • Update alpha at the parent max node:
     • alpha = max(-∞, 5), so alpha = 5.

3. Continue Traversal

   • Move to the next min node:
     • Update beta = min(∞, 7), so beta = 7.
     • Update alpha = max(5, 7), so alpha = 7.
   • Check for pruning:
     • If alpha >= beta, prune the branch. Here, 5 < 7, so continue.

4. Further Traversal

   • Continue checking nodes and updating values.
   • If a min node’s beta becomes less than or equal to a max node’s alpha, prune that branch.
   • Repeat the process until all nodes are processed.

5. Example Outcome

   • After completing the traversal, the optimal value is determined by the last computed alpha and beta values.
   • In this example, the final values lead to pruning several branches, indicating the efficiency of the algorithm.

Conclusion

• Alpha-Beta pruning significantly reduces the number of nodes evaluated in the minimax algorithm.
• By understanding how to set and update the alpha and beta values, one can effectively prune branches and optimize search in decision trees.