Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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.

----

<code>
max(a, b) == -min(-a, -b)
</code>

This is how the pseudo-code of the recursive algorithm looks like. For clarity move making and unmaking is omitted.

<code>
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;
}
</code>

<WRAP info>
**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.

</WRAP>

----

===== References =====

http://web.archive.org/web/20120209042116/http://chessprogramming.wikispaces.com/Negamax