Maximize usage of transposition table in probcut

Probcut is a heuristic that wasn't changed a lot in past years,
all attempts to change it using information / writing info to transposition table failed.

This patch has a number of differences that can be summarized as follows:

* For TT write/read we use depth - 3. Because probcut search is depth - 4 but we actually do the move prior to it so effectively we do depth - 3 search;
* In any case of depth of eval from transposition table being >= depth - 3 we either produce cutoff or refuse to even do probcut search, this is allowing us to write info of probcut to transposition table because we know that we wouldn't be overwriting some deeper data with our depth - 3 search - this is an important aspect of this patch;
* For some not really known reason this patch completely ignores tte->bound() - which was the case for previous patch that made probcut interact with TT, maybe 2) is the reason, although it's unproven.

A first version of this patch passed STC and LTC

passed STC
https://tests.stockfishchess.org/tests/view/5f05908a59f6f03532894613
LLR: 2.95 (-2.94,2.94) {-0.50,1.50}
Total: 95776 W: 18300 L: 17973 D: 59503
Ptnml(0-2): 1646, 10944, 22377, 11279, 1642

passed LTC
https://tests.stockfishchess.org/tests/view/5f06b54059f6f035328946bb
LLR: 2.94 (-2.94,2.94) {0.25,1.75}
Total: 57128 W: 7266 L: 6938 D: 42924
Ptnml(0-2): 372, 5163, 17217, 5389, 423

However, an additional bugfix was needed to avoid checking a condition on ttMove if was not available. This passed non-regression bounds on top of the first version:

at STC
https://tests.stockfishchess.org/tests/view/5f080e5059f6f03532894766
LLR: 2.94 (-2.94,2.94) {-1.50,0.50}
Total: 14096 W: 2800 L: 2628 D: 8668
Ptnml(0-2): 225, 1620, 3238, 1688, 277

at LTC
https://tests.stockfishchess.org/tests/view/5f0836a559f6f0353289479c
LLR: 2.95 (-2.94,2.94) {-1.50,0.50}
Total: 25352 W: 3228 L: 3139 D: 18985
Ptnml(0-2): 175, 2350, 7549, 2415, 187

closes https://github.com/official-stockfish/Stockfish/pull/2804

Bench 4540940

diff --git a/src/search.cpp b/src/search.cpp
index 720a910093216be07e52c00cec03789c918c6891..6cf2f90d409f96dbe4f6a88ce625d71341153493 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -596,7 +596,7 @@ namespace {
     Key posKey;
     Move ttMove, move, excludedMove, bestMove;
     Depth extension, newDepth;
     Key posKey;
     Move ttMove, move, excludedMove, bestMove;
     Depth extension, newDepth;

-    Value bestValue, value, ttValue, eval, maxValue;
+    Value bestValue, value, ttValue, eval, maxValue, probcutBeta;

     bool ttHit, ttPv, formerPv, givesCheck, improving, didLMR, priorCapture;
     bool captureOrPromotion, doFullDepthSearch, moveCountPruning,
          ttCapture, singularQuietLMR;
     bool ttHit, ttPv, formerPv, givesCheck, improving, didLMR, priorCapture;
     bool captureOrPromotion, doFullDepthSearch, moveCountPruning,
          ttCapture, singularQuietLMR;


@@ -871,23 +871,33 @@ namespace {
         }
     }
 
         }
     }
 

+    probcutBeta = beta + 176 - 49 * improving;
+

     // Step 10. ProbCut (~10 Elo)
     // If we have a good enough capture and a reduced search returns a value
     // much above beta, we can (almost) safely prune the previous move.
     if (   !PvNode
         &&  depth > 4
     // Step 10. ProbCut (~10 Elo)
     // If we have a good enough capture and a reduced search returns a value
     // much above beta, we can (almost) safely prune the previous move.
     if (   !PvNode
         &&  depth > 4

-        &&  abs(beta) < VALUE_TB_WIN_IN_MAX_PLY)
+        &&  abs(beta) < VALUE_TB_WIN_IN_MAX_PLY
+        && !(   ttHit
+             && tte->depth() >= depth - 3
+             && ttValue != VALUE_NONE
+             && ttValue < probcutBeta))

     {
     {

-        Value raisedBeta = beta + 176 - 49 * improving;
-        assert(raisedBeta < VALUE_INFINITE);
-        MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &captureHistory);
+        if (   ttHit
+            && tte->depth() >= depth - 3
+            && ttValue != VALUE_NONE
+            && ttValue >= probcutBeta
+            && ttMove
+            && pos.capture_or_promotion(ttMove))
+            return probcutBeta;
+
+        assert(probcutBeta < VALUE_INFINITE);
+        MovePicker mp(pos, ttMove, probcutBeta - ss->staticEval, &captureHistory);

         int probCutCount = 0;
 
         while (   (move = mp.next_move()) != MOVE_NONE
         int probCutCount = 0;
 
         while (   (move = mp.next_move()) != MOVE_NONE

-               && probCutCount < 2 + 2 * cutNode
-               && !(   move == ttMove
-                    && tte->depth() >= depth - 4
-                    && ttValue < raisedBeta))
+               && probCutCount < 2 + 2 * cutNode)

             if (move != excludedMove && pos.legal(move))
             {
                 assert(pos.capture_or_promotion(move));
             if (move != excludedMove && pos.legal(move))
             {
                 assert(pos.capture_or_promotion(move));


@@ -905,16 +915,21 @@ namespace {
                 pos.do_move(move, st);
 
                 // Perform a preliminary qsearch to verify that the move holds
                 pos.do_move(move, st);
 
                 // Perform a preliminary qsearch to verify that the move holds

-                value = -qsearch<NonPV>(pos, ss+1, -raisedBeta, -raisedBeta+1);
+                value = -qsearch<NonPV>(pos, ss+1, -probcutBeta, -probcutBeta+1);

 
                 // If the qsearch held, perform the regular search
 
                 // If the qsearch held, perform the regular search

-                if (value >= raisedBeta)
-                    value = -search<NonPV>(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4, !cutNode);
+                if (value >= probcutBeta)
+                    value = -search<NonPV>(pos, ss+1, -probcutBeta, -probcutBeta+1, depth - 4, !cutNode);

 
                 pos.undo_move(move);
 
 
                 pos.undo_move(move);
 

-                if (value >= raisedBeta)
+                if (value >= probcutBeta)
+                {
+                    tte->save(posKey, value_to_tt(value, ss->ply), ttPv,
+                        BOUND_LOWER,
+                        depth - 3, move, ss->staticEval);

                     return value;
                     return value;

+                }

             }
     }
 
             }
     }