Merge Joona Kiiski NULL search beta correction

Prune more moves after a null search because of
a lower beta limit then in main search.

In test positions reduces the searched nodes of 30% !!!!

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/evaluate.cpp b/src/evaluate.cpp
index c397671cb408d53293b76967260b2d292591f6f1..4745da0210a921112852c3a3cb69192200660481 100644 (file)
--- a/src/evaluate.cpp
+++ b/src/evaluate.cpp
@@ -289,7 +289,6 @@ namespace {
 
   void evaluate_space(const Position &p, Color us, EvalInfo &ei);
   inline Value apply_weight(Value v, int w);
-  Value scale_by_game_phase(Value mv, Value ev, Phase ph, const ScaleFactor sf[]);
 
   int count_1s_8bit(Bitboard b);
 
@@ -528,6 +527,22 @@ void read_weights(Color us) {
 }
 
 
+/// scale_by_game_phase() interpolates between a middle game and an endgame
+/// score, based on game phase.  It also scales the return value by a
+/// ScaleFactor array.
+
+Value scale_by_game_phase(Value mv, Value ev, Phase ph, const ScaleFactor sf[]) {
+
+  assert(mv > -VALUE_INFINITE && mv < VALUE_INFINITE);
+  assert(ev > -VALUE_INFINITE && ev < VALUE_INFINITE);
+  assert(ph >= PHASE_ENDGAME && ph <= PHASE_MIDGAME);
+
+  ev = apply_scale_factor(ev, sf[(ev > Value(0) ? WHITE : BLACK)]);
+
+  Value result = Value(int((mv * ph + ev * (128 - ph)) / 128));
+  return Value(int(result) & ~(GrainSize - 1));
+}
+
 namespace {
 
   // evaluate_common() computes terms common to all pieces attack
@@ -1144,23 +1159,6 @@ namespace {
   }
 
 
-  // scale_by_game_phase() interpolates between a middle game and an endgame
-  // score, based on game phase.  It also scales the return value by a
-  // ScaleFactor array.
-
-  Value scale_by_game_phase(Value mv, Value ev, Phase ph, const ScaleFactor sf[]) {
-
-    assert(mv > -VALUE_INFINITE && mv < VALUE_INFINITE);
-    assert(ev > -VALUE_INFINITE && ev < VALUE_INFINITE);
-    assert(ph >= PHASE_ENDGAME && ph <= PHASE_MIDGAME);
-
-    ev = apply_scale_factor(ev, sf[(ev > Value(0) ? WHITE : BLACK)]);
-
-    Value result = Value(int((mv * ph + ev * (128 - ph)) / 128));
-    return Value(int(result) & ~(GrainSize - 1));
-  }
-
-
   // count_1s_8bit() counts the number of nonzero bits in the 8 least
   // significant bits of a Bitboard. This function is used by the king
   // shield evaluation.

diff --git a/src/evaluate.h b/src/evaluate.h
index b95aa15d92aad4e662f90a1cc8f2f8d52fced5f1..1e97fd35ad9b32542d9a1560398b7bd5110433c3 100644 (file)
--- a/src/evaluate.h
+++ b/src/evaluate.h
@@ -105,6 +105,7 @@ extern Value quick_evaluate(const Position &pos);
 extern void init_eval(int threads);
 extern void quit_eval();
 extern void read_weights(Color sideToMove);
+extern Value scale_by_game_phase(Value mv, Value ev, Phase ph, const ScaleFactor sf[]);
 
 
 #endif // !defined(EVALUATE_H_INCLUDED)

diff --git a/src/search.cpp b/src/search.cpp
index 5606847a8370be6ed954b770ad3516474a88370f..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;
@@ -1202,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
@@ -1229,7 +1245,7 @@ namespace {
         {
             /* Do not return unproven mates */
         }
-        else if (nullValue >= beta)
+        else if (nullValue >= beta - delta)
         {
             if (depth < 6 * OnePly)
                 return beta;