Alpha-Beta Pruning

Skip branches that cannot matter

Alpha-beta pruning keeps track of the best value each player is already guaranteed (alpha for max, beta for min). When a branch cannot possibly change the final decision, it stops exploring it. The result is exactly the same as minimax, but with good move ordering it can search roughly twice as deep in the same time. Combined with evaluation functions, iterative deepening and opening books, this was the core of classic chess engines like Deep Blue.

Minimax versus alpha-beta node counts, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. From a position after X and O have each played once, plain minimax visits 7,332 nodes and alpha-beta visits 844, a nearly 9x saving, and both return the same value (0, a draw).

import math
LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(b):
    for a, c, d in LINES:
        if b[a] != "." and b[a] == b[c] == b[d]: return b[a]
def moves(b): return [i for i, ch in enumerate(b) if ch == "."]
def play(b, i, p): return b[:i] + p + b[i + 1:]
count = {"minimax": 0, "alphabeta": 0}
def mm(b, p):
    count["minimax"] += 1
    w = winner(b)
    if w: return 1 if w == "X" else -1
    if not moves(b): return 0
    vals = [mm(play(b, i, p), "O" if p == "X" else "X") for i in moves(b)]
    return max(vals) if p == "X" else min(vals)
def ab(b, p, alpha=-math.inf, beta=math.inf):
    count["alphabeta"] += 1
    w = winner(b)
    if w: return 1 if w == "X" else -1
    if not moves(b): return 0
    if p == "X":
        v = -math.inf
        for i in moves(b):
            v = max(v, ab(play(b, i, p), "O", alpha, beta)); alpha = max(alpha, v)
            if alpha >= beta: break
        return v
    v = math.inf
    for i in moves(b):
        v = min(v, ab(play(b, i, p), "X", alpha, beta)); beta = min(beta, v)
        if alpha >= beta: break
    return v
start = "X...O...."
print("minimax value   :", mm(start, "X"), "| nodes visited", count["minimax"])
print("alpha-beta value:", ab(start, "X"), "| nodes visited", count["alphabeta"])

Output:

minimax value   : 0 | nodes visited 7332
alpha-beta value: 0 | nodes visited 844

Order moves well

Trying the most promising moves first (captures, previously best moves) lets alpha-beta prune far more.

त्वरित जाँच: How does alpha-beta's result compare with minimax?

• It searches more nodes
• It is always less accurate
• It returns the same value while visiting fewer nodes
• It ignores the opponent