Use prob cut search to prune bad captures
authorJoona Kiiski <joona.kiiski@gmail.com>
Sat, 2 Apr 2011 07:15:05 +0000 (08:15 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sat, 2 Apr 2011 07:39:54 +0000 (08:39 +0100)
The idea is to try a shallow search with reduced beta
on bad captures so to quickly prune them out in case
are really bad.

After 5529 games 966 - 868 - 3695  ELO +6 (+- 5.4) LOS 91%

Tested also version without upper limitation to 8 plies:

After 8780 games 1537 - 1398 - 5850  ELO +5 (+- 4.3) LOS 93%

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
src/search.cpp

index 6c49c0694343d3bd395b27b96b96aeb42d71d4c1..aec723ef767c0dda26db1db63b8f53d1ac37ba07 100644 (file)
@@ -825,7 +825,7 @@ namespace {
     ValueType vt;
     Value bestValue, value, oldAlpha;
     Value refinedValue, nullValue, futilityBase, futilityValueScaled; // Non-PV specific
-    bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous;
+    bool isPvMove, isCheck, singularExtensionNode, moveIsCheck, captureOrPromotion, dangerous, isBadCap;
     bool mateThreat = false;
     int moveCount = 0, playedMoveCount = 0;
     int threadID = pos.thread();
@@ -1172,6 +1172,16 @@ split_point_start: // At split points actual search starts from here
           }
       }
 
+      // Bad capture detection. Will be used by prob-cut search
+      isBadCap =   depth >= 3 * ONE_PLY
+                && depth < 8 * ONE_PLY
+                && captureOrPromotion
+                && move != ttMove
+                && !dangerous
+                && !move_is_promotion(move)
+                &&  abs(alpha) < VALUE_MATE_IN_PLY_MAX
+                &&  pos.see_sign(move) < 0;
+
       // Step 13. Make the move
       pos.do_move(move, st, ci, moveIsCheck);
 
@@ -1193,6 +1203,7 @@ split_point_start: // At split points actual search starts from here
           // Step 14. Reduced depth search
           // If the move fails high will be re-searched at full depth.
           bool doFullDepthSearch = true;
+          alpha = SpNode ? sp->alpha : alpha;
 
           if (    depth >= 3 * ONE_PLY
               && !captureOrPromotion
@@ -1213,6 +1224,18 @@ split_point_start: // At split points actual search starts from here
               ss->reduction = DEPTH_ZERO; // Restore original reduction
           }
 
+          // Probcut search for bad captures. If a reduced search returns a value
+          // very below beta then we can (almost) safely prune the bad capture.
+          if (isBadCap)
+          {
+              ss->reduction = 3 * ONE_PLY;
+              Value redAlpha = alpha - 300;
+              Depth d = newDepth - ss->reduction;
+              value = -search<NonPV>(pos, ss+1, -(redAlpha+1), -redAlpha, d, ply+1);
+              doFullDepthSearch = (value > redAlpha);
+              ss->reduction = DEPTH_ZERO; // Restore original reduction
+          }
+
           // Step 15. Full depth search
           if (doFullDepthSearch)
           {