Minimax & Alpha-Beta
In short: when a competitor is also optimising, searching their replies
is a tree: Meridian's bid desk picks a move to maximise the outcome, the
rival picks their reply to minimise it, alternating all the way down to
the leaves. Plain minimax visits every leaf. Alpha-beta pruning keeps two
running numbers — alpha, the best the maximiser can already guarantee, and
beta, the best the minimiser can already guarantee — and the moment
alpha >= beta, the rest of the current node's children can be skipped
entirely: nothing left in that subtree could ever change the parent's
decision. The value found is always identical to plain minimax. Only the
amount of tree actually looked at changes, and how the leaves are
ordered changes that amount a lot.
Why alpha ≥ beta ends the search early
At a MIN node, beta only ever falls as better (lower) replies are found.
The moment beta drops to or below the alpha the MAX parent already has
in hand from an earlier sibling, the parent already has something at least
as good available elsewhere — so this MIN node can never be the parent's
actual choice, no matter what its remaining children turn out to be:
MAX at the root, MIN at L and R, MAX again at LL/LR/RL/RR. Alpha starts at the value the root already has in hand from an earlier branch; the moment it meets or beats beta, the rest of that branch is skipped -- here, all of RR.
LL (a MAX node over leaves 3 and 5) settles at 5. Binary tree, 15 nodes, height 4. Settled: LL.
Plain minimax first, so you know what pruning has to match
Every leaf gets visited here — 9 of them. Alpha-beta pruning, added next, never changes this number. It only changes how many of the 9 it has to look at to be sure of it.
def minimax_with_pruning(node, maximizing, alpha=float("-inf"), beta=float("inf")):
if not isinstance(node, list):
return node
if maximizing:
value = float("-inf")
for child in node:
value = max(value, minimax_with_pruning(child, False, alpha, beta))
alpha = max(alpha, value)
if alpha >= beta:
break
return value
else:
value = float("inf")
for child in node:
value = min(value, minimax_with_pruning(child, True, alpha, beta))
beta = min(beta, value)
if alpha >= beta:
break
return value
a = minimax_with_pruning([[3, 5, 2], [9, 1, 0], [7, 4, 8]], True)
b = minimax_with_pruning([[7, 4, 8], [9, 1, 0], [3, 5, 2]], True)
print(a, b)Move ordering changes the search, not the answer
Put the strongest-looking branch first and alpha rises fast, which makes
later siblings easy to cut. Put it last and the search has to do almost
everything before it finds a reason to stop:
This prints 0.0 instead of 0.1111. Add the cutoff: `if alpha >= beta: break`, in both branches.
Quick practice
tree = [[1, 2], [3, 4]]
print(len([x for group in tree for x in group]))alpha, beta = 5, 3
print(alpha >= beta)🎯 Your turn
Build best_counter_bid(tree). tree is a nested list game tree: a leaf is
a number, an internal node is a list of children, and the root always
maximises. Run minimax with alpha-beta pruning and return
{"value": ..., "nodes_visited": ..., "nodes_pruned": ..., "total_leaves": ...},
where nodes_pruned counts every leaf under a subtree that was skipped.
best_counter_bid([[3,5,2],[9,1,0],[7,4,8]])→ value4,8visited,1pruned,9total leaves.
Hint: thread alpha and beta through the recursion; at a max node
raise alpha, at a min node lower beta, and the instant alpha >= beta,
stop looping over that node's remaining children — but still add up the
leaves underneath each one you skip.
Press ▶ Run, try the Live App chips, then ✓ Check.