Merge Joona Kiiski NULL search beta correction

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index ba80ccdfde93ba1ab4ec97ed68d74e69fe929613..be324c16edff44b08a7450edbd8d016cf65fe351 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -152,6 +152,16 @@ namespace {
   // evaluation of the position is more than NullMoveMargin below beta.
   const Value NullMoveMargin = Value(0x300);
 
+  //Null move search refutes move when Nullvalue >= Beta - Delta. Index is depth
+  //in full plies. Last index is 9+.
+  const Value NullMoveDeltaMidgame[] =
+    { Value(-8), Value( 6), Value(-15), Value( 9), Value(21),
+      Value(34), Value(54), Value( 59), Value(61), Value(61) };
+
+  const Value NullMoveDeltaEndgame[] =
+    { Value( 6), Value( 0), Value(-13), Value(-9), Value(-35),
+      Value(12), Value(24), Value(  9), Value( 5), Value(  5) };
+
   // Pruning criterions.  See the code and comments in ok_to_prune() to
   // understand their precise meaning.
   const bool PruneEscapeMoves = false;
@@ -259,8 +269,6 @@ namespace {
                 Depth depth, int ply, int threadID);
   void sp_search(SplitPoint *sp, int threadID);
   void sp_search_pv(SplitPoint *sp, int threadID);
-  void init_search_stack(SearchStack& ss);
-  void init_search_stack(SearchStack ss[]);
   void init_node(const Position &pos, SearchStack ss[], int ply, int threadID);
   void update_pv(SearchStack ss[], int ply);
   void sp_update_pv(SearchStack *pss, SearchStack ss[], int ply);
@@ -324,6 +332,24 @@ History H;  // Should be made local?
 SearchStack EmptySearchStack;
 
 
+// SearchStack::init() initializes a search stack. Used at the beginning of a
+// new search from the root.
+void SearchStack::init(int ply) {
+
+  pv[ply] = pv[ply + 1] = MOVE_NONE;
+  currentMove = threatMove = MOVE_NONE;
+  reduction = Depth(0);
+  currentMoveCaptureValue = Value(0);
+}
+
+void SearchStack::initKillers() {
+
+  mateKiller = MOVE_NONE;
+  for (int i = 0; i < KILLER_MAX; i++)
+      killers[i] = MOVE_NONE;
+}
+
+
 ////
 //// Functions
 ////
@@ -588,7 +614,8 @@ void init_threads() {
   }
 
   // Init also the empty search stack
-  init_search_stack(EmptySearchStack);
+  EmptySearchStack.init(0);
+  EmptySearchStack.initKillers();
 }
 
 
@@ -640,8 +667,11 @@ namespace {
     // Initialize
     TT.new_search();
     H.clear();
-    init_search_stack(ss);
-
+    for (int i = 0; i < 3; i++)
+    {
+        ss[i].init(i);
+        ss[i].initKillers();
+    }
     ValueByIteration[0] = Value(0);
     ValueByIteration[1] = rml.get_move_score(0);
     Iteration = 1;
@@ -1182,13 +1212,19 @@ namespace {
         &&  ok_to_do_nullmove(pos)
         &&  approximateEval >= beta - NullMoveMargin)
     {
+        //Calculate correct delta. Idea and tuning from Joona Kiiski.
+        ScaleFactor factor[2] = { SCALE_FACTOR_NORMAL, SCALE_FACTOR_NORMAL };
+        Phase phase = pos.game_phase();
+        int i = Min(depth / OnePly, 9);
+        Value delta = scale_by_game_phase(NullMoveDeltaMidgame[i], NullMoveDeltaEndgame[i], phase, factor);
+
         ss[ply].currentMove = MOVE_NULL;
 
         StateInfo st;
         pos.do_null_move(st);
         int R = (depth >= 4 * OnePly ? 4 : 3); // Null move dynamic reduction
 
-        Value nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
+        Value nullValue = -search(pos, ss, -(beta-delta-1), depth-R*OnePly, ply+1, false, threadID);
 
         // Check for a null capture artifact, if the value without the null capture
         // is above beta then mark the node as a suspicious failed low. We will verify
@@ -1209,7 +1245,7 @@ namespace {
         {
             /* Do not return unproven mates */
         }
-        else if (nullValue >= beta)
+        else if (nullValue >= beta - delta)
         {
             if (depth < 6 * OnePly)
                 return beta;
@@ -1990,34 +2026,6 @@ namespace {
   }
 
 
-  // init_search_stack() initializes a search stack at the beginning of a
-  // new search from the root.
-  void init_search_stack(SearchStack& ss) {
-
-    ss.pv[0] = MOVE_NONE;
-    ss.pv[1] = MOVE_NONE;
-    ss.currentMove = MOVE_NONE;
-    ss.threatMove = MOVE_NONE;
-    ss.reduction = Depth(0);
-    for (int j = 0; j < KILLER_MAX; j++)
-        ss.killers[j] = MOVE_NONE;
-  }
-
-  void init_search_stack(SearchStack ss[]) {
-
-    for (int i = 0; i < 3; i++)
-    {
-        ss[i].pv[i] = MOVE_NONE;
-        ss[i].pv[i+1] = MOVE_NONE;
-        ss[i].currentMove = MOVE_NONE;
-        ss[i].threatMove = MOVE_NONE;
-        ss[i].reduction = Depth(0);
-        for (int j = 0; j < KILLER_MAX; j++)
-            ss[i].killers[j] = MOVE_NONE;
-    }
-  }
-
-
   // init_node() is called at the beginning of all the search functions
   // (search(), search_pv(), qsearch(), and so on) and initializes the search
   // stack object corresponding to the current node.  Once every
@@ -2037,13 +2045,9 @@ namespace {
         NodesSincePoll = 0;
       }
     }
-    ss[ply].pv[ply] = ss[ply].pv[ply+1] = ss[ply].currentMove = MOVE_NONE;
-    ss[ply+2].mateKiller = MOVE_NONE;
-    ss[ply].threatMove = MOVE_NONE;
-    ss[ply].reduction = Depth(0);
-    ss[ply].currentMoveCaptureValue = Value(0);
-    for (int j = 0; j < KILLER_MAX; j++)
-        ss[ply+2].killers[j] = MOVE_NONE;
+
+    ss[ply].init(ply);
+    ss[ply+2].initKillers();
 
     if(Threads[threadID].printCurrentLine)
       print_current_line(ss, ply, threadID);