From 2e8998eac94c7955633e69c04430899f4bdb7907 Mon Sep 17 00:00:00 2001 From: Joona Kiiski Date: Sat, 2 Apr 2011 08:15:05 +0100 Subject: [PATCH 1/1] Use prob cut search to prune bad captures 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 --- src/search.cpp | 25 ++++++++++++++++++++++++- 1 file changed, 24 insertions(+), 1 deletion(-) diff --git a/src/search.cpp b/src/search.cpp index 6c49c069..aec723ef 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -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(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) { -- 2.39.2