chess:programming:search:negamax
Table of Contents
Chess - Programming - Search - Negamax
Negamax is 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:
How to Use NegaMax
NegaMax is called from a root function.
In the loop which generates all the root moves:
- Generate a Score relative to the side being evaluated, for a specific move.
- In the Root retain the returned score for each potential move.
- Pick the move with the lowest score.
max(a, b) == -min(-a, -b)
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;
}
NOTE: In order for NegaMax to work, the Static Evaluation function must return a score relative to the side to being evaluated.
- This score must be symmetric.
- The simplest score evaluation could be: score = materialWeight * (numWhitePieces - numBlackPieces) * who2move where who2move = 1 for white, and who2move = -1 for black.
References
chess/programming/search/negamax.txt · Last modified: 2021/10/12 00:50 by peter