X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=abf2673499ec8be4f0f5ea7a09ad63701ef4542c;hp=6bc77d3ba61224197a72a5ada11e509ef08103c6;hb=d7d2c1b7e31f5b680ebb44e2ffcbfc4bcb2aecfd;hpb=ea53006a9ded671c5f9deb27c1262d77f9722177

diff --git a/src/search.cpp b/src/search.cpp
index 6bc77d3b..abf26734 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -32,7 +32,6 @@
 #include "book.h"
 #include "evaluate.h"
 #include "history.h"
-#include "maxgain.h"
 #include "misc.h"
 #include "movegen.h"
 #include "movepick.h"
@@ -186,6 +185,8 @@ namespace {
   // 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);
 
@@ -215,6 +216,9 @@ namespace {
   IterationInfoType IterationInfo[PLY_MAX_PLUS_2];
   int BestMoveChangesByIteration[PLY_MAX_PLUS_2];
 
+  // Search window management
+  int AspirationDelta;
+
   // MultiPV mode
   int MultiPV;
 
@@ -235,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;
@@ -264,13 +268,10 @@ namespace {
   // History table
   History H;
 
-  // MaxGain table
-  MaxGain MG;
-
   /// Functions
 
   Value id_loop(const Position& pos, Move searchMoves[]);
-  Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta);
+  Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta);
   Value search_pv(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
   Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move excludedMove = MOVE_NONE);
   Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
@@ -287,8 +288,11 @@ 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);
+  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);
 
   bool fail_high_ply_1();
   int current_search_time();
@@ -570,11 +574,19 @@ 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;
 
+  // Init futility margins array
+  FutilityMargins[0] = FutilityMargins[1] = Value(0);
+
+  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
+  }
+
   // Initialize global locks
   lock_init(&MPLock, NULL);
   lock_init(&IOLock, NULL);
@@ -703,7 +715,6 @@ namespace {
     // Initialize
     TT.new_search();
     H.clear();
-    MG.clear();
     init_ss_array(ss);
     IterationInfo[1] = IterationInfoType(rml.get_move_score(0), rml.get_move_score(0));
     Iteration = 1;
@@ -734,7 +745,10 @@ namespace {
             int prevDelta1 = IterationInfo[Iteration - 1].speculatedValue - IterationInfo[Iteration - 2].speculatedValue;
             int prevDelta2 = IterationInfo[Iteration - 2].speculatedValue - IterationInfo[Iteration - 3].speculatedValue;
 
-            int delta = Max(2 * abs(prevDelta1) + abs(prevDelta2), ProblemMargin);
+            int delta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
+
+            delta = (delta + 7) / 8 * 8; // Round to match grainSize
+            AspirationDelta = delta;
 
             alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
             beta  = Min(IterationInfo[Iteration - 1].value + delta,  VALUE_INFINITE);
@@ -890,11 +904,12 @@ namespace {
   // similar to search_pv except that it uses a different move ordering
   // scheme and prints some information to the standard output.
 
-  Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta) {
+  Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value& oldAlpha, Value& beta) {
 
-    Value oldAlpha = alpha;
-    Value value = -VALUE_INFINITE;
+    Value alpha = oldAlpha;
+    Value value;
     CheckInfo ci(pos);
+    int researchCount = 0;
     bool isCheck = pos.is_check();
 
     // Evaluate the position statically
@@ -904,6 +919,9 @@ namespace {
     else
         ss[0].eval = VALUE_NONE;
 
+    while(1) // Fail low loop
+    {
+
     // Loop through all the moves in the root move list
     for (int i = 0; i <  rml.move_count() && !AbortSearch; i++)
     {
@@ -945,10 +963,19 @@ namespace {
         ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
         newDepth = depth + ext;
 
+        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
+        {
+
         // Make the move, and search it
         pos.do_move(move, st, ci, moveIsCheck);
 
-        if (i < MultiPV)
+        if (i < MultiPV || value > alpha)
         {
             // Aspiration window is disabled in multi-pv case
             if (MultiPV > 1)
@@ -977,10 +1004,9 @@ namespace {
                 && !captureOrPromotion
                 && !move_is_castle(move))
             {
-                double red = 0.5 + ln(RootMoveNumber - MultiPV + 1) * ln(depth / 2) / 6.0;
-                if (red >= 1.0)
+                ss[0].reduction = reduction(RootMoveNumber - MultiPV + 1, LogLimit, BaseReduction, Gradient);
+                if (ss[0].reduction)
                 {
-                    ss[0].reduction = Depth(int(floor(red * int(OnePly))));
                     value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
                     doFullDepthSearch = (value > alpha);
                 }
@@ -988,6 +1014,7 @@ namespace {
 
             if (doFullDepthSearch)
             {
+                ss[0].reduction = Depth(0);
                 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
 
                 if (value > alpha)
@@ -1004,6 +1031,46 @@ namespace {
 
         pos.undo_move(move);
 
+        if (AbortSearch || value < beta)
+            break; // We are not failing high
+
+        // We are failing high and going to do a research. It's important to update score
+        // before research in case we run out of time while researching.
+        rml.set_move_score(i, value);
+        update_pv(ss, 0);
+        TT.extract_pv(pos, ss[0].pv, PLY_MAX);
+        rml.set_move_pv(i, ss[0].pv);
+
+        // Print search information to the standard output
+        cout << "info depth " << Iteration
+             << " score " << value_to_string(value)
+             << ((value >= beta) ? " lowerbound" :
+                ((value <= alpha)? " upperbound" : ""))
+             << " time "  << current_search_time()
+             << " nodes " << nodes_searched()
+             << " nps "   << nps()
+             << " pv ";
+
+        for (int j = 0; ss[0].pv[j] != MOVE_NONE && j < PLY_MAX; j++)
+            cout << ss[0].pv[j] << " ";
+
+        cout << endl;
+
+        if (UseLogFile)
+        {
+            ValueType type =  (value >= beta  ? VALUE_TYPE_LOWER
+                            : (value <= alpha ? VALUE_TYPE_UPPER : VALUE_TYPE_EXACT));
+
+            LogFile << pretty_pv(pos, current_search_time(), Iteration,
+                                 nodes_searched(), value, type, ss[0].pv) << endl;
+        }
+
+        // Prepare for research
+        researchCount++;
+        beta = Min(beta + AspirationDelta * (1 << researchCount), VALUE_INFINITE);
+
+        } // End of fail high loop
+
         // Finished searching the move. If AbortSearch is true, the search
         // was aborted because the user interrupted the search or because we
         // ran out of time. In this case, the return value of the search cannot
@@ -1098,6 +1165,17 @@ namespace {
 
         FailLow = (alpha == oldAlpha);
     }
+
+    if (AbortSearch || alpha > oldAlpha)
+        break; // End search, we are not failing low
+
+    // Prepare for research
+    researchCount++;
+    alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
+    oldAlpha = alpha;
+
+    } // Fail low loop
+
     return alpha;
   }
 
@@ -1165,21 +1243,14 @@ namespace {
         tte = TT.retrieve(pos.get_key());
     }
 
-    // Evaluate the position statically
     isCheck = pos.is_check();
-    EvalInfo ei;
     if (!isCheck)
     {
+        // Update gain statistics of the previous move that lead
+        // us in this position.
+        EvalInfo ei;
         ss[ply].eval = evaluate(pos, ei, threadID);
-
-        // Store gain statistics
-        Move m = ss[ply - 1].currentMove;
-        if (   m != MOVE_NULL
-            && pos.captured_piece() == NO_PIECE_TYPE
-            && !move_is_castle(m)
-            && !move_is_promotion(m))
-            MG.store(pos.piece_on(move_to(m)), move_from(m), move_to(m), ss[ply - 1].eval, -ss[ply].eval);
-
+        update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
     }
 
     // Initialize a MovePicker object for the current position, and prepare
@@ -1188,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
@@ -1245,14 +1320,13 @@ namespace {
             && !captureOrPromotion
             && !move_is_castle(move)
             && !move_is_killer(move, ss[ply]))
-        {
-          double red = 0.5 + ln(moveCount) * ln(depth / 2) / 6.0;
-          if (red >= 1.0)
-          {
-              ss[ply].reduction = Depth(int(floor(red * int(OnePly))));
-              value = -search(pos, ss, -alpha, newDepth-ss[ply].reduction, ply+1, true, threadID);
-              doFullDepthSearch = (value > alpha);
-          }
+        {            
+            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);
+                doFullDepthSearch = (value > alpha);
+            }
         }
 
         if (doFullDepthSearch) // Go with full depth non-pv search
@@ -1403,7 +1477,6 @@ namespace {
 
     // Calculate depth dependant futility pruning parameters
     const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8));
-    const int PostFutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2);
 
     // Evaluate the position statically
     if (!isCheck)
@@ -1417,21 +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
-
-        // Store gain statistics
-        Move m = ss[ply - 1].currentMove;
-        if (   m != MOVE_NULL
-            && pos.captured_piece() == NO_PIECE_TYPE
-            && !move_is_castle(m)
-            && !move_is_promotion(m))
-            MG.store(pos.piece_on(move_to(m)), move_from(m), move_to(m), ss[ply - 1].eval, -ss[ply].eval);
+        update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
     }
 
-    // Post futility pruning
-    if (depth < SelectiveDepth && staticValue - PostFutilityValueMargin >= beta)
-        return (staticValue - PostFutilityValueMargin);
+    // Do a "stand pat". If we are above beta by a good margin then
+    // return immediately.
+    if (  !isCheck
+        && allowNullmove
+        && depth < RazorDepth
+        && staticValue - FutilityMargins[int(depth)] >= beta)
+        return staticValue - FutilityMargins[int(depth)];
 
     // Null move search
     if (    allowNullmove
@@ -1511,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
@@ -1555,29 +1629,6 @@ namespace {
       // Update current move
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
-      // Futility pruning for captures
-      Color them = opposite_color(pos.side_to_move());
-
-      if (   !isCheck
-          && newDepth < SelectiveDepth
-          && !dangerous
-          && pos.move_is_capture(move)
-          && !pos.move_is_check(move, ci)
-          && !move_is_promotion(move)
-          && move != ttMove
-          && !move_is_ep(move)
-          && (pos.type_of_piece_on(move_to(move)) != PAWN || !pos.pawn_is_passed(them, move_to(move)))) // Do not prune passed pawn captures
-      {
-          int preFutilityValueMargin = 0;
-
-          if (newDepth >= OnePly)
-              preFutilityValueMargin = 112 * bitScanReverse32(int(newDepth) * int(newDepth) / 2);
-
-          if (ss[ply].eval + pos.endgame_value_of_piece_on(move_to(move)) + preFutilityValueMargin + ei.futilityMargin + 90 < beta)
-              continue;
-      }
-
-
       // Futility pruning
       if (   !isCheck
           && !dangerous
@@ -1594,18 +1645,18 @@ namespace {
           // Value based pruning
           Depth predictedDepth = newDepth;
 
-          //FIXME HACK: awful code duplication
-          double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0;
-          if (red >= 1.0)
-              predictedDepth -= int(floor(red * int(OnePly)));
+          //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG??
+          ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
+          if (ss[ply].reduction)
+              predictedDepth -= ss[ply].reduction;
 
           if (predictedDepth < SelectiveDepth)
           {
               int preFutilityValueMargin = 0;
               if (predictedDepth >= OnePly)
-                  preFutilityValueMargin = 112 * bitScanReverse32(int(predictedDepth) * int(predictedDepth) / 2);
+                  preFutilityValueMargin = FutilityMargins[int(predictedDepth)];
 
-              preFutilityValueMargin += MG.retrieve(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45;
+              preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45;
 
               futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin;
 
@@ -1629,13 +1680,11 @@ namespace {
           && !dangerous
           && !captureOrPromotion
           && !move_is_castle(move)
-          && !move_is_killer(move, ss[ply])
-          /* && move != ttMove*/)
+          && !move_is_killer(move, ss[ply]))
       {
-          double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0;
-          if (red >= 1.0)
+          ss[ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
+          if (ss[ply].reduction)
           {
-              ss[ply].reduction = Depth(int(floor(red * int(OnePly))));
               value = -search(pos, ss, -(beta-1), newDepth-ss[ply].reduction, ply+1, true, threadID);
               doFullDepthSearch = (value >= beta);
           }
@@ -1726,6 +1775,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.
@@ -1764,16 +1814,9 @@ namespace {
     if (!isCheck)
     {
         ss[ply].eval = staticValue;
-        // Store gain statistics
-        Move m = ss[ply - 1].currentMove;
-        if (   m != MOVE_NULL
-            && pos.captured_piece() == NO_PIECE_TYPE
-            && !move_is_castle(m)
-            && !move_is_promotion(m))
-            MG.store(pos.piece_on(move_to(m)), move_from(m), move_to(m), ss[ply - 1].eval, -ss[ply].eval);
+        update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
     }
 
-
     // Initialize "stand pat score", and return it immediately if it is
     // at least beta.
     bestValue = staticValue;
@@ -1876,14 +1919,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);
@@ -1892,6 +1935,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);
 
@@ -1917,28 +1962,33 @@ namespace {
     SearchStack* ss = sp->sstack[threadID];
     Value value = -VALUE_INFINITE;
     Move move;
+    int moveCount;
     bool isCheck = pos.is_check();
     bool useFutilityPruning =     sp->depth < SelectiveDepth
                               && !isCheck;
 
     const int FutilityMoveCountMargin = 3 + (1 << (3 * int(sp->depth) / 8));
 
-    while (    sp->bestValue < sp->beta
+    // 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)
-           && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
+           && (move = sp->mp->get_next_move()) != MOVE_NONE)
     {
+      moveCount = ++sp->moves;
+      lock_release(&(sp->lock));
+
       assert(move_is_ok(move));
 
       bool moveIsCheck = pos.move_is_check(move, ci);
       bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
 
-      lock_grab(&(sp->lock));
-      int moveCount = ++sp->moves;
-      lock_release(&(sp->lock));
-
       ss[sp->ply].currentMove = move;
 
-      // Decide the new search depth.
+      // Decide the new search depth
       bool dangerous;
       Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous);
       Depth newDepth = sp->depth - OnePly + ext;
@@ -1983,10 +2033,9 @@ namespace {
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 3.0;
-          if (red >= 1.0)
+          ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
+          if (ss[sp->ply].reduction)
           {
-              ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly))));
               value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
               doFullDepthSearch = (value >= sp->beta);
           }
@@ -2002,7 +2051,10 @@ namespace {
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
       if (thread_should_stop(threadID))
+      {
+          lock_grab(&(sp->lock));
           break;
+      }
 
       // New best move?
       if (value > sp->bestValue) // Less then 2% of cases
@@ -2025,7 +2077,7 @@ namespace {
       }
     }
 
-    lock_grab(&(sp->lock));
+    /* Here we have the lock still grabbed */
 
     // If this is the master thread and we have been asked to stop because of
     // a beta cutoff higher up in the tree, stop all slave threads.
@@ -2058,24 +2110,29 @@ namespace {
     CheckInfo ci(pos);
     SearchStack* ss = sp->sstack[threadID];
     Value value = -VALUE_INFINITE;
+    int moveCount;
     Move move;
 
-    while (    sp->alpha < sp->beta
+    // 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)
-           && (move = sp->mp->get_next_move(sp->lock)) != MOVE_NONE)
+           && (move = sp->mp->get_next_move()) != MOVE_NONE)
     {
-      bool moveIsCheck = pos.move_is_check(move, ci);
-      bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
+      moveCount = ++sp->moves;
+      lock_release(&(sp->lock));
 
       assert(move_is_ok(move));
 
-      lock_grab(&(sp->lock));
-      int moveCount = ++sp->moves;
-      lock_release(&(sp->lock));
+      bool moveIsCheck = pos.move_is_check(move, ci);
+      bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
 
       ss[sp->ply].currentMove = move;
 
-      // Decide the new search depth.
+      // Decide the new search depth
       bool dangerous;
       Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
       Depth newDepth = sp->depth - OnePly + ext;
@@ -2093,11 +2150,10 @@ namespace {
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 6.0;
-          if (red >= 1.0)
+          ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
+          if (ss[sp->ply].reduction)
           {
               Value localAlpha = sp->alpha;
-              ss[sp->ply].reduction = Depth(int(floor(red * int(OnePly))));
               value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
               doFullDepthSearch = (value > localAlpha);
           }
@@ -2135,7 +2191,10 @@ namespace {
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
       if (thread_should_stop(threadID))
+      {
+          lock_grab(&(sp->lock));
           break;
+      }
 
       // New best move?
       if (value > sp->bestValue) // Less then 2% of cases
@@ -2174,7 +2233,7 @@ namespace {
       }
     }
 
-    lock_grab(&(sp->lock));
+    /* Here we have the lock still grabbed */
 
     // If this is the master thread and we have been asked to stop because of
     // a beta cutoff higher up in the tree, stop all slave threads.
@@ -2618,6 +2677,35 @@ namespace {
       return defaultEval;
   }
 
+
+  // 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.
+
+  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;
+  }
+
+
+  // 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.
 
@@ -2655,6 +2743,21 @@ namespace {
   }
 
 
+  // update_gains() updates the gains table of a non-capture move given
+  // the static position evaluation before and after the move.
+
+  void update_gains(const Position& pos, Move m, Value before, Value after) {
+
+    if (   m != MOVE_NULL
+        && before != VALUE_NONE
+        && after != VALUE_NONE
+        && pos.captured_piece() == NO_PIECE_TYPE
+        && !move_is_castle(m)
+        && !move_is_promotion(m))
+        H.set_gain(pos.piece_on(move_to(m)), move_from(m), move_to(m), -(before + after));
+  }
+
+
   // fail_high_ply_1() checks if some thread is currently resolving a fail
   // high at ply 1 at the node below the first root node.  This information
   // is used for time management.