Build a Depth-Limited Negamax Search

(Warning: this is a bit long and hard, so watch closely.)

Now that you have a state evaluator to go with your move generator, you have really improved your random chess player. Your algorithm is something like

best_move(s1) = argmin(m in moves(s1) | eval(move(s1, m)))

The problem with this plan is that the move that gives you the best value now might lead to big trouble later. Think about this position:

30 W
.....
.k...
.p...
.Q...
.....
...K.

You would not want to take the Black Pawn with the White Queen—but that is what would most improve your state right now! You need to plan ahead to make things work better.


The best move for you is one that makes sure you will win the game. (If there is no winning move, you try to find a move that will tie.) If you knew the "true value" to your opponent of each of the states resulting from your possible moves, you could just pick the move that will give the opponent the worst result. The key idea of minimax is that you can find out the true value of a state s to your opponent by recursively valuing the state resulting from each possible move your opponent has on s using minimax. The value of s to you is the negation of the opponent's worst s value resulting from one of your moves; you should make this move. The recursion stops when the value of a state is known—for example, when a King is captured.

negamax(s) = do
  if game_over(s) return value(s)
  return max(m in moves(s) | -negamax(move(s, m)))

In the state above, minimax will notice that if the White Queen takes the Black Pawn, Black can take the Queen to force a draw. This is just what is wanted: it says that White should look for some other move.

We often draw a "call tree" to show the recursion in a negamax search. Here's part of the call tree for our sample position. The nodes are states, and the edges are moves. This picture makes it easy to see how the negamax value of a state is computed. (Note that we never build these graphs in memory. They are just recursive call trees.)

negamax search tree


Computing the negamax value of a state is nice. But what you want is to choose a move for the initial state. We choose a move as before, except using the negamax value instead of the minimax value.

best_move(s1) = argmin(m in moves(s1) | negamax(move(s1, m)))


There is just one more trick, and then we are done. Note that this recursion is big: even for a simple game like MiniChess, a program that runs this recursion will probably never finish. We have gone from not enough planning to too much. We need to limit how far ahead we look.

The easy way to do this is just to pick a depth limit for the recursion. When the depth limit is reached, return the current position's estimated value, not its negamax value.

negamax(s, d) = do
  if game_over(s) or d = 0 return value(s)
  return max(m in moves(s) | -negamax(move(s, m), d - 1))

best_move(s1) = argmin(m in moves(s1) | negamax(move(s1, m), d0))

where d0 is chosen to be big enough to get a good plan, but small enough to plan fast enough to be useful. (Choosing d0 is hard. See the next lesson for how to avoid having to make this choice.)


Let us put all this together. Here is some pseudocode for negamax that does all of what we have talked about so far. The algorithm has been changed slightly: instead of using extra code for storing the move to be made, we use a global variable. This is a common trick that avoids duplicate code at a tiny extra cost per step.

To find the negamax value of state s with max depth d:
    if s is a final state or d ≤ 0
        return score(s)
    M ← legal moves from s
    extract some move m from M
    s′ ← m(s)
    v′ ← -(negamax(s′d - 1))
    for m in remaining moves of M
        s′ ← m(s)
        v ← -(negamax(s′d - 1))
        v′ ← max(v′v)
    return v′

Posted Wed 13 Apr 2011 01:14:05 PM PDT

Missed Opportunity: There are some problems with depth-limited negamax. It does some search that can be avoided with enough cleverness, using techniques we will see shortly. It also suffers from the "horizon effect"; it should keep going in situations where the value at the depth limit might be way off.