Alpha–beta pruning algorithm

nAlpha–beta pruning algorithm

nAlpha-Beta Heuristic  is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of thegame tree applying a branch-and-bound technique. Remarkably, it does this without any potential of overlooking a better move. If one already has found a quite good move and search for alternatives, onerefutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and beta. They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. 

function alphabeta(node, depth, α, β, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return the heuristic value of node
      if maximizingPlayer
         for each child of node
              α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
              if β ≤ α
                    break (* β cut-off *)
              return α
    else
         for each child of node
               β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
              if β ≤ α
                  break (* α cut-off *)
         return β
 (* Initial call *) alphabeta(origin, depth, -∞, +∞, TRUE)