AlphaBeta

Strong vs. Weak Methods in Game AI

In game AI, Strong Methods leverage specific knowledge of a particular game's structure (e.g., chess openings, Go patterns). Weak Methods, like Minimax and Alpha-Beta Pruning, are general-purpose algorithms that can apply to any two-player zero-sum game without deep domain knowledge, relying on search and evaluation.

Reducing Search via Symmetry

Search space can be limited by exploiting symmetry in the game state. For example, in tic-tac-toe, many board positions are rotationally or reflectionally equivalent. A strong method would recognize these as identical, avoiding redundant expansion of multiple branches leading to the same strategic situation.

Alpha-Beta Pruning: Core Idea

Alpha-Beta Pruning is an optimization of the Minimax algorithm. It performs a depth-first search of the game tree but prunes (discards) branches that cannot possibly influence the final decision, allowing it to achieve the same result as Minimax while exploring far fewer nodes.

Alpha Parameter (α)

In Alpha-Beta, Alpha (α) is a value associated with MAX nodes. It represents the lower bound on the node's value—the minimum score that MAX is already guaranteed to achieve from the current search path so far. The value of α never decreases as the search progresses at a MAX node.

Beta Parameter (β)

In Alpha-Beta, Beta (β) is a value associated with MIN nodes. It represents the upper bound on the node's value—the maximum score that MIN is already guaranteed to allow (i.e., the worst outcome for MAX that MIN can enforce) on that branch. The value of β never increases as the search progresses at a MIN node.

Alpha-Beta Process: Initialization & Value Passing

The process starts at the root with α = -∞ and β = +∞. These α and β values are passed down to child nodes during recursive search. Each node inherits the current bounds from its parent, which represent the best options found so far for the ancestors.

Alpha-Beta Process at a MAX Node

At a MAX node: 1) Evaluate children. 2) For each child's returned value, update α = max(α, child_value). 3) After updating, check if α ≥ β. If true, a beta cutoff occurs: prune (stop evaluating) the remaining children of this MAX node, as MIN (the parent) would never allow this path.

Alpha-Beta Process at a MIN Node

At a MIN node: 1) Evaluate children. 2) For each child's returned value, update β = min(β, child_value). 3) After updating, check if β ≤ α. If true, an alpha cutoff occurs: prune the remaining children of this MIN node, as MAX (the parent) would never choose this path.

Pruning Condition (Alpha ≥ Beta)

Pruning occurs when α ≥ β. This means the current node has found a move that is already too good for the parent node's opponent. The opponent (at the parent level) would never let the game reach this node because they have a better (for them) option elsewhere, so further search here is wasted.

Alpha-Beta vs. Minimax: Correctness & Complexity

Correctness: Alpha-Beta is guaranteed to return the exact same value as full Minimax. Complexity: In the worst case (poor move ordering), it is O(b^d), like Minimax. With optimal child ordering (best moves first), complexity improves to O(b^(d/2)), effectively allowing it to search twice as deep as Minimax in the same time.

Key Insight of Alpha-Beta Pruning

The key insight is: If we find a move for the current player that is worse than a move we already know the opponent can force at a higher level, we can stop searching that branch. The opponent will steer the game away from this line, making further analysis pointless.