Alpha-beta pruning
= Alpha-beta pruning
<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\geq\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.https://www.cs.cmu.edu/~15281-f23/coursenotes/search/index.html[CMU 15-281, Search and Games, alpha-beta pruning]{ref}