Alpha-Beta Pruning

The algorithm maintains two values that represent the current best-known scores for each player along the search path.

• Alpha (α): The minimum score that the maximizing player is assured of. It starts at negative infinity and can only increase.
• Beta (β): The maximum score that the minimizing player is assured of. It starts at positive infinity and can only decrease.

These values are passed down the tree during recursive search, creating a window of possible scores. If a node's evaluation falls outside this window, its branch is pruned.

Pruning occurs when the algorithm proves that exploring a branch is futile. The core logic is:

• Alpha Cutoff (at a Min Node): If the minimizing player finds a move with a value ≤ α, they can stop. The maximizing player above already has a better guaranteed option, so this branch is irrelevant.
• Beta Cutoff (at a Max Node): If the maximizing player finds a move with a value ≥ β, they can stop. The minimizing player above will never allow a path that leads to such a high score for the opponent.

This is often summarized as: stop searching when value ≥ β (for Max) or value ≤ α (for Min).

Alpha-Beta Pruning is not a standalone search but an enhancement to depth-first minimax. It traverses the game tree recursively, evaluating leaf nodes with a heuristic function.

The key is that it performs a depth-first search while propagating the α and β bounds. As it backtracks, it updates these bounds. This ordered, depth-first exploration is essential because effective pruning depends on finding good moves early to tighten the α-β window quickly.

The efficiency of Alpha-Beta Pruning is highly dependent on the order in which moves (child nodes) are examined.

• Best-Case Scenario: If the best move is always evaluated first, the algorithm prunes the maximum number of branches. In a perfectly ordered tree, it evaluates only O(b^(d/2)) nodes instead of O(b^d) for full minimax, effectively searching twice as deep in the same time.
• Common Ordering Heuristics:
  • Use a simple static evaluation to sort moves.
  • Implement a Transposition Table to cache and recall previously seen board states and their values.
  • Use Killer Heuristics—prioritize moves that caused cutoffs in other branches at the same depth.

A common, elegant implementation of Alpha-Beta Pruning uses the Negamax framework. This formulation simplifies the code by always maximizing the negated value from the perspective of the current player.

The core recursive function signature becomes: function negamax(node, depth, alpha, beta, color) Where color is +1 for one player and -1 for the other. The alpha-beta condition simplifies to a single check: if value >= beta, trigger a cutoff. The values alpha and beta are negated and swapped on recursive calls.

Alpha-Beta Pruning is a specific instance of branch-and-bound optimization applied to the minimax algorithm. Its principles relate to broader search concepts:

• Constraint Satisfaction: The α-β window acts as a dynamic constraint that prunes invalid solution spaces.
• Adversarial Search: It is the foundational optimization for perfect-information, two-player zero-sum games like Chess and Go (used within Monte Carlo Tree Search for classical evaluation).
• Heuristic Guidance: While it prunes, it still relies on a heuristic evaluation function at leaf nodes or depth limits to estimate board value, making the quality of the heuristic critical for strong play.

The foundational adversarial search algorithm that Alpha-Beta optimizes. Minimax operates on a zero-sum game assumption, where one player's gain is the other's loss.

• It recursively explores a game tree to a specified depth.
• At maximizer nodes, it chooses the move leading to the highest evaluation.
• At minimizer nodes, it chooses the move leading to the lowest evaluation.
• The final output is the optimal move assuming perfect play from the opponent. Alpha-Beta Pruning dramatically accelerates Minimax by eliminating irrelevant branches.

A general technique for reducing the size of a search tree by permanently discarding branches that cannot affect the final decision. Alpha-Beta is a specific, sound pruning method.

• Sound Pruning: Guarantees the result is identical to an exhaustive search (e.g., Alpha-Beta).
• Unsound Pruning: May sacrifice optimality for speed (e.g., futility pruning in chess engines).
• The core principle is branch elimination based on established bounds, which is critical for searching deep into complex game trees or planning horizons.

A simplified implementation of the Minimax algorithm commonly used in practice. It leverages the zero-sum property to use a single, unified evaluation function.

• The same recursive function is called for both players, with the evaluation score negated at each recursion level.
• This eliminates the need for separate max and min functions, streamlining code.
• Alpha-Beta Pruning integrates seamlessly with Negamax, using a single alpha-beta bound pair that is negated and swapped between recursive calls.

The evaluation function that estimates the utility of a game or search state. It is the computational engine guiding both Minimax and Alpha-Beta.

• Provides a static score for non-terminal nodes where the full search is truncated.
• A well-designed heuristic is critical: Alpha-Beta's pruning efficiency depends heavily on exploring the best moves first (move ordering).
• In chess, a simple heuristic may count material (pawn=1, knight=3, etc.). In agent planning, it could estimate the cost-to-goal.

A probabilistic, best-first search algorithm that represents a different paradigm from depth-first, exhaustive methods like Minimax/Alpha-Beta.

• Builds a search tree asymmetrically, focusing on more promising nodes.
• Uses random simulations (playouts) to estimate node value, rather than a deterministic heuristic.
• Does not require a hand-crafted evaluation function, making it versatile for games with complex states (e.g., Go).
• Modern engines often hybridize MCTS with shallow Alpha-Beta search for tactical precision.

A search strategy that performs a series of depth-limited searches, incrementally increasing the depth limit. It is frequently combined with Alpha-Beta Pruning.

• Provides a natural framework for move ordering: the results of a shallow search (which is fast) inform the move ordering for the next, deeper search.
• This improved ordering dramatically increases the number of branches Alpha-Beta can prune.
• Ensures the algorithm can provide a best move within any time constraint, as it completes each depth fully before proceeding.