Logarithmic LMR

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index 5fc9be3679aa1d265b71285ab82b69e4460936eb..18b972f27b4aba6348983f6894777329d117c5e9 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -288,6 +288,7 @@ namespace {
   bool ok_to_do_nullmove(const Position& pos);
   bool ok_to_prune(const Position& pos, Move m, Move threat);
   bool ok_to_use_TT(const TTEntry* tte, Depth depth, Value beta, int ply);
+  Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
   void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
   void update_killers(Move m, SearchStack& ss);
 
@@ -325,6 +326,13 @@ namespace {
 //// Functions
 ////
 
+//FIXME: HACK
+static double lnArray[512];
+
+inline double ln(int i)
+{
+    return lnArray[i];
+}
 
 /// perft() is our utility to verify move generation is bug free. All the legal
 /// moves up to given depth are generated and counted and the sum returned.
@@ -561,8 +569,14 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
 /// and initializes the split point stack and the global locks and condition
 /// objects.
 
+#include <cmath> //FIXME: HACK
+
 void init_threads() {
 
+  // FIXME: HACK!!
+  for (int i = 0; i < 512; i++)
+    lnArray[i] = log(double(i));
+
   volatile int i;
 
 #if !defined(_MSC_VER)
@@ -1201,14 +1215,19 @@ namespace {
         // Try to reduce non-pv search depth by one ply if move seems not problematic,
         // if the move fails high will be re-searched at full depth.
         if (    depth >= 3*OnePly
-            &&  moveCount >= LMRPVMoves
             && !dangerous
             && !captureOrPromotion
             && !move_is_castle(move)
             && !move_is_killer(move, ss[ply]))
         {
-            ss[ply].reduction = OnePly;
-            value = -search(pos, ss, -alpha, newDepth-OnePly, ply+1, true, threadID);
+          double red = ln(moveCount) * ln(depth / 2) / 3.0;
+          if (red >= 1.0)
+          {
+              ss[ply].reduction = Depth(floor(red * int(OnePly)));
+              value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
+          }
+          else
+              value = alpha + 1; // Just to trigger next condition
         }
         else
             value = alpha + 1; // Just to trigger next condition
@@ -1360,7 +1379,7 @@ namespace {
         return value_from_tt(tte->value(), ply);
     }
 
-    approximateEval = quick_evaluate(pos);
+    approximateEval = refine_eval(tte, quick_evaluate(pos), ply);
     isCheck = pos.is_check();
 
     // Null move search
@@ -1526,14 +1545,20 @@ namespace {
       // Try to reduce non-pv search depth by one ply if move seems not problematic,
       // if the move fails high will be re-searched at full depth.
       if (    depth >= 3*OnePly
-          &&  moveCount >= LMRNonPVMoves
           && !dangerous
           && !captureOrPromotion
           && !move_is_castle(move)
-          && !move_is_killer(move, ss[ply]))
+          && !move_is_killer(move, ss[ply])
+          /* && move != ttMove*/)
       {
-          ss[ply].reduction = OnePly;
-          value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
+          double red = ln(moveCount) * ln(depth / 2) / 1.5;
+          if (red >= 1.0)
+          {
+              ss[ply].reduction = Depth(floor(red * int(OnePly)));
+              value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
+          }
+          else
+              value = beta; // Just to trigger next condition
       }
       else
           value = beta; // Just to trigger next condition
@@ -1867,13 +1892,18 @@ namespace {
       // Try to reduce non-pv search depth by one ply if move seems not problematic,
       // if the move fails high will be re-searched at full depth.
       if (   !dangerous
-          &&  moveCount >= LMRNonPVMoves
           && !captureOrPromotion
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          ss[sp->ply].reduction = OnePly;
-          value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
+          double red = ln(moveCount) * ln(sp->depth / 2) / 1.5;
+          if (red >= 1.0)
+          {
+              ss[sp->ply].reduction = Depth(floor(red * int(OnePly)));
+              value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+          }
+          else
+              value = sp->beta; // Just to trigger next condition
       }
       else
           value = sp->beta; // Just to trigger next condition
@@ -1973,13 +2003,18 @@ namespace {
       // Try to reduce non-pv search depth by one ply if move seems not problematic,
       // if the move fails high will be re-searched at full depth.
       if (   !dangerous
-          &&  moveCount >= LMRPVMoves
           && !captureOrPromotion
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          ss[sp->ply].reduction = OnePly;
-          value = -search(pos, ss, -sp->alpha, newDepth - OnePly, sp->ply+1, true, threadID);
+          double red = ln(moveCount) * ln(sp->depth / 2) / 3.0;
+          if (red >= 1.0)
+          {
+              ss[sp->ply].reduction = Depth(floor(red * int(OnePly)));
+              value = -search(pos, ss, -sp->alpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+          }
+          else
+              value = sp->alpha + 1; // Just to trigger next condition
       }
       else
           value = sp->alpha + 1; // Just to trigger next condition
@@ -2474,6 +2509,23 @@ namespace {
   }
 
 
+  // refine_eval() returns the transposition table score if
+  // possible otherwise falls back on static position evaluation.
+
+  Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
+
+      if (!tte)
+          return defaultEval;
+
+      Value v = value_from_tt(tte->value(), ply);
+
+      if (   (is_lower_bound(tte->type()) && v >= defaultEval)
+          || (is_upper_bound(tte->type()) && v < defaultEval))
+          return v;
+
+      return defaultEval;
+  }
+
   // update_history() registers a good move that produced a beta-cutoff
   // in history and marks as failures all the other moves of that ply.