Alpha-Beta Pruning Demo

Minimax assumes that MAX chooses the highest utility and MIN chooses the lowest. Alpha-beta pruning returns the same root value while skipping branches that cannot change the decision.

This notebook uses NetworkX and Matplotlib to show the recursive calls. Run the cells in order. Leaf utilities are always measured from MAX’s perspective.

Imports

The directed graph stores parent-to-child edges; Matplotlib displays it after each recursive call. The search itself uses the supplied child lists, not a NetworkX search routine.

# alpha beta pruning demo

import networkx as nx
import matplotlib.pyplot as plt

Define a Small Game Tree

A is MAX; B and C are MIN. The left subtree has leaves 3 and 5, so B returns 3. Before running the code, decide whether both leaves under C need to be visited once A can already obtain 3.

The child-list order determines the search order. All terminal nodes must have entries in values.

# Example tree structure
tree_structure = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F", "G"],
    "D": [],
    "E": [],
    "F": [],
    "G": [],
}

values = {"D": 3, "E": 5, "F": 2, "G": 9}

Run the Trace

The expected call order is A, B, D, E, C, F. B returns 3, raising A’s alpha to 3. At C, F yields 2, lowering beta to 2. Since 2 is no greater than 3, G is skipped. The printed root value is 3.

The whole tree remains visible even when a branch is not searched. A picture is drawn on entry to a call, before that call backs up its result, so its label can still be blank. The last printed value is the final answer.

alpha_beta_demo = AlphaBetaTree(tree_structure, values)
print(alpha_beta_demo.alpha_beta_pruning("A"))

3

Check the Pruning Decision

  • Change G’s value from 9 to 100. Why does the root value remain 3?
  • Swap the order of C’s children. Which additional recursive call appears?
  • Compute the root value without pruning and compare it with the printed result.
Answers and discussion
  1. MIN still selects 2 under C. Changing G from 9 to 100 gives C = min(2, 100) = 2, while B = min(3, 5) = 3. A therefore remains max(3, 2) = 3. With the original child order, G is never evaluated because F already makes C no better than 2 for MAX.
  2. G is now visited as well. Searching C’s children in the order G, F first obtains 9. C’s beta is then 9, still greater than the inherited alpha of 3, so F must also be checked. The full call order becomes A, B, D, E, C, G, F. The root value stays 3, but no leaf is skipped.
  3. Ordinary minimax also returns 3. Evaluate both children of each MIN node: B = min(3, 5) = 3 and C = min(2, 9) = 2. The MAX root chooses max(3, 2) = 3. Alpha-beta obtains this same answer without visiting G in the original ordering.

Takeaway: move ordering changes the amount of pruning, not the minimax answer. A value returned from a cutoff can be a bound rather than the exact value of that subtree.