Editing Alpha–beta pruning (section)

{{short description|Search algorithm that seeks to decrease the number of nodes in the minimax algorithm search tree}}
{{other uses|Alphabeta (disambiguation)}}
{{Infobox algorithm
|class=[[Search algorithm]]
|image=
|data=
|time=<math>O(b^d)</math>
|best-time=<math>O\left(\sqrt{b^d}\right)</math>
|average-time=
|space=
|optimal=
|complete=
}}

'''Alpha–beta pruning''' is a [[search algorithm]] that seeks to decrease the number of nodes that are evaluated by the [[Minimax#Minimax algorithm with alternate moves|minimax algorithm]] in its [[game tree|search tree]]. It is an adversarial search algorithm used commonly for machine playing of two-player [[Combinatorial game theory|combinatorial games]] ([[Tic-tac-toe]], [[Chess]], [[Connect 4]], etc.). '''It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move.''' Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.{{sfn|Russell|Norvig|2021|p=152-161}}