Alpha-Beta Pruning

In the previous lesson, we learned about the Minimax algorithm and how it helps an intelligent agent make decisions in competitive environments. While Minimax works correctly, it becomes very slow as the game tree grows.

Alpha-Beta Pruning is an optimization technique that makes Minimax faster without changing the final decision.

Why Do We Need Alpha-Beta Pruning?

Minimax evaluates every possible move in the game tree. In real-world games like chess, this means millions of positions.

Most of these positions are unnecessary to evaluate because some moves are already worse than previously examined options.

Alpha-Beta Pruning removes these unnecessary branches and saves computation time.

Real-World Connection

Alpha-Beta Pruning reflects how humans make decisions.

• We stop considering bad options once we find a better one
• We do not analyze every possibility if the outcome is already worse
• We focus only on promising choices

This idea is used not only in games, but also in decision-making systems and optimization problems.

What Are Alpha and Beta?

Alpha-Beta Pruning keeps track of two values:

• Alpha: The best value that the MAX player can guarantee so far
• Beta: The best value that the MIN player can guarantee so far

When the algorithm finds that a branch cannot improve the current result, it stops exploring that branch.

How Pruning Works (Concept)

During tree traversal:

• If MAX finds a value greater than or equal to Beta, it stops searching further
• If MIN finds a value less than or equal to Alpha, it stops searching further

This avoids evaluating branches that will never affect the final decision.

Alpha-Beta Pruning Algorithm (Python)

Below is a simple Python implementation of Alpha-Beta Pruning based on Minimax.

def alphabeta(depth, alpha, beta, is_maximizing):
    if depth == 0:
        return 1
    if depth == 1:
        return -1
    if depth == 2:
        return 0

    if is_maximizing:
        best = -float("inf")
        for _ in range(2):
            value = alphabeta(depth - 1, alpha, beta, False)
            best = max(best, value)
            alpha = max(alpha, best)
            if beta <= alpha:
                break
        return best
    else:
        best = float("inf")
        for _ in range(2):
            value = alphabeta(depth - 1, alpha, beta, True)
            best = min(best, value)
            beta = min(beta, best)
            if beta <= alpha:
                break
        return best

print(alphabeta(3, -float("inf"), float("inf"), True))
  

Code Explanation

This algorithm works similarly to Minimax but with pruning added.

• alpha tracks the best value for MAX
• beta tracks the best value for MIN
• Branches are skipped when further evaluation cannot improve results

The pruning does not change the answer — it only avoids unnecessary calculations.

Output Explanation

The output 0 means that, with optimal play from both sides, the game ends in a draw.

Compared to Minimax, Alpha-Beta reaches this result faster by skipping useless branches.

Benefits of Alpha-Beta Pruning

• Much faster than plain Minimax
• Same accuracy and decisions
• Scales better for larger games

With good move ordering, Alpha-Beta can reduce the number of evaluated nodes dramatically.

Where Alpha-Beta Is Used

• Chess engines
• Checkers and board games
• Game AI in video games
• Strategic decision systems

It is one of the most important algorithms in classical game-playing AI.

Practice Questions

Quick Quiz

Coming up next: Logic in AI — how machines represent facts, rules, and reasoning.