Alpha-Beta search :

Alpha-Beta search is the first major refinement for reducing the number of positions that has to be searched and thus making greater depths possible in the same amount of time. The idea is that in large parts of the tree we are not interested in the exact value of a position, but are just interested if it is better or worse than what we have found before.

Only the value of the position along the principal variation has to be determined exactly.

Chess Tree Search  
MiniMax and NegaMax  
Alpha-Beta search
Aspiration search  
Transposition table  
 

The AlphaBeta search procedure gets two additional arguments which indicate the bounds between which we are interested in exact values for a position.

The gain from AlphaBeta will come form the earlier exit from the wile loop; a value of best that equals or exceeds beta is call a cutoff.

Under optimal circumstances AlphaBeta still has to search X^((D+1)/2)+Y^(D/2)-1 positions. This is much less than MiniMax, but still exponential.

 

MiniMax and NegaMax   -  Alpha-Beta search   -  AspirationSearch  -  Transposition table