Minimax Decision Trees & Alpha-Beta Pruning
“Alpha (MAX lower bound) >= Beta (MIN upper bound) triggers immediate subtree cutoff.”
1.Two-Player Zero-Sum Games & The Minimax Principle
§ 3.1.In classical game playing (Chess, Checkers, Go), two adversarial players alternate turns in a zero-sum environment: any advantage gained by player MAX directly corresponds to an equivalent loss for player MIN (U(MAX) + U(MIN) = 0).
The Minimax Equation:
$Minimax(s) = \begin{cases} Utility(s) & if s is terminal \\ \max_{a \in Actions(s)} Minimax(Result(s, a)) & if Player(s) = MAX \\ \min_{a \in Actions(s)} Minimax(Result(s, a)) & if Player(s) = MIN \end{cases}$
Minimax performs a complete depth-first exploration of the game tree. On a game with branching factor b and maximum depth d, standard Minimax evaluates O(b^d) terminal states, which is computationally intractable for complex games (e.g., Chess has b \approx 35, d \approx 80 \implies 35^{80} states).
2.The Alpha-Beta Pruning Algorithm
§ 3.2.Alpha-Beta Pruning computes the exact Minimax decision while pruning entire subtrees that cannot affect the root's decision.
Parameters Maintained Along the Path:
• \alpha (Alpha): The value of the best (highest-value) choice found so far for MAX along the path. Initialized to -\infty.
• \beta (Beta): The value of the best (lowest-value) choice found so far for MIN along the path. Initialized to +\infty.
Cutoff Rule:
As soon as \alpha ≥ \beta at any node, stop searching its remaining children and return immediately!
Intuition: If MAX already has a guaranteed path yielding \alpha = 5, and at a descendant MIN node, MIN has found a move yielding \beta = 3, MAX will never allow play to reach this MIN node (MAX would pick the \alpha=5 alternative earlier). Therefore, evaluating further moves for MIN is completely irrelevant.
3. GATE DA Worked Example: Alpha-Beta Pruning Cutoff Count
Ensure that alpha is updated ONLY at MAX nodes, and beta is updated ONLY at MIN nodes!
Problem (Original Practice Problem · Modeled on GATE DA Pattern):
Consider a 2-ply game tree with root MAX node A having two MIN children B and C:
Node B has leaf children evaluated left-to-right: 3, 5.
Node C has leaf children evaluated left-to-right: 2, 8, 1.
Step 1: At Root A (MAX):
Initializes alpha = -inf, beta = +inf.
Calls MIN child B with (alpha = -inf, beta = +inf).
Step 2: At Left Child B (MIN):
- Evaluates leaf 3: beta = min(+inf, 3) = 3.
- Check cutoff: alpha (-inf) >= beta (3)? No.
- Evaluates leaf 5: beta = min(3, 5) = 3.
- Returns value 3 to Root A.
Step 3: Back at Root A (MAX):
Updates alpha = max(-inf, 3) = 3.
Calls MIN child C with (alpha = 3, beta = +inf).
Step 4: At Right Child C (MIN):
- Inherits alpha = 3, beta = +inf.
- Evaluates first leaf 2: beta = min(+inf, 2) = 2.
- Check Cutoff: alpha (3) >= beta (2) is TRUE! Cutoff occurs immediately!
- Leaves 8 and 1 are PRUNED without being evaluated.
- Node C returns value 2 to Root A.
Step 5: At Root A (MAX):
Root value = max(3, 2) = 3. Best move is to node B.
Conclusion: Root value is 3. Exactly 2 leaf nodes (8 and 1) are pruned.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.