NegaMax Search

NegaMax search is used to find the best choice in a zero-sum two player turn based game (e.g. chess, draughts and tic-tac-toe). In reality, negamax is nothing more than a more concise way to code another search algorithm called MiniMax. Understanding the logic of minimax means understanding the logic of negamax. So we will do that first. Then we will derive negamax from minimax.

Decision Tree

We will use the decision tree shown below, to walk through minimax search. Let’s assume it represents a chess game, half way through, between two players named Nimzo and Capa. Each node in the tree represents a board position. Every branch represents a possible move. Root node represents current board position. Every level represents alternating turns between Nimzo and Capa. So the top three branches represent three possible moves available to Nimzo. The next level down, branches represents possible move choices for Capa for every possible move that Nimzo can make now. Third level, in turn, represents Nimzo’s countermoves to Capa’s counter moves. The tree stops at four levels, called depth of the tree, but in real chess game this can carry on for many more levels.

Animation of minimax search

Animation of minimax search

Every node (i.e. chess board position) has a score associated. The score is from the perspective of the player whose turn it is at the root node. So in ours example, the score for each board will be from the perspective of Nimzo because it’s Nimzo’s turn at the root node. Now remember this is a zero-sum game. That means, sum of scores for the two players for each node must be zero. Therefore the score for a node from perspective of Nimzo will be -1 times the score for the same node from perspective of Capa. So we can call Nimzo the maximising player and Capa the minimising player. This point is crucial to our discussion here.

Our objective here is to find the best move for Nimzo.

MiniMax

Nimzo wants to make the best move which leaves Capa with worst best option possible. But then when Capa makes his move he will want to do the same thing, leaving Nimzo with the worst best option. Nimzo would want to factor Capa’s perspective into his calculations. But since Capa would like to do the same with regard to Nimzo, this turns into a recursive calculation. A chess game’s decision tree is impractically tall to calculate all the possible moves and countermoves so we have to limit the depth to a practical level. At that level each node will be a leaf node. Once the minimax search reaches that level, it uses a special function (called Evaluate()) which takes in the board position at each leaf node and uses some heuristics to return an integer which represents the score for that node.

As shown in the animated gif above, minimax works its way in a depth-first manner. Once it reaches the leaf nodes it calls Evaluate() to assign scores to leaf nodes. Then based upon those scores it assigns scores to nodes one level above the deepest level. That is either the maximum or the minimum of the leaf node scores depending upon whose move it is at the second to last level. It will be maximum if it is Nimzo’s turn and minimum if it is Capa’s turn.

Pseudo code and NegaMax

Finally we present pseudo code for minimax which then sets the stage for negamax.

int maxi( int depth ) {
  if ( depth == 0 ) return evaluate();
  int max = -oo; /* set max to negative infinity */
  for ( all moves) {
    score = mini( depth - 1 );
    if( score > max )
      max = score;
  }

  return max;
}
int mini( int depth ) {
  if ( depth == 0 ) return -evaluate();
  int min = +oo; /* set min to positive infinity */
  for ( all moves) {
    score = maxi( depth - 1 );
    if( score < min )
      min = score;
  }

  return min;
}

Here, the two methods maxi and mini recursively call into eachother until leaf nodes are reached and then work their way back up the tree assigning scores to nodes as they go.

Now recall the fact that it is a zero sum game where one player’s loss is the other gain. Mathematically:

max(a, b) == -min(-a, -b)

NegaMax combines the two methods above, maxi and mini, into a single method. It alternates the calculation of score for maximising and minimising players by reversing the arguments passed to its recursive calls. Following is the pseudocode for negamax:

int negaMax( int depth ) {
  if ( depth == 0 ) return evaluate();
  int max = -oo; /* set max to negative infinity */
  for ( all moves)  {
    score = -negaMax( depth - 1 );
    if( score > max )
      max = score;
  }

  return max;
}

Before finishing, let’s quickly see why is there a need for more compact negamax. Minimax is a brute force search and when applied to problems like chess, due to the sheer size of the tree, it becomes impracticably slow. Therefore programmers rely on search optimisations like alpha-beta pruning. Those search optimisations are easier to apply when using a compact format like negamax rather than the two-method minimax format.

The pseudo codes and the animated gif above are from the excellent resource http://chessprogramming.wikispaces.com.

Advertisements

One thought on “NegaMax Search

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s