Negamax
Negamax,
a common way of implementing minimax and derived algorithms. Instead of using two separate subroutines for the Min player and the Max player, it passes on the negated score due to following mathematical relation:
max(a, b) == -min(-a, -b)
Negated Minimax
This is how the pseudo-code of the recursive algorithm looks like. For clarity move making and unmaking is omitted.
int negaMax( int depth ) {
if ( depth == 0 ) return evaluate();
int max = -oo;
for ( all moves) {
score = -negaMax( depth - 1 );
if( score > max )
max = score;
}
return max;
}
How to Use NegaMax
Once you have your negaMax function – there are two questions which arise – i) how do you initially call negaMax, and ii) if negaMax is only returning an optimal score, then just how is it that you can know which particular move this score is related to? These two questions are related.
One calls negaMax with another root negaMax which makes the call to the negaMax proper with the default search depth. In the body of the loop of this root negaMax, in the loop which generates all the root moves – there one holds a variable as you call negaMax on the movement of each piece – and that is where you find the particular move attached to the score – in the line where you find score > max, right after you keep track of it by adding max = score – in the root negamax, that is where you pick out your move – which is what the root negaMax will return (instead of a score).
Note! In order for negaMax to work, your Static Evaluation function must return a score relative to the side to being evaluated, e.g. the simplest score evaluation could be:
score = materialWeight * (numWhitePieces - numBlackPieces) * who2move
where who2move = 1 for white, and who2move = -1 for black.
See also
Publications
- Warren D. Smith (1992). Fixed Point for Negamaxing Probability Distributions on Regular Trees. NEC Research Institute, ps [1]
Forum Posts
- NegaMax etc. (Beginner difficulity) by Mats Forsén, CCC, April 08, 1998
- Negamax algorithm?? by Severi Salminen, CCC, April 11, 2000
