*(Warning: this is a bit 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(minmoves(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

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 after one of
your moves m—you should make move m. The recursion stops when the value of a state is
known: for example, when a King is captured.

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.negamax(s) =do

ifgame_over(s)returnvalue(s)

returnmax(minmoves(s) | -negamax(move(s,m)))

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.)*

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(minmoves(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 Mini-Chess, 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.

wherenegamax(s,d) =do

ifgame_over(s)ord= 0returnvalue(s)

returnmax(minmoves(s) | -negamax(move(s,m),d - 1))

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

*Missed Opportunity:* There are some problems with
depth-limited negamax. It still does some search that can
be avoided with enough cleverness: see e.g. MTD(f). It also
suffers from the "horizon effect"; it should keep going in
situations where the value at the depth limit might be way off.

prev index next