✂️Alpha-Beta Pruning

NEW

A technique reducing nodes evaluated in minimax by pruning branches.

DESCRIPTION

Alpha-beta pruning accelerates minimax by maintaining bounds (alpha, beta) that determine whether subtrees can affect the final decision. With good move ordering, it can reduce complexity from b^d to roughly b^(d/2). It guarantees the same result as full minimax. Widely used in board game engines, it often pairs with iterative deepening, transposition tables, and heuristics.

ALTERNATIVE DEFINITIONS

UC Berkeley

Alpha-Beta pruning reduces the number of nodes evaluated by the minimax algorithm by pruning branches that cannot possibly influence the final decision.

Clarifies pruning criterion as non-influential branches.

Source

Stanford University

By tracking alpha and beta bounds, we can avoid exploring parts of the game tree that cannot change the minimax value.

Emphasizes bound tracking as the mechanism for pruning.

Source

RELATED TERMS

Minimax Game Tree Heuristic Evaluation Transposition Table Move Ordering Branch and Bound Adversarial Search Search Depth Threshold Expectimax

COMPETING TERMS

Monte Carlo Tree Search

RELATIONS

• Broader: Pruning
• Derived from: Minimax

KNOWLEDGE AREAS

AI Mathematics

TARGET AUDIENCE

AI Engineer Software Developer Data Scientist

EXTERNAL SOURCES

• Wikipedia - Alpha–beta pruning
• Chess Programming Wiki - Detailed alpha-beta techniques
• MIT OpenCourseWare - Game search lecture with pruning

TOP QUESTIONS

How does Alpha-Beta Pruning guarantee the same result as Minimax?

It prunes only branches that cannot affect the minimax value, preserving optimality under correct bounds and evaluation.

Category: Definition

Why is move ordering critical for Alpha-Beta Pruning?

Good ordering increases early cutoffs, drastically reducing evaluated nodes and improving performance.

Category: Requirements

What is the impact of Alpha-Beta Pruning on complexity?

With ideal ordering, effective branching can approach b^(d/2), enabling deeper searches.

Category: Example

What are common mistakes when implementing Alpha-Beta Pruning?

Incorrect bound updates or evaluation reuse can cause missed cutoffs or wrong results. Test carefully.

Category: Mistakes

Can Alpha-Beta Pruning be combined with transposition tables?

Yes. Cached evaluations and bounds prevent redundant work and improve cutoffs.

Category: Topic

Does Alpha-Beta Pruning help in stochastic games?

Expectiminimax variants exist, but pruning is less effective without strong ordering and deterministic payoffs.

Category: Opinion

What risks arise with shallow cutoffs?

Over-pruning from bad heuristics or bounds can miss critical lines, degrading play strength.

Category: Risks

Is Alpha-Beta Pruning outdated?

No. It remains vital in classic engines, though MCTS dominates in large, complex domains.

Category: Relevancy

How to visualize Alpha-Beta Pruning?

Use a game tree with alpha and beta bounds highlighting cut branches; track updates at each node.

Category: Example