Math
Game tree and alpha-beta
A game tree where every block is as tall as its value: a MAX node stands as high as its tallest child, a MIN node as low as its lowest. Minimax looks at every leaf; alpha-beta skips what cannot change the answer, and how much it skips depends on the order of the moves.
What happens
Every block is as tall as its value, so the rule is visible before it is named: a MAX node stands as high as its tallest child, a MIN node as low as its lowest, and the root is the value of the game. Minimax reads all b^d leaves. Alpha-beta reads them in order and stops looking at a node the moment a sibling already seen makes the rest irrelevant - the branches it never enters stay dark. The answer is never changed by this, only the count is, and the count depends on the ORDER of the moves, not on the tree: with the best move first at every node it needs exactly the Knuth-Moore minimum, about the square root of b^d; with the worst move first it sees every leaf - but only to depth 3, because from depth 4 the alpha raised at the root reaches down and prunes even that. What to watch: the pruned branches, the gold path of the principal variation, and the three bars behind - minimax, this search, the minimum.
Equations used in the module
Equations MAX node: v = max over children; MIN node: v = min over children; minimax reads all b^d leaves alpha-beta: cut the rest of a node's children as soon as alpha >= beta - the answer is the same, the count is not perfect ordering: N_min = 2·b^(d/2) − 1 for even d, b^((d+1)/2) + b^((d−1)/2) − 1 for odd d (Knuth - Moore, 1975) worst ordering at every node: N = b^d for d <= 3; from d = 4 the root's alpha reaches the third level and prunes anyway ordering s in [−1, 1]: a node's children are sorted by exact value when its own hash coin is below |s| - best first for s > 0, worst first for s < 0
