X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=16847b3d830733873c23d1d2207f68648570a00e;hb=252844e899515d48c0db1153ef5e91bdd8c6679f;hp=671a23cf5a6b14e8ef20eb84a088e485eead727a;hpb=973e574e1f0952b80cebc634d7cebc05f27fc9ec;p=stockfish

diff --git a/src/search.cpp b/src/search.cpp
index 671a23cf..16847b3d 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -239,8 +239,8 @@ namespace {
   std::ofstream LogFile;
 
   // Natural logarithmic lookup table and its getter function
-  double lnArray[512];
-  inline double ln(int i) { return lnArray[i]; }
+  float lnArray[512];
+  inline float ln(int i) { return lnArray[i]; }
 
   // MP related variables
   int ActiveThreads = 1;
@@ -288,7 +288,8 @@ namespace {
   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);
-  Depth calculate_reduction(double baseReduction, int moveCount, Depth depth, double reductionInhibitor);
+  void reduction_parameters(float base, float Inhibitor, Depth depth, float& logLimit, float& gradient);
+  Depth reduction(int moveCount, const float LogLimit, const float BaseRed, const float Gradient);
   void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
   void update_killers(Move m, SearchStack& ss);
   void update_gains(const Position& pos, Move move, Value before, Value after);
@@ -573,7 +574,7 @@ void init_threads() {
 
   // Init our logarithmic lookup table
   for (i = 0; i < 512; i++)
-      lnArray[i] = log(double(i)); // log() returns base-e logarithm
+      lnArray[i] = float(log(double(i))); // log() returns base-e logarithm
 
   for (i = 0; i < THREAD_MAX; i++)
       Threads[i].activeSplitPoints = 0;
@@ -964,6 +965,10 @@ namespace {
 
         value = - VALUE_INFINITE;
 
+        // Precalculate reduction parameters
+        float LogLimit, Gradient, BaseReduction = 0.5;
+        reduction_parameters(BaseReduction, 6.0, depth, LogLimit, Gradient);
+
         while (1) // Fail high loop
         {
 
@@ -999,7 +1004,7 @@ namespace {
                 && !captureOrPromotion
                 && !move_is_castle(move))
             {
-                ss[0].reduction = calculate_reduction(0.5, RootMoveNumber - MultiPV + 1, depth, 6.0);
+                ss[0].reduction = reduction(RootMoveNumber - MultiPV + 1, LogLimit, BaseReduction, Gradient);
                 if (ss[0].reduction)
                 {
                     value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
@@ -1254,6 +1259,10 @@ namespace {
     CheckInfo ci(pos);
     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
 
+    // Precalculate reduction parameters
+    float LogLimit, Gradient, BaseReduction = 0.5;
+    reduction_parameters(BaseReduction, 6.0, depth, LogLimit, Gradient);
+
     // Loop through all legal moves until no moves remain or a beta cutoff
     // occurs.
     while (   alpha < beta
@@ -1311,8 +1320,8 @@ namespace {
             && !captureOrPromotion
             && !move_is_castle(move)
             && !move_is_killer(move, ss[ply]))
-        {
-            ss[ply].reduction = calculate_reduction(0.5, moveCount, depth, 6.0);
+        {            
+            ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
             if (ss[ply].reduction)
             {
                 value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
@@ -1468,7 +1477,6 @@ namespace {
 
     // Calculate depth dependant futility pruning parameters
     const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8));
-    const int PostFutilityValueMargin = FutilityMargins[int(depth)];
 
     // Evaluate the position statically
     if (!isCheck)
@@ -1482,19 +1490,18 @@ namespace {
         }
 
         ss[ply].eval = staticValue;
-        futilityValue = staticValue + PostFutilityValueMargin; //FIXME: Remove me, only for split
+        futilityValue = staticValue + FutilityMargins[int(depth)]; //FIXME: Remove me, only for split
         staticValue = refine_eval(tte, staticValue, ply); // Enhance accuracy with TT value if possible
         update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
     }
 
     // Do a "stand pat". If we are above beta by a good margin then
     // return immediately.
-    // FIXME: test with added condition 'allowNullmove || depth <= OnePly' and !value_is_mate(beta)
-    // FIXME: test with modified condition 'depth < RazorDepth'
     if (  !isCheck
-        && depth < SelectiveDepth
-        && staticValue - PostFutilityValueMargin >= beta)
-        return staticValue - PostFutilityValueMargin;
+        && allowNullmove
+        && depth < RazorDepth
+        && staticValue - FutilityMargins[int(depth)] >= beta)
+        return staticValue - FutilityMargins[int(depth)];
 
     // Null move search
     if (    allowNullmove
@@ -1574,6 +1581,10 @@ namespace {
     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
     CheckInfo ci(pos);
 
+    // Precalculate reduction parameters
+    float LogLimit, Gradient, BaseReduction = 0.5;
+    reduction_parameters(BaseReduction, 3.0, depth, LogLimit, Gradient);
+
     // Loop through all legal moves until no moves remain or a beta cutoff occurs
     while (   bestValue < beta
            && (move = mp.get_next_move()) != MOVE_NONE
@@ -1665,7 +1676,7 @@ namespace {
           Depth predictedDepth = newDepth;
 
           //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG??
-          ss[ply].reduction = calculate_reduction(0.5, moveCount, depth, 3.0);
+          ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
           if (ss[ply].reduction)
               predictedDepth -= ss[ply].reduction;
 
@@ -1701,7 +1712,7 @@ namespace {
           && !move_is_castle(move)
           && !move_is_killer(move, ss[ply]))
       {
-          ss[ply].reduction = calculate_reduction(0.5, moveCount, depth, 3.0);
+          ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
           if (ss[ply].reduction)
           {
               value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
@@ -1794,6 +1805,7 @@ namespace {
     const TTEntry* tte = NULL;
     int moveCount = 0;
     bool pvNode = (beta - alpha != 1);
+    Value oldAlpha = alpha;
 
     // Initialize, and make an early exit in case of an aborted search,
     // an instant draw, maximum ply reached, etc.
@@ -1937,14 +1949,14 @@ namespace {
 
     // Update transposition table
     Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
-    if (bestValue < beta)
+    if (bestValue <= oldAlpha)
     {
         // If bestValue isn't changed it means it is still the static evaluation
         // of the node, so keep this info to avoid a future evaluation() call.
         ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
         TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
     }
-    else
+    else if (bestValue >= beta)
     {
         move = ss[ply].pv[ply];
         TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
@@ -1953,6 +1965,8 @@ namespace {
         if (!pos.move_is_capture_or_promotion(move))
             update_killers(move, ss[ply]);
     }
+    else
+        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EXACT, d, ss[ply].pv[ply]);
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
@@ -1985,6 +1999,10 @@ namespace {
 
     const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8));
 
+    // Precalculate reduction parameters
+    float LogLimit, Gradient, BaseReduction = 0.5;
+    reduction_parameters(BaseReduction, 3.0, sp->depth, LogLimit, Gradient);
+
     while (    lock_grab_bool(&(sp->lock))
            &&  sp->bestValue < sp->beta
            && !thread_should_stop(threadID)
@@ -2045,7 +2063,7 @@ namespace {
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          ss[sp->ply].reduction = calculate_reduction(0.5, moveCount, sp->depth, 3.0);
+          ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
           if (ss[sp->ply].reduction)
           {
               value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
@@ -2125,6 +2143,10 @@ namespace {
     int moveCount;
     Move move;
 
+    // Precalculate reduction parameters
+    float LogLimit, Gradient, BaseReduction = 0.5;
+    reduction_parameters(BaseReduction, 6.0, sp->depth, LogLimit, Gradient);
+
     while (    lock_grab_bool(&(sp->lock))
            &&  sp->alpha < sp->beta
            && !thread_should_stop(threadID)
@@ -2158,7 +2180,7 @@ namespace {
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          ss[sp->ply].reduction = calculate_reduction(0.5, moveCount, sp->depth, 6.0);
+          ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
           if (ss[sp->ply].reduction)
           {
               Value localAlpha = sp->alpha;
@@ -2685,20 +2707,35 @@ namespace {
       return defaultEval;
   }
 
-  // calculate_reduction() returns reduction in plies based on
-  // moveCount and depth. Reduction is always at least one ply.
 
-  Depth calculate_reduction(double baseReduction, int moveCount, Depth depth, double reductionInhibitor) {
+  // reduction_parameters() precalculates some parameters used later by reduction. Becasue
+  // floating point operations are involved we try to recalculate reduction at each move, but
+  // we do the most consuming computation only once per node.
 
-    double red = baseReduction + ln(moveCount) * ln(depth / 2) / reductionInhibitor;
+  void reduction_parameters(float baseReduction, float reductionInhibitor, Depth depth, float& logLimit, float& gradient)
+  {
+      // Precalculate some parameters to avoid to calculate the following formula for each move:
+      //
+      //    red = baseReduction + ln(moveCount) * ln(depth / 2) / reductionInhibitor;
+      //
+      logLimit = depth  > OnePly ? (1 - baseReduction) * reductionInhibitor / ln(depth / 2) : 1000;
+      gradient = depth  > OnePly ? ln(depth / 2) / reductionInhibitor : 0;
+  }
 
-    if (red >= 1.0)
-        return Depth(int(floor(red * int(OnePly))));
-    else
+
+  // reduction() returns reduction in plies based on moveCount and depth.
+  // Reduction is always at least one ply.
+
+  Depth reduction(int moveCount, float logLimit, float baseReduction, float gradient) {    
+
+    if (ln(moveCount) < logLimit)
         return Depth(0);
 
+    float red = baseReduction + ln(moveCount) * gradient;
+    return Depth(int(floor(red * int(OnePly))));
   }
 
+
   // update_history() registers a good move that produced a beta-cutoff
   // in history and marks as failures all the other moves of that ply.