AI Unit 1

Alpha-Beta Pruning in AI: Complete Exam Guide

1. Introduction

Alpha-Beta Pruning is an advanced search optimization technique used in the Minimax algorithm. In two-player, zero-sum games (like Chess or Tic-Tac-Toe), the Minimax algorithm explores all possible game states to find the best move. However, this generates a massive search tree, taking too much time and memory.

Alpha-Beta Pruning solves this by "pruning" (cutting off) branches of the game tree that are guaranteed to not influence the final decision. By skipping useless branches, the algorithm calculates the optimal move much faster without changing the final output.

2. Key Concepts: Alpha and Beta

To decide which branches to cut, the algorithm uses two tracker variables passed down the tree:

• Alpha (α): The best (highest) value that the Maximizer can guarantee so far at the current level or above.
  Initial Value: -∞ (Negative Infinity)
• Beta (β): The best (lowest) value that the Minimizer can guarantee so far at the current level or above.
  Initial Value: +∞ (Positive Infinity)

The Pruning Condition: At any node, if α ≥ β, stop evaluating this branch and return the current value. The opponent will never let you reach this path anyway.

3. General Overview of the Example

Below is the standard tree example explaining how values are updated and branches are pruned.

4. Detailed Node-by-Node Traversal (Steps 0 to 17)

Follow the algorithm exactly as it traverses the tree diagram above, updating alpha/beta values and executing the pruning conditions.

Step 0

Start at Node A (Root - MAX). Initialize α = -∞ and β = +∞. Move down left to Node B.

Step 1

At Node B (MIN). Inherits α = -∞, β = +∞. Move down left to Node D.

Step 2

At Node D (MAX). Inherits α = -∞, β = +∞. Evaluates its left leaf child, which has a value of 2.

Step 3

Node D (MAX) updates α = max(-∞, 2) = 2. Evaluates right leaf child, value is 3.

Step 4

Node D updates α = max(2, 3) = 3. All children evaluated. Node D returns 3 to Node B.

Step 5

Back at Node B (MIN). Updates β = min(+∞, 3) = 3. Current values at B: α = -∞, β = 3. Move to right child Node E.

Step 6

At Node E (MAX). Inherits values from B: α = -∞, β = 3. Evaluates left leaf child, value is 5.

Step 7

Node E (MAX) updates α = max(-∞, 5) = 5. Current values at E: α = 5, β = 3.

Step 8: PRUNING!

Pruning Condition Met at E! Since α (5) ≥ β (3), the algorithm stops evaluating E's children. The right leaf (value 9) is pruned. Node E returns 5 to Node B.

Step 9

Back at Node B (MIN). Checks newly returned value: β = min(3, 5) = 3. All non-pruned children evaluated. Node B returns 3 to Root A.

Step 10

Back at Node A (Root - MAX). Updates α = max(-∞, 3) = 3. Current values at A: α = 3, β = +∞. Move down right to Node C.

Step 11

At Node C (MIN). Inherits values from A: α = 3, β = +∞. Move down left to Node F.

Step 12

At Node F (MAX). Inherits α = 3, β = +∞. Evaluates left leaf child, value is 0.

Step 13

Node F (MAX) attempts to update α. α = max(3, 0) = 3 (remains unchanged). Evaluates right leaf child, value is 1.

Step 14

Node F attempts to update α. α = max(3, 1) = 3 (remains unchanged). All children evaluated. Node F returns 1 to Node C.

Step 15

Back at Node C (MIN). Updates β = min(+∞, 1) = 1. Current values at C: α = 3, β = 1.

Step 16: PRUNING!

Pruning Condition Met at C! Since α (3) ≥ β (1), the algorithm stops evaluating C's right side. The entire Node G subtree (values 7 and 5) is pruned. Node C returns 1 to Root A.

Step 17

Back at Node A (Root - MAX). Updates α = max(3, 1) = 3. Entire tree traversal is complete. The optimal value is 3.

5. Advantages of Alpha-Beta Pruning

• Improved Efficiency: By ignoring useless branches, it significantly reduces the number of nodes evaluated compared to standard Minimax.
• Time Complexity: Standard Minimax has a time complexity of