Editing Alpha–beta pruning (section)

== Improvements over naive minimax ==
[[File:AB pruning.svg|thumb|400px|An illustration of alpha–beta pruning. The grayed-out subtrees don't need to be explored (when moves are evaluated from left to right), since it is known that the group of subtrees as a whole yields the value of an equivalent subtree or worse, and as such cannot influence the final result. The max and min levels represent the turn of the player and the adversary, respectively.]]
The benefit of alpha–beta pruning lies in the fact that branches of the search tree can be eliminated.{{r|levy198601}} This way, the search time can be limited to the 'more promising' subtree, and a deeper search can be performed in the same time. Like its predecessor, it belongs to the [[branch and bound]] class of algorithms. The optimization reduces the effective depth to slightly more than half that of simple minimax if the nodes are evaluated in an optimal or near optimal order (best choice for side on move ordered first at each node).

With an (average or constant) [[branching factor]] of ''b'', and a search depth of ''d'' [[Ply (game theory)|plies]], the maximum number of leaf node positions evaluated (when the move ordering is [[wiktionary:pessimal|pessimal]]) is [[Big O notation|''O'']](''b''<sup>''d''</sup>) – the same as a simple minimax search. If the move ordering for the search is optimal (meaning the best moves are always searched first), the number of leaf node positions evaluated is about ''O''(''b''×1×''b''×1×...×''b'') for odd depth and ''O''(''b''×1×''b''×1×...×1) for even depth, or <math>O(b^{d/2}) = O(\sqrt{b^d})</math>. In the latter case, where the ply of a search is even, the effective branching factor is reduced to its [[square root]], or, equivalently, the search can go twice as deep with the same amount of computation.{{sfn|Russell|Norvig|2021|p=155}} The explanation of ''b''×1×''b''×1×... is that all the first player's moves must be studied to find the best one, but for each, only the second player's best move is needed to refute all but the first (and best) first player move—alpha–beta ensures no other second player moves need be considered. When nodes are considered in a random order (i.e., the algorithm randomizes), asymptotically,
the expected number of nodes evaluated in uniform trees with binary leaf-values is <math>\Theta( ((b-1+\sqrt{b^2+14b+1})/4 )^d )</math>
.<ref name="SaksWigderson">{{cite book |last1=Saks |first1=M. |first2=A. |last2=Wigderson |chapter=Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees |title=27th Annual Symposium on Foundations of Computer Science |pages=29–38 |year=1986 |doi=10.1109/SFCS.1986.44 |isbn=0-8186-0740-8 |s2cid=6130392 }}</ref>
For the same trees, when the values are assigned to the leaf values independently of each other and say zero and one are both equally probable, the expected number of nodes evaluated is <math>\Theta( (b/2)^{d} )</math>, which is much smaller than the work done by the randomized algorithm, mentioned above, and is again optimal for such random trees.<ref name="Pearl1980">{{cite journal |last=Pearl |first=Judea |title=Asymptotic Properties of Minimax Trees and Game-Searching Procedures |journal=[[Artificial Intelligence (journal)|Artificial Intelligence]] |volume=14 |issue=2 |year=1980 |pages=113–138 |doi=10.1016/0004-3702(80)90037-5 }}</ref> When the leaf values are chosen independently of each other but from the <math>[0,1]</math> interval uniformly at random, the expected number of nodes evaluated increases to <math>\Theta( b^{d/log(d)} )</math> in the <math>d\to\infty</math> limit,<ref name="Pearl1982">{{cite journal |last=Pearl |first=Judea |title=The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality |journal=Communications of the ACM |volume=25 |issue=8 |year=1982 |pages=559–64 |doi=10.1145/358589.358616 |s2cid=8296219 |doi-access=free }}</ref> which is again optimal for this kind of random tree. Note that the actual work for "small" values of <math>d</math> is better approximated using <math>0.925 d^{0.747}</math>.<ref name="Pearl1982" /><ref name="Pearl1980" />

A chess program that searches four plies with an average of 36 branches per node evaluates more than one million terminal nodes. An optimal alpha-beta prune would eliminate all but about 2,000 terminal nodes, a reduction of 99.8%.{{r|levy198601}}

[[File:Minmaxab.gif|thumb|400px|An animated pedagogical example that attempts to be human-friendly by substituting initial infinite (or arbitrarily large) values for emptiness and by avoiding using the [[negamax]] coding simplifications.]]
Normally during alpha–beta, the [[subtrees]] are temporarily dominated by either a first player advantage (when many first player moves are good, and at each search depth the first move checked by the first player is adequate, but all second player responses are required to try to find a refutation), or vice versa. This advantage can switch sides many times during the search if the move ordering is incorrect, each time leading to inefficiency. As the number of positions searched decreases exponentially each move nearer the current position, it is worth spending considerable effort on sorting early moves. An improved sort at any depth will exponentially reduce the total number of positions searched, but sorting all positions at depths near the root node is relatively cheap as there are so few of them.  In practice, the move ordering is often determined by the results of earlier, smaller searches, such as through [[Iterative deepening depth-first search|iterative deepening]].

Additionally, this algorithm can be trivially modified to return an entire [[principal variation]] in addition to the score. Some more aggressive algorithms such as [[MTD(f)]] do not easily permit such a modification.