X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=f259ab707fe7983a271bdd6b05093490d6fe404a;hp=03993be432a43ce24d496bc0b7bac92fd8d016a6;hb=6247f27a0548562c122f658082d31f535208d603;hpb=0e15b0f1d3837d9203b562fe698d223143882501

diff --git a/src/search.cpp b/src/search.cpp
index 03993be4..f259ab70 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -23,6 +23,7 @@
 ////
 
 #include <cassert>
+#include <cmath>
 #include <cstring>
 #include <fstream>
 #include <iostream>
@@ -31,6 +32,7 @@
 #include "book.h"
 #include "evaluate.h"
 #include "history.h"
+#include "maxgain.h"
 #include "misc.h"
 #include "movegen.h"
 #include "movepick.h"
@@ -94,8 +96,16 @@ namespace {
 
   struct RootMove {
 
-    RootMove();
-    bool operator<(const RootMove&) const; // Used to sort
+    RootMove() { nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL; }
+
+    // RootMove::operator<() is the comparison function used when
+    // 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 operator<(const RootMove& m) const {
+
+        return score != m.score ? score < m.score : theirBeta <= m.theirBeta;
+    }
 
     Move move;
     Value score;
@@ -111,16 +121,18 @@ namespace {
 
   public:
     RootMoveList(Position& pos, Move searchMoves[]);
-    inline Move get_move(int moveNum) const;
-    inline Value get_move_score(int moveNum) const;
-    inline void set_move_score(int moveNum, Value score);
-    inline void set_move_nodes(int moveNum, int64_t nodes);
-    inline void set_beta_counters(int moveNum, int64_t our, int64_t their);
+
+    int move_count() const { return count; }
+    Move get_move(int moveNum) const { return moves[moveNum].move; }
+    Value get_move_score(int moveNum) const { return moves[moveNum].score; }
+    void set_move_score(int moveNum, Value score) { moves[moveNum].score = score; }
+    Move get_move_pv(int moveNum, int i) const { return moves[moveNum].pv[i]; }
+    int64_t get_move_cumulative_nodes(int moveNum) const { return moves[moveNum].cumulativeNodes; }
+
+    void set_move_nodes(int moveNum, int64_t nodes);
+    void set_beta_counters(int moveNum, int64_t our, int64_t their);
     void set_move_pv(int moveNum, const Move pv[]);
-    inline Move get_move_pv(int moveNum, int i) const;
-    inline int64_t get_move_cumulative_nodes(int moveNum) const;
-    inline int move_count() const;
-    inline void sort();
+    void sort();
     void sort_multipv(int n);
 
   private:
@@ -162,15 +174,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);
-
-  // Pruning criterions. See the code and comments in ok_to_prune() to
-  // understand their precise meaning.
-  const bool PruneEscapeMoves    = false;
-  const bool PruneDefendingMoves = false;
-  const bool PruneBlockingMoves  = false;
+  const Value NullMoveMargin = Value(0x200);
 
   // If the TT move is at least SingleReplyMargin better then the
   // remaining ones we will extend it.
@@ -186,18 +192,8 @@ namespace {
   // 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;
 
@@ -227,7 +223,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;
 
@@ -238,6 +234,10 @@ namespace {
   bool UseLogFile;
   std::ofstream LogFile;
 
+  // Natural logarithmic lookup table and its getter function
+  double lnArray[512];
+  inline double ln(int i) { return lnArray[i]; }
+
   // MP related variables
   int ActiveThreads = 1;
   Depth MinimumSplitDepth;
@@ -264,6 +264,8 @@ namespace {
   // History table
   History H;
 
+  // MaxGain table
+  MaxGain MG;
 
   /// Functions
 
@@ -284,7 +286,8 @@ 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);
-  void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount);
+  Value refine_eval(const TTEntry* tte, Value defaultEval, int ply);
+  void update_history(const Position& pos, Move move, Depth depth, Move movesSearched[], int moveCount);
   void update_killers(Move m, SearchStack& ss);
 
   bool fail_high_ply_1();
@@ -361,8 +364,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())
@@ -376,15 +391,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;
@@ -420,8 +426,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");
@@ -441,6 +445,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
@@ -452,51 +460,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)
@@ -560,11 +562,16 @@ 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] = log(double(i)); // log() returns base-e logarithm
+
   for (i = 0; i < THREAD_MAX; i++)
       Threads[i].activeSplitPoints = 0;
 
@@ -595,12 +602,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);
   }
@@ -644,6 +657,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() {
@@ -688,6 +703,7 @@ 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;
@@ -773,7 +789,7 @@ namespace {
 
         Problem = false;
 
-        if (!InfiniteSearch)
+        if (UseTimeManagement)
         {
             // Time to stop?
             bool stopSearch = false;
@@ -827,9 +843,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
@@ -877,8 +893,16 @@ namespace {
   Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, Value beta) {
 
     Value oldAlpha = alpha;
-    Value value;
+    Value value = -VALUE_INFINITE;
     CheckInfo ci(pos);
+    bool isCheck = pos.is_check();
+
+    // Evaluate the position statically
+    EvalInfo ei;
+    if (!isCheck)
+        ss[0].eval = evaluate(pos, ei, 0);
+    else
+        ss[0].eval = VALUE_NONE;
 
     // Loop through all the moves in the root move list
     for (int i = 0; i <  rml.move_count() && !AbortSearch; i++)
@@ -894,7 +918,7 @@ namespace {
         int64_t nodes;
         Move move;
         StateInfo st;
-        Depth ext, newDepth;
+        Depth depth, ext, newDepth;
 
         RootMoveNumber = i + 1;
         FailHigh = false;
@@ -917,8 +941,9 @@ namespace {
         bool moveIsCheck = pos.move_is_check(move);
         bool captureOrPromotion = pos.move_is_capture_or_promotion(move);
         bool dangerous;
+        depth =  (Iteration - 2) * OnePly + InitialDepth;
         ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
-        newDepth = (Iteration - 2) * OnePly + ext + InitialDepth;
+        newDepth = depth + ext;
 
         // Make the move, and search it
         pos.do_move(move, st, ci, moveIsCheck);
@@ -945,18 +970,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.
-            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
+                double red = 0.5 + ln(RootMoveNumber - MultiPV + 1) * ln(depth / 2) / 6.0;
+                if (red >= 1.0)
+                {
+                    ss[0].reduction = Depth(int(floor(red * int(OnePly))));
+                    value = -search(pos, ss, -alpha, newDepth-ss[0].reduction, 1, true, 0);
+                    doFullDepthSearch = (value > alpha);
+                }
+            }
 
-            if (value > alpha)
+            if (doFullDepthSearch)
             {
                 value = -search(pos, ss, -alpha, newDepth, 1, true, 0);
 
@@ -1083,7 +1113,6 @@ namespace {
     assert(threadID >= 0 && threadID < ActiveThreads);
 
     Move movesSearched[256];
-    EvalInfo ei;
     StateInfo st;
     const TTEntry* tte;
     Move ttMove, move;
@@ -1091,7 +1120,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);
@@ -1104,12 +1133,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);
@@ -1139,9 +1165,25 @@ namespace {
         tte = TT.retrieve(pos.get_key());
     }
 
+    // Evaluate the position statically
+    isCheck = pos.is_check();
+    EvalInfo ei;
+    if (!isCheck)
+    {
+        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);
+
+    }
+
     // 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]);
@@ -1196,20 +1238,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.
+        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);
+          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);
+          }
         }
-        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);
@@ -1312,11 +1358,11 @@ namespace {
     const TTEntry* tte;
     Move ttMove, move;
     Depth ext, newDepth;
-    Value approximateEval, nullValue, value, futilityValue, futilityValueScaled;
+    Value bestValue, staticValue, nullValue, value, futilityValue, futilityValueScaled;
     bool isCheck, useFutilityPruning, 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);
@@ -1329,12 +1375,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;
@@ -1356,26 +1399,57 @@ 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));
+    const int PostFutilityValueMargin = 112 * bitScanReverse32(int(depth) * int(depth) / 2);
+
+    // 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 + PostFutilityValueMargin; //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);
+    }
+
+    // Post futility pruning
+    if (staticValue - PostFutilityValueMargin >= beta)
+        return (staticValue - PostFutilityValueMargin);
+
     // 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);
@@ -1410,13 +1484,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;
@@ -1424,7 +1499,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];
@@ -1435,17 +1510,8 @@ 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;
-
     // Loop through all legal moves until no moves remain or a beta cutoff occurs
     while (   bestValue < beta
            && (move = mp.get_next_move()) != MOVE_NONE
@@ -1456,8 +1522,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
@@ -1490,10 +1556,33 @@ namespace {
       // Update current move
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
+      // Futility pruning for captures
+      Color them = opposite_color(pos.side_to_move());
+
+      if (    useFutilityPruning
+          && !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 (    useFutilityPruning
           && !dangerous
           && !captureOrPromotion
+          && !move_is_castle(move)
           &&  move != ttMove)
       {
           // Move count based pruning
@@ -1503,10 +1592,20 @@ namespace {
               continue;
 
           // Value based pruning
-          if (futilityValue == VALUE_NONE)
-              futilityValue = evaluate(pos, ei, threadID) + FutilityValueMargin;
+          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)));
+
+          int preFutilityValueMargin = 0;
+          if (predictedDepth >= OnePly)
+              preFutilityValueMargin = 112 * bitScanReverse32(int(predictedDepth) * int(predictedDepth) / 2);
+
+          preFutilityValueMargin += MG.retrieve(pos.piece_on(move_from(move)), move_from(move), move_to(move)) + 45;
 
-          futilityValueScaled = futilityValue - moveCount * IncrementalFutilityMargin;
+          futilityValueScaled = ss[ply].eval + preFutilityValueMargin - moveCount * IncrementalFutilityMargin;
 
           if (futilityValueScaled < beta)
           {
@@ -1521,20 +1620,25 @@ 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]))
+          && !move_is_killer(move, ss[ply])
+          /* && move != ttMove*/)
       {
-          ss[ply].reduction = OnePly;
-          value = -search(pos, ss, -(beta-1), newDepth-OnePly, ply+1, true, threadID);
+          double red = 0.5 + ln(moveCount) * ln(depth / 2) / 3.0;
+          if (red >= 1.0)
+          {
+              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);
+          }
       }
-      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);
@@ -1562,14 +1666,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,
@@ -1583,12 +1687,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);
@@ -1613,8 +1718,8 @@ 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);
@@ -1627,41 +1732,44 @@ 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;
+        // 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);
+    }
+
 
     // Initialize "stand pat score", and return it immediately if it is
     // at least beta.
@@ -1679,12 +1787,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;
 
     // Loop through the moves until no moves remain or a beta cutoff
     // occurs.
@@ -1693,11 +1806,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
@@ -1707,12 +1821,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)
           {
@@ -1722,8 +1833,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)
@@ -1748,31 +1866,31 @@ 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 < beta)
     {
-        // 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.
+        // 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);
-        Depth d = (depth == Depth(0) ? Depth(0) : Depth(-1));
+        TT.store(pos.get_key(), value_to_tt(bestValue, ply), type, d, MOVE_NONE);
+    }
+    else
+    {
+        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]);
     }
 
-    // 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;
   }
@@ -1791,17 +1909,16 @@ 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;
     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
            && !thread_should_stop(threadID)
@@ -1835,12 +1952,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)
@@ -1862,19 +1973,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 (   !dangerous
-          &&  moveCount >= LMRNonPVMoves
           && !captureOrPromotion
           && !move_is_castle(move)
           && !move_is_killer(move, ss[sp->ply]))
       {
-          ss[sp->ply].reduction = OnePly;
-          value = -search(pos, ss, -(sp->beta-1), newDepth - OnePly, sp->ply+1, true, threadID);
+          double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 3.0;
+          if (red >= 1.0)
+          {
+              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);
+          }
       }
-      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);
@@ -1936,10 +2051,10 @@ 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;
 
     while (    sp->alpha < sp->beta
@@ -1968,34 +2083,47 @@ 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);
+          double red = 0.5 + ln(moveCount) * ln(sp->depth / 2) / 6.0;
+          if (red >= 1.0)
+          {
+              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);
+          }
       }
-      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;
         }
       }
@@ -2007,35 +2135,40 @@ namespace {
           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));
@@ -2080,30 +2213,9 @@ namespace {
   }
 
 
-  /// The RootMove class
-
-  // Constructor
-
-  RootMove::RootMove() {
-    nodes = cumulativeNodes = ourBeta = theirBeta = 0ULL;
-  }
-
-  // RootMove::operator<() is the comparison function used when
-  // 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 {
-
-    if (score != m.score)
-        return (score < m.score);
-
-    return theirBeta <= m.theirBeta;
-  }
-
   /// The RootMoveList class
 
-  // Constructor
+  // RootMoveList c'tor
 
   RootMoveList::RootMoveList(Position& pos, Move searchMoves[]) : count(0) {
 
@@ -2141,56 +2253,37 @@ namespace {
   }
 
 
-  // Simple accessor methods for the RootMoveList class
-
-  inline Move RootMoveList::get_move(int moveNum) const {
-    return moves[moveNum].move;
-  }
+  // RootMoveList simple methods definitions
 
-  inline Value RootMoveList::get_move_score(int moveNum) const {
-    return moves[moveNum].score;
-  }
+  void RootMoveList::set_move_nodes(int moveNum, int64_t nodes) {
 
-  inline void RootMoveList::set_move_score(int moveNum, Value score) {
-    moves[moveNum].score = score;
-  }
-
-  inline 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;
   }
 
   void RootMoveList::set_move_pv(int moveNum, const Move pv[]) {
-    int j;
-    for (j = 0; pv[j] != MOVE_NONE; j++)
-      moves[moveNum].pv[j] = pv[j];
-    moves[moveNum].pv[j] = MOVE_NONE;
-  }
 
-  inline Move RootMoveList::get_move_pv(int moveNum, int i) const {
-    return moves[moveNum].pv[i];
-  }
+    int j;
 
-  inline int64_t RootMoveList::get_move_cumulative_nodes(int moveNum) const {
-    return moves[moveNum].cumulativeNodes;
-  }
+    for (j = 0; pv[j] != MOVE_NONE; j++)
+        moves[moveNum].pv[j] = pv[j];
 
-  inline int RootMoveList::move_count() const {
-    return count;
+    moves[moveNum].pv[j] = MOVE_NONE;
   }
 
 
   // 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); // all items
+    sort_multipv(count - 1); // Sort all items
   }
 
 
@@ -2200,20 +2293,22 @@ namespace {
 
   void RootMoveList::sort_multipv(int n) {
 
-    for (int i = 1; i <= n; i++)
+    int i,j;
+
+    for (i = 1; i <= n; i++)
     {
-      RootMove rm = moves[i];
-      int j;
-      for (j = i; j > 0 && moves[j-1] < rm; j--)
-          moves[j] = moves[j-1];
-      moves[j] = rm;
+        RootMove rm = moves[i];
+        for (j = i; j > 0 && moves[j - 1] < rm; j--)
+            moves[j] = moves[j - 1];
+
+        moves[j] = rm;
     }
   }
 
 
   // init_node() is called at the beginning of all the search functions
-  // (search(), search_pv(), qsearch(), and so on) and initializes the search
-  // stack object corresponding to the current node.  Once every
+  // (search(), search_pv(), qsearch(), and so on) and initializes the
+  // search stack object corresponding to the current node. Once every
   // NodesBetweenPolls nodes, init_node() also calls poll(), which polls
   // for user input and checks whether it is time to stop the search.
 
@@ -2234,48 +2329,56 @@ namespace {
         }
     }
     ss[ply].init(ply);
-    ss[ply+2].initKillers();
+    ss[ply + 2].initKillers();
 
     if (Threads[threadID].printCurrentLine)
         print_current_line(ss, ply, threadID);
   }
 
 
-  // update_pv() is called whenever a search returns a value > alpha.  It
-  // updates the PV in the SearchStack object corresponding to the current
-  // node.
+  // update_pv() is called whenever a search returns a value > alpha.
+  // It updates the PV in the SearchStack object corresponding to the
+  // current node.
 
   void update_pv(SearchStack ss[], int ply) {
+
     assert(ply >= 0 && ply < PLY_MAX);
 
-    ss[ply].pv[ply] = ss[ply].currentMove;
     int p;
-    for (p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
-      ss[ply].pv[p] = ss[ply+1].pv[p];
+
+    ss[ply].pv[ply] = ss[ply].currentMove;
+
+    for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
+        ss[ply].pv[p] = ss[ply + 1].pv[p];
+
     ss[ply].pv[p] = MOVE_NONE;
   }
 
 
-  // sp_update_pv() is a variant of update_pv for use at split points.  The
+  // sp_update_pv() is a variant of update_pv for use at split points. The
   // difference between the two functions is that sp_update_pv also updates
   // the PV at the parent node.
 
   void sp_update_pv(SearchStack* pss, SearchStack ss[], int ply) {
+
     assert(ply >= 0 && ply < PLY_MAX);
 
-    ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
     int p;
-    for (p = ply + 1; ss[ply+1].pv[p] != MOVE_NONE; p++)
-      ss[ply].pv[p] = pss[ply].pv[p] = ss[ply+1].pv[p];
+
+    ss[ply].pv[ply] = pss[ply].pv[ply] = ss[ply].currentMove;
+
+    for (p = ply + 1; ss[ply + 1].pv[p] != MOVE_NONE; p++)
+        ss[ply].pv[p] = pss[ply].pv[p] = ss[ply + 1].pv[p];
+
     ss[ply].pv[p] = pss[ply].pv[p] = MOVE_NONE;
   }
 
 
   // connected_moves() tests whether two moves are 'connected' in the sense
   // that the first move somehow made the second move possible (for instance
-  // if the moving piece is the same in both moves).  The first move is
-  // assumed to be the move that was made to reach the current position, while
-  // the second move is assumed to be a move from the current position.
+  // if the moving piece is the same in both moves). The first move is assumed
+  // to be the move that was made to reach the current position, while the
+  // second move is assumed to be a move from the current position.
 
   bool connected_moves(const Position& pos, Move m1, Move m2) {
 
@@ -2305,36 +2408,23 @@ namespace {
         && bit_is_set(squares_between(f2, t2), f1))
       return true;
 
-    // Case 4: The destination square for m2 is attacked by the moving piece in m1
+    // Case 4: The destination square for m2 is defended by the moving piece in m1
     p = pos.piece_on(t1);
     if (bit_is_set(pos.attacks_from(p, t1), t2))
         return true;
 
     // Case 5: Discovered check, checking piece is the piece moved in m1
-    if (   piece_is_slider(p)
-        && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
+    if (    piece_is_slider(p)
+        &&  bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2)
         && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2))
     {
-        Bitboard occ = pos.occupied_squares();
-        Color us = pos.side_to_move();
-        Square ksq = pos.king_square(us);
-        clear_bit(&occ, f2);
-        if (type_of_piece(p) == BISHOP)
-        {
-            if (bit_is_set(bishop_attacks_bb(ksq, occ), t1))
-                return true;
-        }
-        else if (type_of_piece(p) == ROOK)
-        {
-            if (bit_is_set(rook_attacks_bb(ksq, occ), t1))
-                return true;
-        }
-        else
-        {
-            assert(type_of_piece(p) == QUEEN);
-            if (bit_is_set(queen_attacks_bb(ksq, occ), t1))
-                return true;
-        }
+        // discovered_check_candidates() works also if the Position's side to
+        // move is the opposite of the checking piece.
+        Color them = opposite_color(pos.side_to_move());
+        Bitboard dcCandidates = pos.discovered_check_candidates(them);
+
+        if (bit_is_set(dcCandidates, f2))
+            return true;
     }
     return false;
   }
@@ -2367,7 +2457,7 @@ namespace {
 
 
   // extension() decides whether a move should be searched with normal depth,
-  // or with extended depth.  Certain classes of moves (checking moves, in
+  // or with extended depth. Certain classes of moves (checking moves, in
   // particular) are searched with bigger depth than ordinary moves and in
   // any case are marked as 'dangerous'. Note that also if a move is not
   // extended, as example because the corresponding UCI option is set to zero,
@@ -2433,11 +2523,11 @@ namespace {
 
 
   // ok_to_do_nullmove() looks at the current position and decides whether
-  // doing a 'null move' should be allowed.  In order to avoid zugzwang
+  // doing a 'null move' should be allowed. In order to avoid zugzwang
   // problems, null moves are not allowed when the side to move has very
-  // little material left.  Currently, the test is a bit too simple:  Null
-  // moves are avoided only when the side to move has only pawns left.  It's
-  // probably a good idea to avoid null moves in at least some more
+  // little material left. Currently, the test is a bit too simple: Null
+  // moves are avoided only when the side to move has only pawns left.
+  // It's probably a good idea to avoid null moves in at least some more
   // complicated endgames, e.g. KQ vs KR.  FIXME
 
   bool ok_to_do_nullmove(const Position& pos) {
@@ -2446,7 +2536,7 @@ namespace {
   }
 
 
-  // ok_to_prune() tests whether it is safe to forward prune a move.  Only
+  // ok_to_prune() tests whether it is safe to forward prune a move. Only
   // non-tactical moves late in the move list close to the leaves are
   // candidates for pruning.
 
@@ -2460,34 +2550,30 @@ namespace {
 
     Square mfrom, mto, tfrom, tto;
 
+    // Prune if there isn't any threat move
+    if (threat == MOVE_NONE)
+        return true;
+
     mfrom = move_from(m);
     mto = move_to(m);
     tfrom = move_from(threat);
     tto = move_to(threat);
 
-    // Case 1: Castling moves are never pruned
-    if (move_is_castle(m))
+    // Case 1: Don't prune moves which move the threatened piece
+    if (mfrom == tto)
         return false;
 
-    // Case 2: Don't prune moves which move the threatened piece
-    if (!PruneEscapeMoves && threat != MOVE_NONE && 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 (   !PruneDefendingMoves
-        && threat != MOVE_NONE
-        && pos.move_is_capture(threat)
+    if (   pos.move_is_capture(threat)
         && (   pos.midgame_value_of_piece_on(tfrom) >= pos.midgame_value_of_piece_on(tto)
             || pos.type_of_piece_on(tfrom) == KING)
         && 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 (  !PruneBlockingMoves
-        && threat != MOVE_NONE
-        && piece_is_slider(pos.piece_on(tfrom))
+    if (   piece_is_slider(pos.piece_on(tfrom))
         && bit_is_set(squares_between(tfrom, tto), mto)
         && pos.see_sign(m) >= 0)
         return false;
@@ -2512,19 +2598,41 @@ namespace {
   }
 
 
+  // refine_eval() returns the transposition table score if
+  // possible otherwise falls back on static position evaluation.
+
+  Value refine_eval(const TTEntry* tte, Value defaultEval, int ply) {
+
+      if (!tte)
+          return defaultEval;
+
+      Value v = value_from_tt(tte->value(), ply);
+
+      if (   (is_lower_bound(tte->type()) && v >= defaultEval)
+          || (is_upper_bound(tte->type()) && v < defaultEval))
+          return v;
+
+      return defaultEval;
+  }
+
   // update_history() registers a good move that produced a beta-cutoff
   // in history and marks as failures all the other moves of that ply.
 
-  void update_history(const Position& pos, Move m, Depth depth,
+  void update_history(const Position& pos, Move move, Depth depth,
                       Move movesSearched[], int moveCount) {
 
-    H.success(pos.piece_on(move_from(m)), move_to(m), depth);
+    Move m;
+
+    H.success(pos.piece_on(move_from(move)), move_to(move), depth);
 
     for (int i = 0; i < moveCount - 1; i++)
     {
-        assert(m != movesSearched[i]);
-        if (!pos.move_is_capture_or_promotion(movesSearched[i]))
-            H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i]), depth);
+        m = movesSearched[i];
+
+        assert(m != move);
+
+        if (!pos.move_is_capture_or_promotion(m))
+            H.failure(pos.piece_on(move_from(m)), move_to(m), depth);
     }
   }
 
@@ -2546,7 +2654,7 @@ namespace {
 
   // 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 managment.
+  // is used for time management.
 
   bool fail_high_ply_1() {
 
@@ -2657,7 +2765,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;
@@ -2687,7 +2795,7 @@ namespace {
                      || stillAtFirstMove
                      || noProblemFound;
 
-    if (Iteration >= 3 && !InfiniteSearch && (noMoreTime || StopOnPonderhit))
+    if (Iteration >= 3 && UseTimeManagement && (noMoreTime || StopOnPonderhit))
         AbortSearch = true;
   }
 
@@ -2770,8 +2878,8 @@ namespace {
         if (AllThreadsShouldExit && threadID != 0)
             break;
 
-        // If we are not thinking, wait for a condition to be signaled instead
-        // of wasting CPU time polling for work.
+        // If we are not thinking, wait for a condition to be signaled
+        // instead of wasting CPU time polling for work.
         while (threadID != 0 && (Idle || threadID >= ActiveThreads))
         {
 
@@ -2789,6 +2897,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);
@@ -2835,7 +2945,7 @@ namespace {
 
   // thread_should_stop() checks whether the thread with a given threadID has
   // been asked to stop, directly or indirectly. This can happen if a beta
-  // cutoff has occured in the thread's currently active split point, or in
+  // cutoff has occurred in the thread's currently active split point, or in
   // some ancestor of the current split point.
 
   bool thread_should_stop(int threadID) {
@@ -2875,7 +2985,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;
@@ -2883,8 +2996,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;
@@ -2934,7 +3049,6 @@ namespace {
     assert(ActiveThreads > 1);
 
     SplitPoint* splitPoint;
-    int i;
 
     lock_grab(&MPLock);
 
@@ -2951,7 +3065,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;
@@ -2965,37 +3079,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