Pruning

Branch and Bound is a general algorithm for combinatorial optimization problems (e.g., Traveling Salesperson, Knapsack). It systematically enumerates candidate solutions via a state-space tree (branching) while using calculated bounds to discard entire subtrees (bounding).

Key mechanisms:

• Upper/Lower Bounds: For a minimization problem, a lower bound is computed for each node (e.g., a relaxed version of the problem). If this bound is worse than the best complete solution found so far (the incumbent), the entire subtree is pruned.
• Incumbent Solution: The best complete solution found during the search provides a global benchmark for pruning.

This technique transforms an exhaustive search with complexity O(n!) into a tractable problem for many real-world instances, as vast regions of the solution space are eliminated early.

Constraint Propagation is a family of inference techniques used in Constraint Satisfaction Problems (CSPs) like scheduling, configuration, or Sudoku. It prunes the search space by using the problem's constraints to eliminate values from variable domains that cannot participate in any valid solution.

Core algorithms include:

• Arc Consistency (AC-3): Ensures that for every value in a variable's domain, there exists a compatible value in the domain of every connected variable. Inconsistent values are removed.
• Forward Checking: During search, after a variable is assigned, it immediately prunes inconsistent values from the domains of its unassigned neighbors.

This is a form of pruning at the domain level, drastically reducing the branching factor before the search algorithm even begins to explore specific value assignments.

Transposition Table Pruning uses memoization to avoid re-evaluating identical game states (transpositions) that can be reached via different sequences of moves. It is critical in games like chess or checkers.

Mechanism:

• A large hash table stores previously evaluated states along with their computed score, depth of search, and type of score (exact, lower bound, upper bound).
• When the search encounters a state, it checks the table. If an entry exists with a search depth greater than or equal to the current required depth, the stored value is used, pruning the entire subtree below that node.

This technique provides massive speedups, as it effectively reuses computation across different branches of the search tree, turning a tree search into a more efficient graph search.

Null-Move Pruning is a heuristic pruning technique based on the observation that in most game positions, making a move is better than passing. It allows the search to assume the opponent gets two moves in a row to quickly identify hopeless positions.

Process:

1. At a node, the side to move is allowed to 'pass' (make a null move).
2. The search then proceeds for the opponent with a reduced depth (e.g., depth-2).
3. If the resulting score is still good enough to cause a beta-cutoff (i.e., the position is strong even after passing), the original node is pruned, as making an actual move would presumably be even better.

This is a probabilistic pruning method; it can occasionally prune a critical line (the 'zugzwang' case where passing is a disadvantage), so it requires careful implementation, often with verification searches.

These are forward-looking, evaluation-driven pruning heuristics commonly used in modern chess engines.

• Futility Pruning: Near the leaves of the search tree, if the current static evaluation of a position is so poor that even the best possible capture cannot raise it above the alpha bound, the remaining moves at that node are pruned. It operates on the assumption that 'quiet' moves (non-captures) are unlikely to dramatically change the evaluation.
• Late Move Reductions (LMR): Based on the observation that moves ordered later in the search (after good captures and killer moves) are less likely to be best. The search depth for these late moves is significantly reduced (e.g., from depth 8 to depth 5). If the shallow search returns a surprisingly good score, a re-search at full depth is triggered. This safely prunes a vast number of unpromising lines while preserving accuracy.

Together, these techniques enable modern engines to search billions of positions per second by focusing computation on the most critical variations.