Alpha-Beta pruning in Artificial Intelligence

Alpha-Beta Pruning Principle

If a move determined to be worse than another move that has already been examined, then further examining the possible consequences of that worse move is pointless.

Analysis of Alpha-Beta Pruning

This method provides its best performance when the game tree is assigned such that the best choice at each level is the first one to be examined by the algorithm using alpha-beta cut-off will examine a game tree to double the depth that a Minimax algorithm without alpha-beta pruning would examine in the same number of steps. How? If a game tree is arranged optimally, then the number of nodes that must be examined to find the best move using alpha-beta pruning cab be derived as found –

Alpha-Beta pruning Algorithm

function alpha-beta (current-node)
{
if is-leaf(current-node)
return static-evaluation(current-node)
if is-max-node(current-node) and
alpha-value of (current-node)>=
beta-value-of(min-ancestor-of(current-node)
then cut-off-search-below(current-node);
if is-min-node(current-node) and
beta-value-of(current-node)<= alpha-value-of(max-anchestor-of(current-node) 
then cut-off-search-below (current-node); 
}