Chess - Programming - Alpha-Beta Pruning

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.

Alpha-beta pruning is most effective on strongly-ordered trees, where the best move is searched first, the second-best move is searched second, and so on up to the worst move which is searched last.

Conversely, on a tree in the exact opposite order, alpha-beta is no better than naive Negamax Search.

• We should therefore endeavour to search the best move first.
• Move Ordering will make this possible.

A program to illustrate Alpha-Beta Pruning

Example

Transposition Table enhanced Alpha-Beta

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)