Modify Minimax to Alpha-Beta pruning pseudo code

Question

I am learning the Alpha-Beta pseudo code and I want to write a simplest pseudo code for Alpha Beta pruning.

I have written the pseudo code for Minimax:

function minimax(node, depth)
     if node is a terminal node or depth ==0
          return the heuristic value of node
     else 
          best = -99999
     for child in node
          best = max(best, -minimax(child, depth-1))
     return best

However, I don't know how to modify it into alpha-beta pruning. Can anyone help?

Answer 1

In Alpha-Beta, you keep track of your guaranteed score for one position. You can stop immediately if you found a move that is better than the score that the opponent already has guaranteed in its previous position (one move before).

Technically, each side keeps track of its lowerbound score (alpha), and you have access to the opponent's lowerbound score (beta).

The following pseudo-code is not tested, but here is the idea:

function alphabeta(node, depth, alpha, beta)
     if node is a terminal node or depth ==0
          return the heuristic value of node
     else 
          best = -99999
     for child in node
          best = max(best, -alphabeta(child, depth-1, -beta, -alpha))
          if best >= beta
                return best
          if best > alpha
                alpha = best
     return best

At the start of the search, you can set alpha to -INFINITY and beta to +INFINITY. Strictly speaking, the sketched algorithm is not alpha-beta but Negamax. Both are identical, so this is just an implementation detail.

Note that in Alpha-Beta, the move ordering is crucial. If most of the time, you start with the best move, or at least a very good move, you should see a huge improvement over Minimax.

An additional optimization to start with restricted alpha beta windows (not -INFINITY and +INFINITY). However, if your assumption turns out wrong, you have to restart the search with a more open search window.