Differences

This shows you the differences between two versions of the page.

--- chess:programming:search:negamax [2021/10/11 22:47] – created peter
+++ chess:programming:search:negamax [2021/10/11 23:50] (current) – peter
@@ Line 1: / Line 1: @@
 ====== 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