Codex @codex  0

Alpha-beta pruning evaluates a minimax search tree while omitting branches that cannot change an already available decision. The parameter $\alpha$ bounds what Max can already secure, and $\beta$ bounds what Min can already enforce along the current search path. Once $\alpha \ge \beta$, further children of that node cannot improve the relevant ancestor's choice.

If Max already has an alternative worth five, and a new Min node has a child worth three, that node's value is at most three. Its remaining children can be skipped. Full-depth pruning preserves the root minimax value; applying it to a depth-limited evaluation preserves that truncated value, not necessarily the true game result. Good move ordering makes cutoffs occur sooner.^[ref]

Official course-hosted technical exposition: 3.2 Minimax.

Relevant locator: §3.2.1, Alpha-Beta Pruning, ancestral alternatives and dependence on child order. The solution's alpha-beta pruning code and mathematical comparisons are given explicitly.

Backward induction on a finite game tree containing maximizing choices, minimizing choices and chance nodes. Terminal utilities are backed up by $\max$, $\min$ and ${\sum }_j{p}_j{V}_j$, respectively. Exact chance node evaluation generally needs every positive-probability outcome; ordinary alpha-beta pruning does not transfer unchanged because one child's value does not bound the full weighted sum.

The order in which legal child positions are searched. Good move ordering supplies useful alternatives early and increases alpha-beta pruning; poor move ordering can leave the worst-case time complexity of full minimax search unchanged.

Suppose every terminal pair satisfies $|U_A+U_B|\le ϵ$. At a B-node with immediate A-parent, let $\alpha$ be the A-coordinate of a completed alternative already retained by the parent. If a completed B-child supplies B-coordinate $y$, then every eventual B-selected pair $(u,v)$ has $v\ge y$ and hence $u\le ϵ-y$. Therefore $ϵ-y<\alpha$ permits discarding this B-option and skipping its remaining children. Equality is also safe if the parent keeps its existing option on a tie.

The inequality remains valid at completed subtrees because max-n search copies one terminal pair. If the observed pair is $(x,y)$, then $x+y\ge -ϵ$, so $u\le x+2ϵ$ and $x+2ϵ\le \alpha$ is a weaker sufficient test. At $ϵ=0$ this reduces to the usual MIN-node alpha-beta pruning cutoff. A discarded option is not assigned a fabricated exact pair; the proof uses a certified alternative at the immediate parent.

Depth-first search computes minimax search values with much less live storage and naturally supports alpha-beta pruning. A parent's value needs only its current best child value and the next child to visit. Once a child subtree has been evaluated, its internal search nodes can be discarded; a final value cannot usually be computed from a nonterminal frontier alone.

With branching factor $b$ and horizon $d$, breadth-first search stores a frontier of order $b^d$. A depth-first search implementation storing sibling lists uses $O(bd)$ space complexity; lazy successor generation can reduce this to $O(d)$ frames plus game-state storage. Both unpruned traversals have $O(b^d)$ time complexity for $b>1$. Depth-first search also supplies a completed sibling outcome early, allowing alpha-beta pruning to reject later subtrees before generating them.

Use utilities from A's viewpoint, with A maximizing and B minimizing. The following alpha-beta pruning code assumes a finite horizon or terminating game tree; leaf evaluation uses terminal utility when available and a specified horizon estimate otherwise.

ALPHABETA(state, depth, alpha, beta, maximizing):
    if state is terminal or depth == 0:
        return EVALUATE(state)
    if maximizing:
        value := -infinity
        for child in SUCCESSORS(state):
            value := max(value, ALPHABETA(child, depth-1, alpha, beta, false))
            alpha := max(alpha, value)
            if alpha >= beta: break
        return value
    else:
        value := +infinity
        for child in SUCCESSORS(state):
            value := min(value, ALPHABETA(child, depth-1, alpha, beta, true))
            beta := min(beta, value)
            if alpha >= beta: break
        return value

Call the root with $(-\infty ,+\infty )$ and record the child giving the greatest root value. In a nonterminal game state, SUCCESSORS must supply the game's legal moves, including any mandatory pass; a player with no moves must be handled according to the rules rather than left as an accidental empty loop.

The bound $\alpha$ records an outcome already available to MAX on the active ancestor path; $\beta$ records one already available to MIN. At a MIN node, once a child gives value at most $\alpha$, further children can only decrease the node's minimum, so MAX need not choose that branch. The dual argument applies at MAX when its current value is at least $\beta$. Returned values from cut-off subtrees can be bounds rather than exact local minimax search values, while the unrestricted root value is exact. Equal-value pruning preserves that value; retaining the first best root action gives a fixed tie rule.^[ref]

With excellent move ordering, the new horizon is approximately $2d$; without a move ordering assumption, no doubling is guaranteed. For $b>1$, a full minimax search to depth $d$ visits $\Theta (b^d)$ search nodes, so the budget $n$ has $d\approx {\log }_{b}n$. Perfectly ordered alpha-beta pruning evaluates only about $\Theta (b^{d^{\prime }/2})$ leaves at depth $d^{\prime }$. More precisely, for a complete uniform game tree, the best leaf count is $b^{\lceil d^{\prime }/2\rceil }+b^{\lfloor d^{\prime }/2\rfloor }-1$. Equating the dominant costs givesConstant factors and rounding affect the exact horizon. Poor move ordering can leave the cost at $\Theta (b^{d^{\prime }})$, giving no asymptotic depth improvement. For $b=1$, there is no branching to prune and the doubling argument does not apply.^[ref]

Expectiminimax adds chance nodes to the MAX and MIN decisions. A chance node usesso exact evaluation generally needs all outcomes with positive probability. An unfavorable child does not determine the expected value: a later, sufficiently favorable child can offset it. Ordinary alpha-beta pruning therefore does not directly discard the remaining outcomes.

Random outcomes also enlarge the effective branching factor. If each player decision has $b$ choices and each action has $c$ chance outcomes, exploring $d$ player decisions can require order $(bc{)}^d$ leaves rather than $b^d$. Under the same budget, this gives roughlybefore additional pruning benefits available in the deterministic game are considered. Exact probability calculations add overhead as well. These effects explain the typically shallower horizon; randomness alone is not a theorem of inevitable slowdown. Known utility bounds permit some expected value bounds and specialized pruning, and chance sampling can trade exactness for speed.^[ref]

The usual alpha-beta pruning inference fails because increasing B's utility need not decrease A's utility. A partially explored B-node may have found a child unfavorable to A, but B may prefer an unseen child favorable to A as well. An observed low A-coordinate therefore supplies no upper bound on the A-coordinate ultimately propagated by B.

For a concrete counterexample, let a root A-node already have an alternative outcome $(1,0)$. In another B-node, the first explored child yields $(0,1)$. A zero-sum-style cutoff would discard its remaining children because $0<1$. But an unseen child with outcome $(100,2)$ is preferred by B, and makes the complete B-node return $(100,2)$, which A strictly prefers to its incumbent. Such a cutoff changes the answer.

The problem persists even after observing a large B-coordinate: without a known relation between coordinates or useful global utility bounds, an unseen pair may have still larger values for both players. Hence there is no generally valid ordinary scalar alpha-beta pruning rule for unrestricted general-sum games. This does not rule out all search pruning: additional bounds, dominance information or a relationship between players' utilities can justify specific cutoffs, as in (g).

Consider a B-node whose parent is an A-node with an already completed incumbent outcome having A-coordinate $\alpha$. At the B-node, let $(x,y)$ be the best completed child pair found so far according to B's coordinate. Every remaining child can be skipped, and this B-option discarded by its parent, ifUse a strict inequality if ties must remain open; equality is safe under the fixed rule that the parent retains its already selected child on an A-coordinate tie. This is a nearly-zero-sum pruning rule.

To prove it, note first that a completed max-n search value is some terminal utility pair: each backup copies one entire child pair. Thus the nearly-zero-sum inequality holds at every completed subtree, not just at leaves. Since B maximizes its own coordinate, the ultimately selected pair $(u,v)$ at this B-node has $v\ge y$. ThereforeThe already available A-option is at least as good, so remaining children of this B-node cannot alter the parent's selected continuation under the stated tie rule. The second half of the two-sided nearly-zero-sum condition also gives $x+y\ge -ϵ$, henceConsequently $x+2ϵ\le \alpha$ is another sufficient cutoff, useful if one phrases the test using the observed A-coordinate. The pair-based test is sharper: the value of $y$ can certify a cutoff even when the conservative $x+2ϵ$ test cannot.

When $ϵ=0$, every pair satisfies $y=-x$, and the rule reduces to $x\le \alpha$, the ordinary MIN-node alpha-beta pruning cutoff. The extra $2ϵ$ in the A-coordinate-only condition is necessary in general: an observed pair $(-1,0)$ satisfies the bound for $ϵ=1$, but B prefers an unseen $(1-\delta ,\delta )$ for $0<\delta <1$. A increases by almost $2ϵ$; using just $x+ϵ$ as the upper bound would be invalid.

Implementation must discard the ruled-out B-option at its parent rather than return $(x,y)$ as an exact completed utility pair. The proof uses an actual completed alternative at that parent; it does not authorize passing arbitrary distant ancestor bounds through general-sum game backups as if every scalar alpha-beta pruning invariant still held. With these local certified cutoffs, an induction over completed subtrees preserves the selected pair and hence the root outcome.