Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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.

----

[[Chess:Programming:Alpha-Beta Pruning:A program to illustrate Alpha-Beta Pruning|A program to illustrate Alpha-Beta Pruning]]

[[Chess:Programming:Alpha-Beta Pruning:Example|Example]]

[[Chess:Programming:Alpha-Beta Pruning:Transposition table enhanced Alpha-Beta|Transposition Table enhanced Alpha-Beta]]

----

===== Pseudocode =====

<code cpp>
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)
</code>

----