View source for Alpha–beta pruning

'''Alpha–beta pruning''' is a [[search algorithm]] that seeks to decrease the number of nodes that are evaluated by the [[minimax]] algorithm in its [[search tree]].

== Description ==

It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, [[Chess]], Go, etc.). 

It stops completely 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.

== See also ==

* [[Branch and bound]]
* [[Combinatorial optimization]]
* [[Minimax]]
* [[Negamax]]
* [[Principal variation search]]
* [[Pruning (algorithm)]]
* [[Search algorithm]]
* [[Search tree]]
* [[Transposition table]]

== External links ==

* [https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning Alpha–beta pruning] @ Wikipedia


[[Category:Artificial intelligence]]
[[Category:Computer science]]
[[Category:Computing]]
[[Category:Game theory]]