X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=4ea31a0b36dcde97bda492310b681fcec6025cf5;hp=660fb7ed4f045d85f886b10c3d8687be24fe2368;hb=35ada63174bbec6289d6dea6d3cfc5b5f14d1d27;hpb=721d5576811e5b641f73c07bdeb122d114cae7ca

diff --git a/src/search.cpp b/src/search.cpp
index 660fb7ed..4ea31a0b 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -23,6 +23,7 @@
 ////
 
 #include <cassert>
+#include <cmath>
 #include <cstring>
 #include <fstream>
 #include <iostream>
@@ -100,7 +101,7 @@ namespace {
     // sorting the moves. A move m1 is considered to be better
     // than a move m2 if it has a higher score, or if the moves
     // have equal score but m1 has the higher node count.
-    bool RootMove::operator<(const RootMove& m) const {
+    bool operator<(const RootMove& m) const {
 
         return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
     }
@@ -172,9 +173,9 @@ namespace {
   // best move from the previous iteration, Problem is set back to false.
   const Value NoProblemMargin = Value(0x14);
 
-  // Null move margin. A null move search will not be done if the approximate
+  // Null move margin. A null move search will not be done if the static
   // evaluation of the position is more than NullMoveMargin below beta.
-  const Value NullMoveMargin = Value(0x300);
+  const Value NullMoveMargin = Value(0x200);
 
   // If the TT move is at least SingleReplyMargin better then the
   // remaining ones we will extend it.
@@ -184,24 +185,16 @@ 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);
 
   // Depth limit for razoring
   const Depth RazorDepth = 4 * OnePly;
 
-  // Remaining depth:                 1 ply         1.5 ply       2 ply         2.5 ply       3 ply         3.5 ply
-  const Value RazorMargins[6]     = { Value(0x180), Value(0x300), Value(0x300), Value(0x3C0), Value(0x3C0), Value(0x3C0) };
-
-  // Remaining depth:                 1 ply         1.5 ply       2 ply         2.5 ply       3 ply         3.5 ply
-  const Value RazorApprMargins[6] = { Value(0x520), Value(0x300), Value(0x300), Value(0x300), Value(0x300), Value(0x300) };
-
-
   /// Variables initialized by UCI options
 
-  // Minimum number of full depth (i.e. non-reduced) moves at PV and non-PV nodes
-  int LMRPVMoves, LMRNonPVMoves;
-
   // Depth limit for use of dynamic threat detection
   Depth ThreatDepth;
 
@@ -223,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;
 
@@ -231,7 +227,7 @@ namespace {
   int SearchStartTime;
   int MaxNodes, MaxDepth;
   int MaxSearchTime, AbsoluteMaxSearchTime, ExtraSearchTime, ExactMaxTime;
-  bool InfiniteSearch, PonderSearch, StopOnPonderhit;
+  bool UseTimeManagement, InfiniteSearch, PonderSearch, StopOnPonderhit;
   bool AbortSearch, Quit;
   bool FailHigh, FailLow, Problem;
 
@@ -242,6 +238,10 @@ namespace {
   bool UseLogFile;
   std::ofstream LogFile;
 
+  // Natural logarithmic lookup table and its getter function
+  float lnArray[512];
+  inline float ln(int i) { return lnArray[i]; }
+
   // MP related variables
   int ActiveThreads = 1;
   Depth MinimumSplitDepth;
@@ -268,11 +268,10 @@ namespace {
   // History table
   History H;
 
-
   /// 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);
@@ -288,8 +287,12 @@ 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 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();
@@ -365,8 +368,20 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
            int time[], int increment[], int movesToGo, int maxDepth,
            int maxNodes, int maxTime, Move searchMoves[]) {
 
-  // Look for a book move
-  if (!infinite && !ponder && get_option_value_bool("OwnBook"))
+  // Initialize global search variables
+  Idle = StopOnPonderhit = AbortSearch = Quit = false;
+  FailHigh = FailLow = Problem = false;
+  NodesSincePoll = 0;
+  SearchStartTime = get_system_time();
+  ExactMaxTime = maxTime;
+  MaxDepth = maxDepth;
+  MaxNodes = maxNodes;
+  InfiniteSearch = infinite;
+  PonderSearch = ponder;
+  UseTimeManagement = !ExactMaxTime && !MaxDepth && !MaxNodes && !InfiniteSearch;
+
+  // Look for a book move, only during games, not tests
+  if (UseTimeManagement && !ponder && get_option_value_bool("OwnBook"))
   {
       Move bookMove;
       if (get_option_value_string("Book File") != OpeningBook.file_name())
@@ -380,15 +395,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
       }
   }
 
-  // Initialize global search variables
-  Idle = StopOnPonderhit = AbortSearch = Quit = false;
-  FailHigh = FailLow = Problem = false;
-  SearchStartTime = get_system_time();
-  ExactMaxTime = maxTime;
-  NodesSincePoll = 0;
-  InfiniteSearch = infinite;
-  PonderSearch = ponder;
-
   for (int i = 0; i < THREAD_MAX; i++)
   {
       Threads[i].nodes = 0ULL;
@@ -424,8 +430,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)"));
   MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)"));
 
-  LMRPVMoves    = get_option_value_int("Full Depth Moves (PV nodes)") + 1;
-  LMRNonPVMoves = get_option_value_int("Full Depth Moves (non-PV nodes)") + 1;
   ThreatDepth   = get_option_value_int("Threat Depth") * OnePly;
 
   Chess960 = get_option_value_bool("UCI_Chess960");
@@ -445,6 +449,10 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   {
       ActiveThreads = newActiveThreads;
       init_eval(ActiveThreads);
+      // HACK: init_eval() destroys the static castleRightsMask[] array in the
+      // Position class. The below line repairs the damage.
+      Position p(pos.to_fen());
+      assert(pos.is_ok());
   }
 
   // Wake up sleeping threads
@@ -456,51 +464,45 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   // Set thinking time
   int myTime = time[side_to_move];
   int myIncrement = increment[side_to_move];
-
-  if (!movesToGo) // Sudden death time control
+  if (UseTimeManagement)
   {
-      if (myIncrement)
-      {
-          MaxSearchTime = myTime / 30 + myIncrement;
-          AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
-      }
-      else // Blitz game without increment
+      if (!movesToGo) // Sudden death time control
       {
-          MaxSearchTime = myTime / 30;
-          AbsoluteMaxSearchTime = myTime / 8;
+          if (myIncrement)
+          {
+              MaxSearchTime = myTime / 30 + myIncrement;
+              AbsoluteMaxSearchTime = Max(myTime / 4, myIncrement - 100);
+          }
+          else // Blitz game without increment
+          {
+              MaxSearchTime = myTime / 30;
+              AbsoluteMaxSearchTime = myTime / 8;
+          }
       }
-  }
-  else // (x moves) / (y minutes)
-  {
-      if (movesToGo == 1)
+      else // (x moves) / (y minutes)
       {
-          MaxSearchTime = myTime / 2;
-          AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
+          if (movesToGo == 1)
+          {
+              MaxSearchTime = myTime / 2;
+              AbsoluteMaxSearchTime = (myTime > 3000)? (myTime - 500) : ((myTime * 3) / 4);
+          }
+          else
+          {
+              MaxSearchTime = myTime / Min(movesToGo, 20);
+              AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
+          }
       }
-      else
+
+      if (PonderingEnabled)
       {
-          MaxSearchTime = myTime / Min(movesToGo, 20);
-          AbsoluteMaxSearchTime = Min((4 * myTime) / movesToGo, myTime / 3);
+          MaxSearchTime += MaxSearchTime / 4;
+          MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
       }
   }
 
-  if (PonderingEnabled)
-  {
-      MaxSearchTime += MaxSearchTime / 4;
-      MaxSearchTime = Min(MaxSearchTime, AbsoluteMaxSearchTime);
-  }
-
-  // Fixed depth or fixed number of nodes?
-  MaxDepth = maxDepth;
-  if (MaxDepth)
-      InfiniteSearch = true; // HACK
-
-  MaxNodes = maxNodes;
+  // Set best NodesBetweenPolls interval
   if (MaxNodes)
-  {
       NodesBetweenPolls = Min(MaxNodes, 30000);
-      InfiniteSearch = true; // HACK
-  }
   else if (myTime && myTime < 1000)
       NodesBetweenPolls = 1000;
   else if (myTime && myTime < 5000)
@@ -529,7 +531,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
   // We're ready to start thinking. Call the iterative deepening loop function
   Value v = id_loop(pos, searchMoves);
 
-
   if (UseLSNFiltering)
   {
       // Step 1. If this is sudden death game and our position is hopeless,
@@ -564,14 +565,27 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move,
 void init_threads() {
 
   volatile int i;
+  bool ok;
 
 #if !defined(_MSC_VER)
   pthread_t pthread[1];
 #endif
 
+  // Init our logarithmic lookup table
+  for (i = 0; i < 512; i++)
+      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);
@@ -599,12 +613,18 @@ void init_threads() {
   for (i = 1; i < THREAD_MAX; i++)
   {
 #if !defined(_MSC_VER)
-      pthread_create(pthread, NULL, init_thread, (void*)(&i));
+      ok = (pthread_create(pthread, NULL, init_thread, (void*)(&i)) == 0);
 #else
       DWORD iID[1];
-      CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID);
+      ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&i), 0, iID) != NULL);
 #endif
 
+      if (!ok)
+      {
+          cout << "Failed to create thread number " << i << endl;
+          Application::exit_with_failure();
+      }
+
       // Wait until the thread has finished launching
       while (!Threads[i].running);
   }
@@ -648,6 +668,8 @@ void SearchStack::init(int ply) {
   pv[ply] = pv[ply + 1] = MOVE_NONE;
   currentMove = threatMove = MOVE_NONE;
   reduction = Depth(0);
+  eval = VALUE_NONE;
+  evalInfo = NULL;
 }
 
 void SearchStack::initKillers() {
@@ -672,6 +694,7 @@ namespace {
     // searchMoves are verified, copied, scored and sorted
     RootMoveList rml(p, searchMoves);
 
+    // Handle special case of searching on a mate/stale position
     if (rml.move_count() == 0)
     {
         if (PonderSearch)
@@ -722,10 +745,11 @@ 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);
+            AspirationDelta = Max(abs(prevDelta1) + abs(prevDelta2) / 2, 16);
+            AspirationDelta = (AspirationDelta + 7) / 8 * 8; // Round to match grainSize
 
-            alpha = Max(IterationInfo[Iteration - 1].value - delta, -VALUE_INFINITE);
-            beta  = Min(IterationInfo[Iteration - 1].value + delta,  VALUE_INFINITE);
+            alpha = Max(IterationInfo[Iteration - 1].value - AspirationDelta, -VALUE_INFINITE);
+            beta  = Min(IterationInfo[Iteration - 1].value + AspirationDelta,  VALUE_INFINITE);
         }
         else
         {
@@ -777,7 +801,7 @@ namespace {
 
         Problem = false;
 
-        if (!InfiniteSearch)
+        if (UseTimeManagement)
         {
             // Time to stop?
             bool stopSearch = false;
@@ -831,9 +855,9 @@ namespace {
 
     rml.sort();
 
-    // If we are pondering, we shouldn't print the best move before we
-    // are told to do so
-    if (PonderSearch)
+    // If we are pondering or in infinite search, we shouldn't print the
+    // best move before we are told to do so.
+    if (!AbortSearch && (PonderSearch || InfiniteSearch))
         wait_for_stop_or_ponderhit();
     else
         // Print final search statistics
@@ -878,11 +902,25 @@ 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;
+    int64_t nodes;
+    Move move;
+    StateInfo st;
+    Depth depth, ext, newDepth;
     Value value;
     CheckInfo ci(pos);
+    int researchCount = 0;
+    bool moveIsCheck, captureOrPromotion, dangerous;
+    Value alpha = oldAlpha;
+    bool isCheck = pos.is_check();
+
+    // Evaluate the position statically
+    EvalInfo ei;
+    ss[0].eval = !isCheck ? evaluate(pos, ei, 0) : 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++)
@@ -895,10 +933,6 @@ namespace {
             rml.set_move_score(i, -VALUE_INFINITE);
             continue;
         }
-        int64_t nodes;
-        Move move;
-        StateInfo st;
-        Depth ext, newDepth;
 
         RootMoveNumber = i + 1;
         FailHigh = false;
@@ -918,16 +952,25 @@ namespace {
                  << " currmovenumber " << RootMoveNumber << endl;
 
         // Decide search depth for this move
-        bool moveIsCheck = pos.move_is_check(move);
-        bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
-        bool dangerous;
+        moveIsCheck = pos.move_is_check(move);
+        captureOrPromotion = pos.move_is_capture_or_promotion(move);
+        depth = (Iteration - 2) * OnePly + InitialDepth;
         ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
-        newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
+        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)
@@ -949,19 +992,24 @@ 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 (   newDepth >= 3*OnePly
-                && i >= MultiPV + LMRPVMoves
+            bool doFullDepthSearch = true;
+
+            if (   depth >= 3*OnePly // FIXME was newDepth
                 && !dangerous
                 && !captureOrPromotion
                 && !move_is_castle(move))
             {
-                ss[0].reduction = OnePly;
-                value = -search(pos, ss, -alpha, newDepth-OnePly, 1, true, 0);
-            } else
-                value = alpha + 1; // Just to trigger next condition
+                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);
+                    doFullDepthSearch = (value > alpha);
+                }
+            }
 
-            if (value > alpha)
+            if (doFullDepthSearch)
             {
+                ss[0].reduction = Depth(0);
                 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
 
                 if (value > alpha)
@@ -978,6 +1026,47 @@ namespace {
 
         pos.undo_move(move);
 
+        // Can we exit fail high loop ?
+        if (AbortSearch || value < beta)
+            break;
+
+        // 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 a research after a fail high, each time with a wider window
+        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
@@ -1072,6 +1161,18 @@ namespace {
 
         FailLow = (alpha == oldAlpha);
     }
+
+    // Can we exit fail low loop ?
+    if (AbortSearch || alpha > oldAlpha)
+        break;
+
+    // Prepare for a research after a fail low, each time with a wider window
+    researchCount++;
+    alpha = Max(alpha - AspirationDelta * (1 << researchCount), -VALUE_INFINITE);
+    oldAlpha = alpha;
+
+    } // Fail low loop
+
     return alpha;
   }
 
@@ -1087,7 +1188,6 @@ namespace {
     assert(threadID >= 0 && threadID < ActiveThreads);
 
     Move movesSearched[256];
-    EvalInfo ei;
     StateInfo st;
     const TTEntry* tte;
     Move ttMove, move;
@@ -1095,7 +1195,7 @@ namespace {
     Value oldAlpha, value;
     bool isCheck, mateThreat, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
     int moveCount = 0;
-    Value bestValue = -VALUE_INFINITE;
+    Value bestValue = value = -VALUE_INFINITE;
 
     if (depth < OnePly)
         return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID);
@@ -1108,12 +1208,9 @@ namespace {
     if (AbortSearch || thread_should_stop(threadID))
         return Value(0);
 
-    if (pos.is_draw())
+    if (pos.is_draw() || ply >= PLY_MAX - 1)
         return VALUE_DRAW;
 
-    if (ply >= PLY_MAX - 1)
-        return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID);
-
     // Mate distance pruning
     oldAlpha = alpha;
     alpha = Max(value_mated_in(ply), alpha);
@@ -1143,13 +1240,26 @@ namespace {
         tte = TT.retrieve(pos.get_key());
     }
 
+    isCheck = pos.is_check();
+    if (!isCheck)
+    {
+        // Update gain statistics of the previous move that lead
+        // us in this position.
+        EvalInfo ei;
+        ss[ply].eval = evaluate(pos, ei, threadID);
+        update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
+    }
+
     // Initialize a MovePicker object for the current position, and prepare
     // to search all moves
-    isCheck = pos.is_check();
     mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
     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
@@ -1200,20 +1310,23 @@ 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.
+        bool doFullDepthSearch = true;
+
         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);
+            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);
+            }
         }
-        else
-            value = alpha + 1; // Just to trigger next condition
 
-        if (value > alpha) // Go with full depth non-pv search
+        if (doFullDepthSearch) // Go with full depth non-pv search
         {
             ss[ply].reduction = Depth(0);
             value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
@@ -1316,11 +1429,11 @@ namespace {
     const TTEntry* tte;
     Move ttMove, move;
     Depth ext, newDepth;
-    Value approximateEval, nullValue, value, futilityValue, futilityValueScaled;
-    bool isCheck, useFutilityPruning, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
+    Value bestValue, staticValue, nullValue, value, futilityValue, futilityValueScaled;
+    bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous;
     bool mateThreat = false;
     int moveCount = 0;
-    Value bestValue = -VALUE_INFINITE;
+    futilityValue = staticValue = bestValue = value = -VALUE_INFINITE;
 
     if (depth < OnePly)
         return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
@@ -1333,12 +1446,9 @@ namespace {
     if (AbortSearch || thread_should_stop(threadID))
         return Value(0);
 
-    if (pos.is_draw())
+    if (pos.is_draw() || ply >= PLY_MAX - 1)
         return VALUE_DRAW;
 
-    if (ply >= PLY_MAX - 1)
-        return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID);
-
     // Mate distance pruning
     if (value_mated_in(ply) >= beta)
         return beta;
@@ -1360,26 +1470,53 @@ namespace {
         return value_from_tt(tte->value(), ply);
     }
 
-    approximateEval = quick_evaluate(pos);
     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)
+    {
+        if (tte && (tte->type() & VALUE_TYPE_EVAL))
+            staticValue = value_from_tt(tte->value(), ply);
+        else
+        {
+            staticValue = evaluate(pos, ei, threadID);
+            ss[ply].evalInfo = &ei;
+        }
+
+        ss[ply].eval = staticValue;
+        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.
+    if (  !isCheck
+        && allowNullmove
+        && depth < RazorDepth
+        && staticValue - FutilityMargins[int(depth)] >= beta)
+        return staticValue - FutilityMargins[int(depth)];
+
     // Null move search
     if (    allowNullmove
         &&  depth > OnePly
         && !isCheck
         && !value_is_mate(beta)
         &&  ok_to_do_nullmove(pos)
-        &&  approximateEval >= beta - NullMoveMargin)
+        &&  staticValue >= beta - NullMoveMargin)
     {
         ss[ply].currentMove = MOVE_NULL;
 
         pos.do_null_move(st);
 
         // Null move dynamic reduction based on depth
-        int R = (depth >= 5 * OnePly ? 4 : 3);
+        int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
 
         // Null move dynamic reduction based on value
-        if (approximateEval - beta > PawnValueMidgame)
+        if (staticValue - beta > PawnValueMidgame)
             R++;
 
         nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);
@@ -1414,13 +1551,14 @@ namespace {
     }
     // Null move search not allowed, try razoring
     else if (   !value_is_mate(beta)
+             && !isCheck
              && depth < RazorDepth
-             && approximateEval < beta - RazorApprMargins[int(depth) - 2]
+             && staticValue < beta - (NullMoveMargin + 16 * depth)
              && ss[ply - 1].currentMove != MOVE_NULL
              && ttMove == MOVE_NONE
              && !pos.has_pawn_on_7th(pos.side_to_move()))
     {
-        Value rbeta = beta - RazorMargins[int(depth) - 2];
+        Value rbeta = beta - (NullMoveMargin + 16 * depth);
         Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
         if (v < rbeta)
           return v;
@@ -1428,7 +1566,7 @@ namespace {
 
     // Go with internal iterative deepening if we don't have a TT move
     if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
-        !isCheck && evaluate(pos, ei, threadID) >= beta - IIDMargin)
+        !isCheck && ss[ply].eval >= beta - IIDMargin)
     {
         search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
         ttMove = ss[ply].pv[ply];
@@ -1439,16 +1577,10 @@ namespace {
     // to search all moves.
     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
     CheckInfo ci(pos);
-    futilityValue = VALUE_NONE;
-    useFutilityPruning = depth < SelectiveDepth && !isCheck;
-
-    // Calculate depth dependant futility pruning parameters
-    const int FutilityMoveCountMargin = 3 + (1 << (3 * int(depth) / 8));
-    const int FutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2);
 
-    // Avoid calling evaluate() if we already have the score in TT
-    if (tte && (tte->type() & VALUE_TYPE_EVAL))
-        futilityValue = value_from_tt(tte->value(), ply) + FutilityValueMargin;
+    // 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
@@ -1460,8 +1592,8 @@ namespace {
       if (move == excludedMove)
           continue;
 
-      singleEvasion = (isCheck && mp.number_of_evasions() == 1);
       moveIsCheck = pos.move_is_check(move, ci);
+      singleEvasion = (isCheck && mp.number_of_evasions() == 1);
       captureOrPromotion = pos.move_is_capture_or_promotion(move);
 
       // Decide the new search depth
@@ -1495,9 +1627,10 @@ namespace {
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
       // Futility pruning
-      if (    useFutilityPruning
+      if (   !isCheck
           && !dangerous
           && !captureOrPromotion
+          && !move_is_castle(move)
           &&  move != ttMove)
       {
           // Move count based pruning
@@ -1507,16 +1640,29 @@ namespace {
               continue;
 
           // Value based pruning
-          if (futilityValue == VALUE_NONE)
-              futilityValue = evaluate(pos, ei, threadID) + FutilityValueMargin;
+          Depth predictedDepth = newDepth;
 
-          futilityValueScaled = futilityValue - moveCount * IncrementalFutilityMargin;
+          //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 (futilityValueScaled < beta)
+          if (predictedDepth < SelectiveDepth)
           {
-              if (futilityValueScaled > bestValue)
-                  bestValue = futilityValueScaled;
-              continue;
+              int preFutilityValueMargin = 0;
+              if (predictedDepth >= OnePly)
+                  preFutilityValueMargin = FutilityMargins[int(predictedDepth)];
+
+              preFutilityValueMargin += H.gain(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45;
+
+              futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin;
+
+              if (futilityValueScaled < beta)
+              {
+                  if (futilityValueScaled > bestValue)
+                      bestValue = futilityValueScaled;
+                  continue;
+              }
           }
       }
 
@@ -1525,20 +1671,23 @@ 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.
+      bool doFullDepthSearch = true;
+
       if (    depth >= 3*OnePly
-          &&  moveCount >= LMRNonPVMoves
           && !dangerous
           && !captureOrPromotion
           && !move_is_castle(move)
           && !move_is_killer(move, ss[ply]))
       {
-          ss[ply].reduction = OnePly;
-          value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
+          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);
+              doFullDepthSearch = (value >= beta);
+          }
       }
-      else
-          value = beta; // Just to trigger next condition
 
-      if (value >= beta) // Go with full depth non-pv search
+      if (doFullDepthSearch) // Go with full depth non-pv search
       {
           ss[ply].reduction = Depth(0);
           value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
@@ -1566,14 +1715,14 @@ namespace {
           && idle_thread_exists(threadID)
           && !AbortSearch
           && !thread_should_stop(threadID)
-          && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue,
+          && split(pos, ss, ply, &beta, &beta, &bestValue, futilityValue, //FIXME: SMP & futilityValue
                    depth, &moveCount, &mp, threadID, false))
           break;
     }
 
-    // All legal moves have been searched.  A special case: If there were
+    // All legal moves have been searched. A special case: If there were
     // no legal moves, it must be mate or stalemate.
-    if (moveCount == 0)
+    if (!moveCount)
         return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
 
     // If the search is not aborted, update the transposition table,
@@ -1587,12 +1736,13 @@ namespace {
     {
         BetaCounter.add(pos.side_to_move(), depth, threadID);
         move = ss[ply].pv[ply];
+        TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
         if (!pos.move_is_capture_or_promotion(move))
         {
             update_history(pos, move, depth, movesSearched, moveCount);
             update_killers(move, ss[ply]);
         }
-        TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
+
     }
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
@@ -1617,11 +1767,12 @@ namespace {
     EvalInfo ei;
     StateInfo st;
     Move ttMove, move;
-    Value staticValue, bestValue, value, futilityValue;
-    bool isCheck, enoughMaterial, moveIsCheck;
+    Value staticValue, bestValue, value, futilityBase, futilityValue;
+    bool isCheck, enoughMaterial, moveIsCheck, evasionPrunable;
     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.
@@ -1631,41 +1782,37 @@ namespace {
     if (AbortSearch || thread_should_stop(threadID))
         return Value(0);
 
-    if (pos.is_draw())
+    if (pos.is_draw() || ply >= PLY_MAX - 1)
         return VALUE_DRAW;
 
-    // Transposition table lookup, only when not in PV
-    if (!pvNode)
+    // Transposition table lookup. At PV nodes, we don't use the TT for
+    // pruning, but only for move ordering.
+    tte = TT.retrieve(pos.get_key());
+    ttMove = (tte ? tte->move() : MOVE_NONE);
+
+    if (!pvNode && tte && ok_to_use_TT(tte, depth, beta, ply))
     {
-        tte = TT.retrieve(pos.get_key());
-        if (tte && ok_to_use_TT(tte, depth, beta, ply))
-        {
-            assert(tte->type() != VALUE_TYPE_EVAL);
+        assert(tte->type() != VALUE_TYPE_EVAL);
 
-            return value_from_tt(tte->value(), ply);
-        }
+        ss[ply].currentMove = ttMove; // Can be MOVE_NONE
+        return value_from_tt(tte->value(), ply);
     }
-    ttMove = (tte ? tte->move() : MOVE_NONE);
 
     isCheck = pos.is_check();
-    ei.futilityMargin = Value(0); // Manually initialize futilityMargin
 
     // Evaluate the position statically
     if (isCheck)
         staticValue = -VALUE_INFINITE;
-
     else if (tte && (tte->type() & VALUE_TYPE_EVAL))
-    {
-        // Use the cached evaluation score if possible
-        assert(ei.futilityMargin == Value(0));
-
         staticValue = value_from_tt(tte->value(), ply);
-    }
     else
         staticValue = evaluate(pos, ei, threadID);
 
-    if (ply >= PLY_MAX - 1)
-        return pos.is_check() ? quick_evaluate(pos) : evaluate(pos, ei, threadID);
+    if (!isCheck)
+    {
+        ss[ply].eval = staticValue;
+        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.
@@ -1674,7 +1821,7 @@ namespace {
     if (bestValue >= beta)
     {
         // Store the score to avoid a future costly evaluation() call
-        if (!isCheck && !tte && ei.futilityMargin == 0)
+        if (!isCheck && !tte && ei.futilityMargin[pos.side_to_move()] == 0)
             TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_EV_LO, Depth(-127*OnePly), MOVE_NONE);
 
         return bestValue;
@@ -1683,12 +1830,17 @@ namespace {
     if (bestValue > alpha)
         alpha = bestValue;
 
+    // If we are near beta then try to get a cutoff pushing checks a bit further
+    bool deepChecks = depth == -OnePly && staticValue >= beta - PawnValueMidgame / 8;
+
     // Initialize a MovePicker object for the current position, and prepare
-    // to search the moves.  Because the depth is <= 0 here, only captures,
-    // queen promotions and checks (only if depth == 0) will be generated.
-    MovePicker mp = MovePicker(pos, ttMove, depth, H);
+    // to search the moves. Because the depth is <= 0 here, only captures,
+    // queen promotions and checks (only if depth == 0 or depth == -OnePly
+    // and we are near beta) will be generated.
+    MovePicker mp = MovePicker(pos, ttMove, deepChecks ? Depth(0) : depth, H);
     CheckInfo ci(pos);
     enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMidgame;
+    futilityBase = staticValue + FutilityMarginQS + ei.futilityMargin[pos.side_to_move()];
 
     // Loop through the moves until no moves remain or a beta cutoff
     // occurs.
@@ -1697,11 +1849,12 @@ namespace {
     {
       assert(move_is_ok(move));
 
+      moveIsCheck = pos.move_is_check(move, ci);
+
+      // Update current move
       moveCount++;
       ss[ply].currentMove = move;
 
-      moveIsCheck = pos.move_is_check(move, ci);
-
       // Futility pruning
       if (   enoughMaterial
           && !isCheck
@@ -1711,12 +1864,9 @@ namespace {
           && !move_is_promotion(move)
           && !pos.move_is_passed_pawn_push(move))
       {
-          futilityValue =  staticValue
-                         + Max(pos.midgame_value_of_piece_on(move_to(move)),
-                               pos.endgame_value_of_piece_on(move_to(move)))
-                         + (move_is_ep(move) ? PawnValueEndgame : Value(0))
-                         + FutilityMarginQS
-                         + ei.futilityMargin;
+          futilityValue =  futilityBase
+                         + pos.endgame_value_of_piece_on(move_to(move))
+                         + (move_is_ep(move) ? PawnValueEndgame : Value(0));
 
           if (futilityValue < alpha)
           {
@@ -1726,8 +1876,15 @@ namespace {
           }
       }
 
-      // Don't search captures and checks with negative SEE values
-      if (   !isCheck
+      // Detect blocking evasions that are candidate to be pruned
+      evasionPrunable =   isCheck
+                       && bestValue != -VALUE_INFINITE
+                       && !pos.move_is_capture(move)
+                       && pos.type_of_piece_on(move_from(move)) != KING
+                       && !pos.can_castle(pos.side_to_move());
+
+      // Don't search moves with negative SEE values
+      if (   (!isCheck || evasionPrunable)
           &&  move != ttMove
           && !move_is_promotion(move)
           &&  pos.see_sign(move) < 0)
@@ -1752,31 +1909,33 @@ namespace {
        }
     }
 
-    // All legal moves have been searched.  A special case: If we're in check
+    // All legal moves have been searched. A special case: If we're in check
     // and no legal moves were found, it is checkmate.
     if (!moveCount && pos.is_check()) // Mate!
         return value_mated_in(ply);
 
-    assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
-
     // Update transposition table
-    move = ss[ply].pv[ply];
-    if (!pvNode)
+    Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
+    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 costly evaluation() call.
-        ValueType type = (bestValue == staticValue && !ei.futilityMargin ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
-        Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
+        // 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[pos.side_to_move()] ? VALUE_TYPE_EV_UP : VALUE_TYPE_UPPER);
+        TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
+    }
+    else if (bestValue >= beta)
+    {
+        move = ss[ply].pv[ply];
+        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
 
-        if (bestValue < beta)
-            TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
-        else
-            TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, d, move);
+        // Update killers only for good checking moves
+        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]);
 
-    // Update killers only for good check moves
-    if (alpha >= beta && !pos.move_is_capture_or_promotion(move))
-        update_killers(move, ss[ply]);
+    assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
     return bestValue;
   }
@@ -1795,34 +1954,38 @@ namespace {
     assert(threadID >= 0 && threadID < ActiveThreads);
     assert(ActiveThreads > 1);
 
-    Position pos = Position(sp->pos);
+    Position pos(*sp->pos);
     CheckInfo ci(pos);
     SearchStack* ss = sp->sstack[threadID];
-    Value value;
+    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));
-    const int FutilityValueMargin = 112 * bitScanReverse32(int(sp->depth) * int(sp->depth) / 2);
 
-    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;
@@ -1839,12 +2002,6 @@ namespace {
               continue;
 
           // Value based pruning
-          if (sp->futilityValue == VALUE_NONE)
-          {
-              EvalInfo ei;
-              sp->futilityValue = evaluate(pos, ei, threadID) + FutilityValueMargin;
-          }
-
           Value futilityValueScaled = sp->futilityValue - moveCount * IncrementalFutilityMargin;
 
           if (futilityValueScaled < sp->beta)
@@ -1866,19 +2023,22 @@ 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.
+      bool doFullDepthSearch = true;
+
       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);
+          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);
+              doFullDepthSearch = (value >= sp->beta);
+          }
       }
-      else
-          value = sp->beta; // Just to trigger next condition
 
-      if (value >= sp->beta) // Go with full depth non-pv search
+      if (doFullDepthSearch) // Go with full depth non-pv search
       {
           ss[sp->ply].reduction = Depth(0);
           value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
@@ -1888,7 +2048,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
@@ -1911,7 +2074,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.
@@ -1940,28 +2103,33 @@ namespace {
     assert(threadID >= 0 && threadID < ActiveThreads);
     assert(ActiveThreads > 1);
 
-    Position pos = Position(sp->pos);
+    Position pos(*sp->pos);
     CheckInfo ci(pos);
     SearchStack* ss = sp->sstack[threadID];
-    Value value;
+    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;
@@ -1972,34 +2140,46 @@ 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.
+      bool doFullDepthSearch = true;
+
       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);
+          ss[sp->ply].reduction = reduction(moveCount, LogLimit, BaseReduction, Gradient);
+          if (ss[sp->ply].reduction)
+          {
+              Value localAlpha = sp->alpha;
+              value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
+              doFullDepthSearch = (value > localAlpha);
+          }
       }
-      else
-          value = sp->alpha + 1; // Just to trigger next condition
 
-      if (value > sp->alpha) // Go with full depth non-pv search
+      if (doFullDepthSearch) // Go with full depth non-pv search
       {
+          Value localAlpha = sp->alpha;
           ss[sp->ply].reduction = Depth(0);
-          value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);
+          value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
 
-          if (value > sp->alpha && value < sp->beta)
+          if (value > localAlpha && value < sp->beta)
           {
               // When the search fails high at ply 1 while searching the first
-              // move at the root, set the flag failHighPly1.  This is used for
+              // move at the root, set the flag failHighPly1. This is used for
               // time managment: We don't want to stop the search early in
               // such cases, because resolving the fail high at ply 1 could
               // result in a big drop in score at the root.
               if (sp->ply == 1 && RootMoveNumber == 1)
                   Threads[threadID].failHighPly1 = true;
 
-              value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
+              // If another thread has failed high then sp->alpha has been increased
+              // to be higher or equal then beta, if so, avoid to start a PV search.
+              localAlpha = sp->alpha;
+              if (localAlpha < sp->beta)
+                  value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
+              else
+                  assert(thread_should_stop(threadID));
+
               Threads[threadID].failHighPly1 = false;
         }
       }
@@ -2008,41 +2188,49 @@ namespace {
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
       if (thread_should_stop(threadID))
+      {
+          lock_grab(&(sp->lock));
           break;
+      }
 
       // New best move?
-      lock_grab(&(sp->lock));
-      if (value > sp->bestValue && !thread_should_stop(threadID))
+      if (value > sp->bestValue) // Less then 2% of cases
       {
-          sp->bestValue = value;
-          if (value > sp->alpha)
+          lock_grab(&(sp->lock));
+          if (value > sp->bestValue && !thread_should_stop(threadID))
           {
-              sp->alpha = value;
-              sp_update_pv(sp->parentSstack, ss, sp->ply);
-              if (value == value_mate_in(sp->ply + 1))
-                  ss[sp->ply].mateKiller = move;
-
-              if (value >= sp->beta)
+              sp->bestValue = value;
+              if (value > sp->alpha)
               {
-                  for (int i = 0; i < ActiveThreads; i++)
-                      if (i != threadID && (i == sp->master || sp->slaves[i]))
-                          Threads[i].stop = true;
+                  // Ask threads to stop before to modify sp->alpha
+                  if (value >= sp->beta)
+                  {
+                      for (int i = 0; i < ActiveThreads; i++)
+                          if (i != threadID && (i == sp->master || sp->slaves[i]))
+                              Threads[i].stop = true;
 
-                  sp->finished = true;
+                      sp->finished = true;
+                  }
+
+                  sp->alpha = value;
+
+                  sp_update_pv(sp->parentSstack, ss, sp->ply);
+                  if (value == value_mate_in(sp->ply + 1))
+                      ss[sp->ply].mateKiller = move;
               }
-        }
-        // If we are at ply 1, and we are searching the first root move at
-        // ply 0, set the 'Problem' variable if the score has dropped a lot
-        // (from the computer's point of view) since the previous iteration.
-        if (   sp->ply == 1
-            && Iteration >= 2
-            && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
-            Problem = true;
+              // If we are at ply 1, and we are searching the first root move at
+              // ply 0, set the 'Problem' variable if the score has dropped a lot
+              // (from the computer's point of view) since the previous iteration.
+              if (   sp->ply == 1
+                     && Iteration >= 2
+                     && -value <= IterationInfo[Iteration-1].value - ProblemMargin)
+                  Problem = true;
+          }
+          lock_release(&(sp->lock));
       }
-      lock_release(&(sp->lock));
     }
 
-    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.
@@ -2090,7 +2278,9 @@ namespace {
 
   RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
 
+    SearchStack ss[PLY_MAX_PLUS_2];
     MoveStack mlist[MaxRootMoves];
+    StateInfo st;
     bool includeAllMoves = (searchMoves[0] == MOVE_NONE);
 
     // Generate all legal moves
@@ -2108,16 +2298,13 @@ namespace {
             continue;
 
         // Find a quick score for the move
-        StateInfo st;
-        SearchStack ss[PLY_MAX_PLUS_2];
         init_ss_array(ss);
-
+        pos.do_move(cur->move, st);
         moves[count].move = cur->move;
-        pos.do_move(moves[count].move, st);
         moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0);
-        pos.undo_move(moves[count].move);
-        moves[count].pv[0] = moves[count].move;
+        moves[count].pv[0] = cur->move;
         moves[count].pv[1] = MOVE_NONE;
+        pos.undo_move(cur->move);
         count++;
     }
     sort();
@@ -2126,13 +2313,13 @@ namespace {
 
   // RootMoveList simple methods definitions
 
-  inline void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
+  void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
 
     moves[moveNum].nodes = nodes;
     moves[moveNum].cumulativeNodes += nodes;
   }
 
-  inline void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
+  void RootMoveList::set_beta_counters(int moveNum, int64_t our, int64_t their) {
 
     moves[moveNum].ourBeta = our;
     moves[moveNum].theirBeta = their;
@@ -2152,7 +2339,7 @@ namespace {
   // RootMoveList::sort() sorts the root move list at the beginning of a new
   // iteration.
 
-  inline void RootMoveList::sort() {
+  void RootMoveList::sort() {
 
     sort_multipv(count - 1); // Sort all items
   }
@@ -2421,9 +2608,8 @@ namespace {
 
     Square mfrom, mto, tfrom, tto;
 
-    // Prune if there isn't any threat move and
-    // is not a castling move (common case).
-    if (threat == MOVE_NONE && !move_is_castle(m))
+    // Prune if there isn't any threat move
+    if (threat == MOVE_NONE)
         return true;
 
     mfrom = move_from(m);
@@ -2431,15 +2617,11 @@ namespace {
     tfrom = move_from(threat);
     tto = move_to(threat);
 
-    // Case 1: Castling moves are never pruned
-    if (move_is_castle(m))
-        return false;
-
-    // Case 2: Don't prune moves which move the threatened piece
+    // Case 1: Don't prune moves which move the threatened piece
     if (mfrom == tto)
         return false;
 
-    // Case 3: If the threatened piece has value less than or equal to the
+    // Case 2: If the threatened piece has value less than or equal to the
     // value of the threatening piece, don't prune move which defend it.
     if (   pos.move_is_capture(threat)
         && (   pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
@@ -2447,7 +2629,7 @@ namespace {
         && pos.move_attacks_square(m, tto))
         return false;
 
-    // Case 4: If the moving piece in the threatened move is a slider, don't
+    // Case 3: If the moving piece in the threatened move is a slider, don't
     // prune safe moves which block its ray.
     if (   piece_is_slider(pos.piece_on(tfrom))
         && bit_is_set(squares_between(tfrom, tto), mto)
@@ -2474,6 +2656,52 @@ 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;
+  }
+
+
+  // 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.
 
@@ -2511,6 +2739,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.
@@ -2624,7 +2867,7 @@ namespace {
                      || stillAtFirstMove //FIXME: We are not checking any problem flags, BUG?
                      || noProblemFound;
 
-    if (   (Iteration >= 3 && !InfiniteSearch && noMoreTime)
+    if (   (Iteration >= 3 && UseTimeManagement && noMoreTime)
         || (ExactMaxTime && t >= ExactMaxTime)
         || (Iteration >= 3 && MaxNodes && nodes_searched() >= MaxNodes))
         AbortSearch = true;
@@ -2654,7 +2897,7 @@ namespace {
                      || stillAtFirstMove
                      || noProblemFound;
 
-    if (Iteration >= 3 && !InfiniteSearch && (noMoreTime || StopOnPonderhit))
+    if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
         AbortSearch = true;
   }
 
@@ -2756,6 +2999,8 @@ namespace {
       // If this thread has been assigned work, launch a search
       if (Threads[threadID].workIsWaiting)
       {
+          assert(!Threads[threadID].idle);
+
           Threads[threadID].workIsWaiting = false;
           if (Threads[threadID].splitPoint->pvNode)
               sp_search_pv(Threads[threadID].splitPoint, threadID);
@@ -2842,7 +3087,10 @@ namespace {
     if (!Threads[slave].idle || slave == master)
         return false;
 
-    if (Threads[slave].activeSplitPoints == 0)
+    // Make a local copy to be sure doesn't change under our feet
+    int localActiveSplitPoints = Threads[slave].activeSplitPoints;
+
+    if (localActiveSplitPoints == 0)
         // No active split points means that the thread is available as
         // a slave for any other thread.
         return true;
@@ -2850,8 +3098,10 @@ namespace {
     if (ActiveThreads == 2)
         return true;
 
-    // Apply the "helpful master" concept if possible
-    if (SplitPointStack[slave][Threads[slave].activeSplitPoints - 1].slaves[master])
+    // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
+    // that is known to be > 0, instead of Threads[slave].activeSplitPoints that
+    // could have been set to 0 by another thread leading to an out of bound access.
+    if (SplitPointStack[slave][localActiveSplitPoints - 1].slaves[master])
         return true;
 
     return false;
@@ -2901,7 +3151,6 @@ namespace {
     assert(ActiveThreads > 1);
 
     SplitPoint* splitPoint;
-    int i;
 
     lock_grab(&MPLock);
 
@@ -2918,7 +3167,7 @@ namespace {
     splitPoint = SplitPointStack[master] + Threads[master].activeSplitPoints;
     Threads[master].activeSplitPoints++;
 
-    // Initialize the split point object and copy current position
+    // Initialize the split point object
     splitPoint->parent = Threads[master].splitPoint;
     splitPoint->finished = false;
     splitPoint->ply = ply;
@@ -2932,37 +3181,40 @@ namespace {
     splitPoint->mp = mp;
     splitPoint->moves = *moves;
     splitPoint->cpus = 1;
-    splitPoint->pos.copy(p);
+    splitPoint->pos = &p;
     splitPoint->parentSstack = sstck;
-    for (i = 0; i < ActiveThreads; i++)
+    for (int i = 0; i < ActiveThreads; i++)
         splitPoint->slaves[i] = 0;
 
-    // Copy the current search stack to the master thread
-    memcpy(splitPoint->sstack[master], sstck, (ply+1) * sizeof(SearchStack));
+    Threads[master].idle = false;
+    Threads[master].stop = false;
     Threads[master].splitPoint = splitPoint;
 
-    // Make copies of the current position and search stack for each thread
-    for (i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
+    // Allocate available threads setting idle flag to false
+    for (int i = 0; i < ActiveThreads && splitPoint->cpus < MaxThreadsPerSplitPoint; i++)
         if (thread_is_available(i, master))
         {
-            memcpy(splitPoint->sstack[i], sstck, (ply+1) * sizeof(SearchStack));
+            Threads[i].idle = false;
+            Threads[i].stop = false;
             Threads[i].splitPoint = splitPoint;
             splitPoint->slaves[i] = 1;
             splitPoint->cpus++;
         }
 
+    assert(splitPoint->cpus > 1);
+
+    // We can release the lock because master and slave threads are already booked
+    lock_release(&MPLock);
+
     // Tell the threads that they have work to do. This will make them leave
-    // their idle loop.
-    for (i = 0; i < ActiveThreads; i++)
+    // their idle loop. But before copy search stack tail for each thread.
+    for (int i = 0; i < ActiveThreads; i++)
         if (i == master || splitPoint->slaves[i])
         {
-            Threads[i].workIsWaiting = true;
-            Threads[i].idle = false;
-            Threads[i].stop = false;
+            memcpy(splitPoint->sstack[i] + ply - 1, sstck + ply - 1, 3 * sizeof(SearchStack));
+            Threads[i].workIsWaiting = true; // This makes the slave to exit from idle_loop()
         }
 
-    lock_release(&MPLock);
-
     // Everything is set up. The master thread enters the idle loop, from
     // which it will instantly launch a search, because its workIsWaiting
     // slot is 'true'.  We send the split point as a second parameter to the