Only move extension based on exclusion search

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index faac36ce966727734c0109bf42fda9ef20dac9c1..d0ddbd55045639a4e0a0ea87b8d46753c015bb83 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -172,12 +172,15 @@ namespace {
   const bool PruneDefendingMoves = false;
   const bool PruneBlockingMoves  = false;
 
+  // Only move margin
+  const Value OnlyMoveMargin = Value(100);
+
   // Margins for futility pruning in the quiescence search, and at frontier
   // and near frontier nodes.
   const Value FutilityMarginQS = Value(0x80);
 
   // Each move futility margin is decreased
-  const Value IncrementalFutilityMargin = Value(0xA);
+  const Value IncrementalFutilityMargin = Value(0x8);
 
   // Remaining depth:                  1 ply         1.5 ply       2 ply         2.5 ply       3 ply         3.5 ply
   const Value FutilityMargins[12] = { Value(0x100), Value(0x120), Value(0x200), Value(0x220), Value(0x250), Value(0x270),
@@ -277,7 +280,7 @@ namespace {
   Value id_loop(const Position& pos, Move searchMoves[]);
   Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value alpha, 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);
+  Value search(Position& pos, SearchStack ss[], Value beta, Depth depth, int ply, bool allowNullmove, int threadID, Move forbiddenMove = MOVE_NONE);
   Value qsearch(Position& pos, SearchStack ss[], Value alpha, Value beta, Depth depth, int ply, int threadID);
   void sp_search(SplitPoint* sp, int threadID);
   void sp_search_pv(SplitPoint* sp, int threadID);
@@ -1136,6 +1139,25 @@ namespace {
 
       // Decide the new search depth
       ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous);
+
+      // Only move extension
+      if (   moveCount == 1
+          && ext < OnePly
+          && depth >= 8 * OnePly
+          && tte
+          && (tte->type() & VALUE_TYPE_LOWER)
+          && tte->move() != MOVE_NONE
+          && tte->depth() >= depth - 3 * OnePly)
+      {
+          Value ttValue = value_from_tt(tte->value(), ply);
+          if (abs(ttValue) < VALUE_KNOWN_WIN)
+          {
+              Value excValue = search(pos, ss, ttValue - OnlyMoveMargin, depth / 2, ply, false, threadID, tte->move());
+              if (excValue < ttValue - OnlyMoveMargin)
+                  ext = OnePly;
+          }
+      }
+
       newDepth = depth - OnePly + ext;
 
       // Make and search the move
@@ -1251,7 +1273,7 @@ namespace {
   // search() is the search function for zero-width nodes.
 
   Value search(Position& pos, SearchStack ss[], Value beta, Depth depth,
-               int ply, bool allowNullmove, int threadID) {
+               int ply, bool allowNullmove, int threadID, Move forbiddenMove) {
 
     assert(beta >= -VALUE_INFINITE && beta <= VALUE_INFINITE);
     assert(ply >= 0 && ply < PLY_MAX);
@@ -1293,8 +1315,14 @@ namespace {
     if (value_mate_in(ply + 1) < beta)
         return beta - 1;
 
+    // Position key calculation
+    Key posKey = pos.get_key();
+
+    if (forbiddenMove != MOVE_NONE)
+      posKey ^= Position::zobExclusion;
+
     // Transposition table lookup
-    tte = TT.retrieve(pos.get_key());
+    tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
     if (tte && ok_to_use_TT(tte, depth, beta, ply))
@@ -1399,6 +1427,9 @@ namespace {
     {
       assert(move_is_ok(move));
 
+      if (move == forbiddenMove)
+          continue;
+
       singleReply = (isCheck && mp.number_of_evasions() == 1);
       moveIsCheck = pos.move_is_check(move, ci);
       captureOrPromotion = pos.move_is_capture_or_promotion(move);
@@ -1407,6 +1438,26 @@ namespace {
 
       // Decide the new search depth
       ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleReply, mateThreat, &dangerous);
+
+      // Only move extension
+      if (   forbiddenMove == MOVE_NONE
+          && moveCount == 1
+          && ext < OnePly
+          && depth >= 8 * OnePly
+          && tte
+          && (tte->type() & VALUE_TYPE_LOWER)
+          && tte->move() != MOVE_NONE
+          && tte->depth() >= depth - 3 * OnePly)
+      {
+          Value ttValue = value_from_tt(tte->value(), ply);
+          if (abs(ttValue) < VALUE_KNOWN_WIN)
+          {
+              Value excValue = search(pos, ss, ttValue - OnlyMoveMargin, depth / 2, ply, false, threadID, tte->move());
+              if (excValue < ttValue - OnlyMoveMargin)
+                  ext = OnePly;
+          }
+      }
+
       newDepth = depth - OnePly + ext;
 
       // Futility pruning
@@ -1473,7 +1524,7 @@ namespace {
           {
               if (futilityValue == VALUE_NONE)
                   futilityValue =  evaluate(pos, ei, threadID)
-                                 + 64*(1+bitScanReverse32(int(depth) * int(depth)));
+                                 + 64*(2+bitScanReverse32(int(depth) * int(depth)));
 
               futilityValueScaled = futilityValue - moveCount * IncrementalFutilityMargin;
 
@@ -1540,7 +1591,7 @@ namespace {
     // All legal moves have been searched.  A special case: If there were
     // no legal moves, it must be mate or stalemate.
     if (moveCount == 0)
-        return (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
+        return (forbiddenMove == MOVE_NONE ? (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW) : beta - 1);
 
     // If the search is not aborted, update the transposition table,
     // history counters, and killer moves.
@@ -1548,7 +1599,7 @@ namespace {
         return bestValue;
 
     if (bestValue < beta)
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
+        TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_UPPER, depth, MOVE_NONE);
     else
     {
         BetaCounter.add(pos.side_to_move(), depth, threadID);
@@ -1558,7 +1609,7 @@ namespace {
             update_history(pos, move, depth, movesSearched, moveCount);
             update_killers(move, ss[ply]);
         }
-        TT.store(pos.get_key(), value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
+        TT.store(posKey, value_to_tt(bestValue, ply), VALUE_TYPE_LOWER, depth, move);
     }
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);