Alpha-Beta Pruning

Two implementation points that decide correctness.

The cutoff is checked before alpha or beta is updated, and with >= rather than >. Using strict inequality still gives the right value but prunes less.

Alpha and beta are passed down, never up. What travels up is the node's value. A version that assigns to a shared global alpha prunes wrongly, and it is the commonest bug in a student implementation.

It running, on the same tree as minimax

# Alpha-beta pruning on the SAME tree as the minimax chapter, so the saving can
# be counted. alpha is the best value MAX can already guarantee anywhere above;
# beta is the best MIN can already guarantee. A node stops as soon as it cannot
# affect the value above it.
TREE = ["MAX", [
    ["MIN", [3, 12, 8]],
    ["MIN", [2, 4, 6]],
    ["MIN", [14, 5, 2]],
]]

INF = float("inf")
examined = []

def show(v):
    return "-inf" if v == -INF else ("+inf" if v == INF else "%d" % v)

def alphabeta(node, alpha, beta, depth=0):
    pad = "  " * depth
    if isinstance(node, int):
        examined.append(node)
        print("%sleaf %2d" % (pad, node))
        return node
    player, children = node
    if player == "MAX":
        value = -INF
        for i, child in enumerate(children):
            value = max(value, alphabeta(child, alpha, beta, depth + 1))
            if value >= beta:
                print("%sCUT: MAX has %d >= beta %s, skipping %d sibling(s)"
                      % (pad, value, show(beta), len(children) - i - 1))
                return value
            alpha = max(alpha, value)
        print("%sMAX = %2d   alpha = %s" % (pad, value, show(alpha)))
        return value
    value = INF
    for i, child in enumerate(children):
        value = min(value, alphabeta(child, alpha, beta, depth + 1))
        if value <= alpha:
            print("%sCUT: MIN has %d <= alpha %s, skipping %d sibling(s)"
                  % (pad, value, show(alpha), len(children) - i - 1))
            return value
        beta = min(beta, value)
    print("%sMIN = %2d   beta = %s" % (pad, value, show(beta)))
    return value

best = alphabeta(TREE, -INF, INF)
print()
print("value of the root:", best, " and minimax gave 3 on the same tree")
print("terminals examined:", len(examined), examined)
print("minimax examined 9, so", 9 - len(examined), "were never looked at")

    leaf  3
    leaf 12
    leaf  8
  MIN =  3   beta = 3
    leaf  2
  CUT: MIN has 2 <= alpha 3, skipping 2 sibling(s)
    leaf 14
    leaf  5
    leaf  2
  CUT: MIN has 2 <= alpha 3, skipping 0 sibling(s)
MAX =  3   alpha = 3

value of the root: 3  and minimax gave 3 on the same tree
terminals examined: 7 [3, 12, 8, 2, 14, 5, 2]
minimax examined 9, so 2 were never looked at

The value is 3, exactly as minimax gave, and two terminals were never looked at. Follow the one interesting moment.

The first branch is examined in full. Nothing has been established yet, so alpha is minus infinity and there is nothing to prune against. Its three terminals give MIN a value of 3, and the root's alpha rises to 3: MAX can now guarantee 3.

The second branch is cut after ONE terminal. Its first terminal is 2. This is a MIN node, so its value can only fall from 2; and 2 is already at or below alpha, which is 3. So MAX will never choose this branch, and the 4 and the 6 are never examined. Whatever they were, even a thousand, this MIN node could not exceed 2.

The third branch is examined in full and is cut on its last child, which saves nothing here but is the same rule firing. Its terminals 14, 5 and 2 drive its value down to 2, which reaches alpha at the last moment.

Move ordering decides everything

The saving above is two nodes out of nine, which is small, and it is small because of the order the branches happened to be in. That is the most important practical fact about alpha-beta and it is measurable.

# Move ordering decides how much alpha-beta saves. Same nine leaf values, all six
# orderings of the three branches, with the leaves examined counted each time.
# Then the best case in theory, which is what a chess program is chasing.
INF = float("inf")

def alphabeta(node, alpha, beta, count):
    if isinstance(node, int):
        count[0] += 1
        return node
    player, children = node
    if player == "MAX":
        value = -INF
        for child in children:
            value = max(value, alphabeta(child, alpha, beta, count))
            if value >= beta:
                return value
            alpha = max(alpha, value)
        return value
    value = INF
    for child in children:
        value = min(value, alphabeta(child, alpha, beta, count))
        if value <= alpha:
            return value
        beta = min(beta, value)
    return value

BRANCH = {"A": ["MIN", [3, 12, 8]], "B": ["MIN", [2, 4, 6]], "C": ["MIN", [14, 5, 2]]}
print("order   value   leaves examined of 9")
for order in ("ABC", "ACB", "BAC", "BCA", "CAB", "CBA"):
    count = [0]
    value = alphabeta(["MAX", [BRANCH[k] for k in order]], -INF, INF, count)
    print("  %s       %d           %d" % (order, value, count[0]))

print()
print("in theory, with b moves at each of d levels:")
print("  d   plain minimax   alpha-beta, worst   alpha-beta, best")
for b, d in ((3, 4), (3, 6), (30, 4), (30, 6), (30, 10)):
    plain = b ** d
    best = b ** (d // 2) * 2 - 1 if d % 2 == 0 else b ** ((d + 1) // 2) + b ** (d // 2) - 1
    print("b=%2d d=%2d %14d %19d %18d" % (b, d, plain, plain, best))
print()
print("the best case examines about b**(d/2) nodes instead of b**d, which is the")
print("same as searching TWICE AS DEEP for the same work. Shannon 1950 measured")
print("about 30 legal moves in a typical chess position, so b = 30 is his figure.")

order   value   leaves examined of 9
  ABC       3           7
  ACB       3           7
  BAC       3           9
  BCA       3           9
  CAB       3           7
  CBA       3           7

in theory, with b moves at each of d levels:
  d   plain minimax   alpha-beta, worst   alpha-beta, best
b= 3 d= 4             81                  81                 17
b= 3 d= 6            729                 729                 53
b=30 d= 4         810000              810000               1799
b=30 d= 6      729000000           729000000              53999
b=30 d=10 590490000000000     590490000000000           48599999

the best case examines about b**(d/2) nodes instead of b**d, which is the
same as searching TWICE AS DEEP for the same work. Shannon 1950 measured
about 30 legal moves in a typical chess position, so b = 30 is his figure.

Every ordering returns 3, which is the correctness claim: pruning cannot change the answer.

The work varies from 7 to 9 out of 9. The two orderings that examine everything are the ones beginning with branch B, whose MIN value is 2: starting with a weak branch sets alpha low, and a low alpha prunes nothing. The rule that follows is the practical one: try the best-looking move first.

The theoretical table is the reason this matters. In the worst order alpha-beta examines every node and saves nothing at all, O(bd). In the best order it examines about b(d/2), which at b of 30 and d of 10 is 48 million instead of 590 thousand million: about twelve thousand times less work.

And the right way to state that saving is Shannon's way: b(d/2) instead of bd means the same work buys twice the depth. A chess program that could see five moves ahead can now see ten, and depth is strength.

How the ordering is actually obtained

Worth one paragraph, because "try the best move first" is circular: knowing which move is best is the problem being solved.

Real programs approximate it, and three techniques are standard. Cheap static rules: in chess, try captures and checks before quiet moves. Iterative deepening: search to depth 1, then 2, then 3, and at each new depth try the moves in the order the previous depth preferred. That is the same iterative deepening as in the uninformed row, used here for a completely different purpose, and it is why chess programs are built on it. Remembering: a transposition table stores the value found for a position, so a position reached by a different order of moves is not searched again.

Its properties

The random-ordering figure is the standard published result and this book has not measured it, so it is given as the known figure rather than as a measurement of ours. What this book does measure is the six orderings above.

Distinctions

What it does not mean

Alpha-beta does not change the answer. It returns the minimax value exactly. Any implementation that returns something else is wrong.

It is not a different algorithm from minimax. It is minimax with two bounds carried down and an early return.

alpha is not "the value of the current node". It is the best MAX can guarantee anywhere on the path above, which is why it is inherited and not computed locally.

Pruning does not always save anything. In the worst ordering it examines every node. Two of the six orderings measured above save nothing.

The best case is not typical. It requires the best move examined first at every node, which is exactly what is not known. Programs approximate it with static rules, iterative deepening and transposition tables.

Twice as deep is not twice as good in a trivial sense. It means the same computation reaches twice the depth, and since strength grows with depth, that is where the practical gain lies.

Quick revision

• Alpha-beta pruning returns exactly the minimax value while examining fewer nodes.
• alpha: the best MAX can already guarantee above; starts at minus infinity, only rises. beta: the best MIN can already guarantee; starts at plus infinity, only falls.
• Cut at a MIN node when its value is alpha or less; at a MAX node when its value is beta or more. The reasoning is about the parent's choice, not this node's quality.
• Bounds pass down; values pass up. A shared global alpha is the classic bug.
• On the standing tree: value 3, 7 terminals against minimax's 9. The second branch is cut after one terminal, because 2 is already at or below alpha of 3 and a MIN value can only fall.
• Move ordering decides everything. Measured over all six orderings: 7, 7, 9, 9, 7, 7 of 9. The two that save nothing begin with the weakest branch.
• Worst order O(bd), no saving. Best order O(b(d/2)), which at b of 30 and d of 10 is 48 million against 590 thousand million. The same work buys twice the depth.
• Ordering is approximated by static rules, iterative deepening reusing the previous depth's preference, and a transposition table.

Test yourself

1. Define alpha and beta. alpha is the value of the best choice found so far for MAX at any point along the current path from the root; it begins at minus infinity and only increases. beta is the best found so far for MIN along that path; it begins at plus infinity and only decreases.

2. Give both cutoff conditions and justify one of them. A MIN node stops when its value is alpha or less; a MAX node stops when its value is beta or more. For the first: a MIN node's value can only fall as more children are examined, it is already at or below a value MAX can obtain elsewhere, so MAX will never choose this branch and the remaining children cannot matter.

3. On the standing tree, why is the second branch cut after a single terminal? Its first terminal is 2. The node is a MIN node, so its value can only fall below 2, and alpha is already 3 from the first branch. MAX can guarantee 3 elsewhere, so it will never choose a branch worth at most 2, and the remaining two terminals are irrelevant.

4. Does pruning ever change the value returned? What does it change? Never. It returns exactly the minimax value. It changes only the number of nodes examined.

5. State the best and worst case time complexities and what determines which you get. Worst case O(bd), the same as plain minimax, with no saving. Best case O(b(d/2)). Which you get is determined entirely by the order in which moves are examined at each node; the best case needs the best move examined first everywhere.

6. Why is "try the best move first" circular, and how do real programs get round it? Because identifying the best move is the problem being solved. Programs approximate the order with cheap static rules such as trying captures first, with iterative deepening that reuses the previous shallower search's preferred order, and with a transposition table that remembers values already computed for a position.

7. Express the best-case saving in the way that shows why it matters in practice. Examining about b(d/2) nodes instead of bd means the same amount of work reaches twice the depth. Since playing strength grows with search depth, alpha-beta roughly doubles the depth a program can reach, which at Shannon's branching figure of 30 and a depth of 10 is 48 million nodes instead of 590 thousand million.