Implement futility move count array

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index d3b229e67edd865091d85883688cbd28cb6926c2..e1ac91c3f58e6a3a22f07477ed62b3c893bb9f9d 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -126,9 +126,6 @@ namespace {
   // Search depth at iteration 1
   const Depth InitialDepth = OnePly;
 
-  // Depth limit for selective search
-  const Depth SelectiveDepth = 7 * OnePly;
-
   // Use internal iterative deepening?
   const bool UseIIDAtPVNodes = true;
   const bool UseIIDAtNonPVNodes = true;
@@ -150,15 +147,6 @@ namespace {
   // remaining ones we will extend it.
   const Value SingleReplyMargin = Value(0x20);
 
-  // Margins for futility pruning in the quiescence search, and at frontier
-  // and near frontier nodes.
-  const Value FutilityMarginQS = Value(0x80);
-
-  Value FutilityMargins[2 * PLY_MAX_PLUS_2]; // Initialized at startup.
-
-  // Each move futility margin is decreased
-  const Value IncrementalFutilityMargin = Value(0x8);
-
   // Depth limit for razoring
   const Depth RazorDepth = 4 * OnePly;
 
@@ -207,6 +195,14 @@ namespace {
   bool UseLogFile;
   std::ofstream LogFile;
 
+  // Futility lookup tables and their getter functions
+  const Value FutilityMarginQS = Value(0x80);
+  int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber]
+  int FutilityMoveCountArray[32]; // [depth]
+
+  inline Value futility_margin(Depth d, int mn) { return (Value) (d < 14? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2*VALUE_INFINITE); }
+  inline int futility_move_count(Depth d) { return (d < 32? FutilityMoveCountArray[d] : 512); }
+
   // Reduction lookup tables and their getter functions
   // Initialized at startup
   int8_t    PVReductionMatrix[64][64]; // [depth][moveNumber]
@@ -554,12 +550,15 @@ void init_threads() {
       }
 
   // Init futility margins array
-  FutilityMargins[0] = FutilityMargins[1] = Value(0);
+  for (i = 0; i < 14; i++) // i == depth (OnePly = 2)
+      for (int j = 0; j < 64; j++) // j == moveNumber
+      {
+          FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j; // FIXME: test using log instead of BSR
+      }
 
-  for (i = 2; i < 2 * PLY_MAX_PLUS_2; i++)
-  {
-      FutilityMargins[i] = Value(112 * bitScanReverse32(i * i / 2)); // FIXME: test using log instead of BSR
-  }
+  // Init futility move count array
+  for (i = 0; i < 32; i++) // i == depth (OnePly = 2)
+      FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8));
 
   for (i = 0; i < THREAD_MAX; i++)
       Threads[i].activeSplitPoints = 0;
@@ -1374,9 +1373,6 @@ namespace {
 
     isCheck = pos.is_check();
 
-    // Calculate depth dependant futility pruning parameters
-    const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8));
-
     // Evaluate the position statically
     if (!isCheck)
     {
@@ -1389,7 +1385,7 @@ namespace {
         }
 
         ss[ply].eval = staticValue;
-        futilityValue = staticValue + FutilityMargins[int(depth)]; //FIXME: Remove me, only for split
+        futilityValue = staticValue + futility_margin(depth, 0); //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);
     }
@@ -1400,8 +1396,8 @@ namespace {
     if (  !isCheck
         && allowNullmove
         && depth < RazorDepth
-        && staticValue - FutilityMargins[int(depth)] >= beta)
-        return staticValue - FutilityMargins[int(depth)];
+        && staticValue - futility_margin(depth, 0) >= beta)
+        return staticValue - futility_margin(depth, 0);
 
     // Null move search
     if (    allowNullmove
@@ -1473,7 +1469,7 @@ namespace {
     {
         search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
         ttMove = ss[ply].pv[ply];
-        tte = TT.retrieve(pos.get_key());
+        tte = TT.retrieve(posKey);
     }
 
     // Initialize a MovePicker object for the current position, and prepare
@@ -1533,35 +1529,20 @@ namespace {
           &&  move != ttMove)
       {
           // Move count based pruning
-          if (   moveCount >= FutilityMoveCountMargin
+          if (   moveCount >= futility_move_count(depth)
               && ok_to_prune(pos, move, ss[ply].threatMove)
               && bestValue > value_mated_in(PLY_MAX))
               continue;
 
           // Value based pruning
-          Depth predictedDepth = newDepth;
-
-          //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG??
-          ss[ply].reduction = nonpv_reduction(depth, moveCount);
-          if (ss[ply].reduction)
-              predictedDepth -= ss[ply].reduction;
+          Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG??
+          futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
 
-          if (predictedDepth < SelectiveDepth)
+          if (futilityValueScaled < beta)
           {
-              int preFutilityValueMargin = 0;
-              if (predictedDepth >= OnePly)
-                  preFutilityValueMargin = FutilityMargins[int(predictedDepth)];
-
-              preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45;
-
-              futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin;
-
-              if (futilityValueScaled < beta)
-              {
-                  if (futilityValueScaled > bestValue)
-                      bestValue = futilityValueScaled;
-                  continue;
-              }
+              if (futilityValueScaled > bestValue)
+                  bestValue = futilityValueScaled;
+              continue;
           }
       }
 
@@ -1860,11 +1841,9 @@ namespace {
     Move move;
     int moveCount;
     bool isCheck = pos.is_check();
-    bool useFutilityPruning =     sp->depth < SelectiveDepth
+    bool useFutilityPruning =     sp->depth < 7 * OnePly //FIXME: sync with search
                               && !isCheck;
 
-    const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8));
-
     while (    lock_grab_bool(&(sp->lock))
            &&  sp->bestValue < sp->beta
            && !thread_should_stop(threadID)
@@ -1891,13 +1870,13 @@ namespace {
           && !captureOrPromotion)
       {
           // Move count based pruning
-          if (   moveCount >= FutilityMoveCountMargin
+          if (   moveCount >= futility_move_count(sp->depth)
               && ok_to_prune(pos, move, ss[sp->ply].threatMove)
               && sp->bestValue > value_mated_in(PLY_MAX))
               continue;
 
           // Value based pruning
-          Value futilityValueScaled = sp->futilityValue - moveCount * IncrementalFutilityMargin;
+          Value futilityValueScaled = sp->futilityValue - moveCount * 8; //FIXME: sync with search
 
           if (futilityValueScaled < sp->beta)
           {