Do more futility pruning in qsearch

This patch introduces a third futility pruning heuristic in qsearch. The idea is
that the static exchange evaluation is much worse than the difference between
futility base and alpha. Thus we can assume that the probability of the move
being good enough to beat alpha is low so it can be pruned.

Passed STC:
https://tests.stockfishchess.org/tests/view/64fc982a5dab775b5359dc83
LLR: 2.94 (-2.94,2.94) <0.00,2.00>
Total: 36576 W: 9484 L: 9170 D: 17922
Ptnml(0-2): 121, 4119, 9495, 4431, 122

Passed LTC:
https://tests.stockfishchess.org/tests/view/64fcc7935dab775b5359e1a9
LLR: 2.94 (-2.94,2.94) <0.50,2.50>
Total: 135408 W: 34556 L: 34041 D: 66811
Ptnml(0-2): 56, 14462, 38165, 14953, 68

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

Bench: 1330793

diff --git a/src/search.cpp b/src/search.cpp
index a745d3bfdd0ed16933a9d53dcd8f7ab830637940..beb1cb54822856df2c7522a0a3f0f0f07e0d88b2 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1549,17 +1549,29 @@ moves_loop: // When in check, search starts here
 
                 futilityValue = futilityBase + PieceValue[pos.piece_on(to_sq(move))];
 
+                // If static eval + value of piece we are going to capture is much lower
+                // than alpha we can prune this move
                 if (futilityValue <= alpha)
                 {
                     bestValue = std::max(bestValue, futilityValue);
                     continue;
                 }
 
+                // If static eval is much lower than alpha and move is not winning material
+                // we can prune this move
                 if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1))
                 {
                     bestValue = std::max(bestValue, futilityBase);
                     continue;
                 }
+
+                // If static exchange evaluation is much worse than what is needed to not
+                // fall below alpha we can prune this move
+                if (futilityBase > alpha && !pos.see_ge(move, (alpha - futilityBase) * 4))
+                {
+                    bestValue = alpha;
+                    continue;
+                }
             }
 
             // We prune after the second quiet check evasion move, where being 'in check' is