Alpha-Beta pruning is not actually a new algorithm, rather an optimization technique for minimax algorithm.

• It reduces the computation time by a huge factor.
• This allows us to search much faster and even go into deeper levels in the game tree.
• It cuts off branches in the game tree which need not be searched because there already exists a better move available.
• It is called Alpha-Beta pruning because it passes 2 extra parameters in the minimax function, namely alpha and beta.

Alpha is the best value that the maximizer currently can guarantee at that level or above.

Beta is the best value that the minimizer currently can guarantee at that level or above.

A program to illustrate Alpha-Beta Pruning

Example

function minimax(node, depth, isMaximizingPlayer, alpha, beta):
 
  if node is a leaf node :
    return value of the node
 
  if isMaximizingPlayer :
    bestVal = -INFINITY 
    for each child node :
      value = minimax(node, depth+1, false, alpha, beta)
      bestVal = max( bestVal, value) 
      alpha = max( alpha, bestVal)
      if beta <= alpha:
        break
      return bestVal
 
  else :
    bestVal = +INFINITY 
    for each child node :
      value = minimax(node, depth+1, true, alpha, beta)
      bestVal = min( bestVal, value) 
      beta = min( beta, bestVal)
      if beta <= alpha:
        break
      return bestVal
 
 
// Calling the function for the first time.
minimax(0, 0, true, -INFINITY, +INFINITY)