diff options
| -rwxr-xr-x | src/chess.h | 13 | ||||
| -rwxr-xr-x | src/main.c | 1 | ||||
| -rwxr-xr-x | src/root.c | 11 | ||||
| -rwxr-xr-x | src/search.c | 66 | ||||
| -rw-r--r-- | src/searchsup.c | 62 | ||||
| -rwxr-xr-x | src/split.c | 11 |
6 files changed, 153 insertions, 11 deletions
diff --git a/src/chess.h b/src/chess.h index 245a3b0..abf802e 100755 --- a/src/chess.h +++ b/src/chess.h @@ -819,6 +819,10 @@ typedef struct _COUNTERS UINT64 u64LazyEvals; UINT64 u64FullEvals; UINT64 u64CyclesInEval; + UINT64 u64HistoryPrunes; + UINT64 u64HistoryPruneReSearches; + UINT64 u64FutilityCandidates; + UINT64 u64FutilityPrunes; } tree; @@ -928,6 +932,7 @@ typedef struct _PLY_INFO #endif SCORE iEval; INT iExtensionAmount; + FLAG fIsPVNode; // (iBeta != iAlpha+1) at this ply FLAG fInCheck; FLAG fInQsearch; MOVE mv; @@ -2315,6 +2320,14 @@ ComputeMoveScore(IN SEARCHER_THREAD_CONTEXT *ctx, FLAG ThreadUnderTerminatingSplit(SEARCHER_THREAD_CONTEXT *); +void +InitializeLMRTable(void); + +INT +ExtraReduction(IN ULONG uRemainingDepth, + IN ULONG uMoveNum, + IN ULONG uFailHighPct); + FLAG WeShouldDoHistoryPruning(IN SCORE iRoughEval, IN SCORE iAlpha, @@ -465,6 +465,7 @@ Return value: InitializeDistanceTable(); InitializeOpeningBook(); InitializeDynamicMoveOrdering(); + InitializeLMRTable(); InitializeHashSystem(); InitializePositionHashSystem(); #ifdef MP @@ -456,6 +456,17 @@ Return value: ASSERT(d); Trace("Null move cutoff rate: %5.3f percent.\n", ((n / d) * 100.0)); + n = (double)(ctx->sCounters.tree.u64HistoryPruneReSearches); + d = (double)(ctx->sCounters.tree.u64HistoryPrunes) + 1; + Trace("History/LMR pruning: %"COMPILER_LONGLONG_UNSIGNED_FORMAT + " reduced, %5.3f percent needed a full-depth re-search.\n", + ctx->sCounters.tree.u64HistoryPrunes, ((n / d) * 100.0)); + n = (double)(ctx->sCounters.tree.u64FutilityPrunes); + d = (double)(ctx->sCounters.tree.u64FutilityCandidates) + 1; + Trace("Futility pruning: %"COMPILER_LONGLONG_UNSIGNED_FORMAT + " candidates, %5.3f percent actually pruned " + "(rest saved by fail-high%% / SEE gates).\n", + ctx->sCounters.tree.u64FutilityCandidates, ((n / d) * 100.0)); if (ctx->sCounters.egtb.uProbes > 0) { n = (double)(ctx->sCounters.egtb.uHits); diff --git a/src/search.c b/src/search.c index 29bbc66..ff7e661 100755 --- a/src/search.c +++ b/src/search.c @@ -153,6 +153,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, ULONG uStage = TRY_HASH_MOVE; ULONG u; ULONG uFutilityMargin = 0; + SCORE iMoveSee = 0; #ifdef DEBUG ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); @@ -191,6 +192,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta); iInitialAlpha = iAlpha; + pi->fIsPVNode = (iBeta != iAlpha + 1); ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) || (!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck))); @@ -428,8 +430,19 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // prune away moves we will also make sure there is // no per-move extension. ASSERT(!uFutilityMargin); - if ((iRoughEval + VALUE_ROOK <= iAlpha) && - (uDepth <= TWO_PLY) && + // Narrowed from "<= TWO_PLY" to "< TWO_PLY": ExtraReduction's + // own safety cap guarantees a reduced move's child lands + // with remaining depth >= TWO_PLY, which used to hand every + // heavily-reduced line straight into futility's activation + // floor at exactly that value -- double jeopardy on the + // same move by construction, not by chance. Excluding just + // that exact floor value (not the whole fractional-depth + // window below it) un-stacks that specific overlap. + if (FALSE && // EXPERIMENT: disabled for the unscaled-LMR-table + // test -- isolate the new reduction table's + // effect without also stacking futility pruning + (iRoughEval + VALUE_ROOK <= iAlpha) && + (uDepth < TWO_PLY) && (ctx->uPly >= 2) && (iOrigExtend == 0) && (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0) && @@ -517,6 +530,16 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } #endif + // SEE must be computed on the PRE-move position (it internally + // simulates removing mv.pMoved from mv.cFrom and adding x-rays -- + // see see.c) -- so grab it now, before MakeMove mutates *pos in + // place, for the futility check below to use. Only bother when + // futility mode is actually active at this node. + if (uFutilityMargin) + { + iMoveSee = SEE(pos, mv); + } + if (TRUE == MakeMove(ctx, mv)) { uLegalMoves++; @@ -556,11 +579,22 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, iExtend)) { ASSERT(iExtend == 0); - iExtend = -ONE_PLY; - pi->iExtensionAmount = -ONE_PLY; + iExtend = -(ONE_PLY + ExtraReduction(uDepth, (x - 1), + GetMoveFailHighPercentage(mv))); + pi->iExtensionAmount = iExtend; + INC(ctx->sCounters.tree.u64HistoryPrunes); } - // Maybe even "futility prune" this move away. + // Maybe even "futility prune" this move away. Require two + // independent corroborating signals on top of the static + // margin, not just the move's ordering score alone: this + // specific move must have rarely caused a beta cutoff + // historically (same threshold WeShouldDoHistoryPruning + // uses), and it must not show a tactical gain per SEE -- + // ComputeMoveScore alone is PSQT/history/killer-bonus for + // quiet moves, with no exchange evaluation at all, so it + // was pruning purely on a positional-ordering number. +#ifdef PERF_COUNTERS if ((x != 0) && (uLegalMoves > 1) && (uFutilityMargin) && @@ -568,6 +602,25 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, (iExtend <= 0) && (!IS_ESCAPING_CHECK(mv))) { + INC(ctx->sCounters.tree.u64FutilityCandidates); + } +#endif + if ((x != 0) && + (uLegalMoves > 1) && + (uFutilityMargin) && + (ComputeMoveScore(ctx, mv, (x - 1)) < uFutilityMargin) && + (iExtend <= 0) && + (!IS_ESCAPING_CHECK(mv)) && + // Stricter than WeShouldDoHistoryPruning's <= 10: that one + // gates a reduction with a fail-high re-search safety net + // (search.c's own counters show ~2% wrong-guess rate is + // fine there); this gates an outright, unverified skip -- + // no re-search, no recovery if wrong -- so demand much + // stronger evidence the move is truly hopeless. + (GetMoveFailHighPercentage(mv) <= 3) && + (iMoveSee <= 0)) + { + INC(ctx->sCounters.tree.u64FutilityPrunes); // TODO: test this more carefully ASSERT(!IS_CHECKING_MOVE(mv)); UnmakeMove(ctx, mv); @@ -599,8 +652,9 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // Research deeper if history pruning failed if ((iExtend < 0) && (iScore >= iBeta)) { - uNextDepth += ONE_PLY; + uNextDepth -= iExtend; // undo the full reduction, whatever its magnitude pi->iExtensionAmount = 0; + INC(ctx->sCounters.tree.u64HistoryPruneReSearches); iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); } UnmakeMove(ctx, mv); diff --git a/src/searchsup.c b/src/searchsup.c index 9e842d4..7af1a18 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -18,6 +18,7 @@ Revision History: **/ +#include <math.h> #include "chess.h" extern SCORE g_iRootScore[2]; @@ -224,7 +225,8 @@ Return value: ASSERT((uMoveNum > 0) || (uLegalMoves == 0)); if ((uRemainingDepth >= TWO_PLY) && (iBeta == (iAlpha + 1)) && - (uLegalMoves > 5) && + (FALSE == ctx->sPlyInfo[ctx->uPly - 1].fIsPVNode) && + (uLegalMoves > 3) && (0 == iExtend) && // (iRoughEval + ComputeMoveScore(ctx, mv, uMoveNum - 1) + 200 < iAlpha) && (!IS_ESCAPING_CHECK(mv)) && @@ -244,10 +246,66 @@ Return value: } +#define LMR_TABLE_MAX_DEPTH 32 +#define LMR_TABLE_MAX_MOVES 63 + +static INT g_iLMRTable[LMR_TABLE_MAX_DEPTH + 1][LMR_TABLE_MAX_MOVES + 1]; + +void +InitializeLMRTable(void) +{ + ULONG d, m; + double r; + + g_iLMRTable[0][0] = 0; + for (d = 0; d <= LMR_TABLE_MAX_DEPTH; d++) + { + for (m = 0; m <= LMR_TABLE_MAX_MOVES; m++) + { + if ((d < 1) || (m < 1)) + { + g_iLMRTable[d][m] = 0; + continue; + } + r = 0.7844 + (log((double)d) * log((double)m) / 2.4696); + if (r < 0.0) r = 0.0; + g_iLMRTable[d][m] = (INT)((r * ONE_PLY) + 0.5); + } + } +} + + +INT +ExtraReduction(IN ULONG uRemainingDepth, + IN ULONG uMoveNum, + IN ULONG uFailHighPct) +{ + INT iExtra; + ULONG d = uRemainingDepth / ONE_PLY; + ULONG m = uMoveNum; + + if (d > LMR_TABLE_MAX_DEPTH) d = LMR_TABLE_MAX_DEPTH; + if (m > LMR_TABLE_MAX_MOVES) m = LMR_TABLE_MAX_MOVES; + iExtra = g_iLMRTable[d][m]; + + if (uFailHighPct == 0) + { + iExtra += QUARTER_PLY; + } + + if ((INT)uRemainingDepth - ONE_PLY - iExtra < TWO_PLY) + { + iExtra = MAX((INT)uRemainingDepth - ONE_PLY - TWO_PLY, 0); + } + ASSERT(iExtra >= 0); + return(iExtra); +} + + SCORE ComputeMoveScore(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, - IN ULONG uMoveNum) + IN ULONG uMoveNum) { SCORE iMoveScore = (PIECE_VALUE(mv.pCaptured) + PIECE_VALUE(mv.pPromoted)); diff --git a/src/split.c b/src/split.c index ce9a752..b30cdb6 100755 --- a/src/split.c +++ b/src/split.c @@ -1125,8 +1125,12 @@ Return value: iExtend)) { ASSERT(iExtend == 0); - iExtend = -ONE_PLY; - ctx->sPlyInfo[ctx->uPly].iExtensionAmount = -ONE_PLY; + iExtend = -(ONE_PLY + ExtraReduction(uDepth, + (g_SplitInfo[u].uAlreadyDone + + uMoveNum + 1), + GetMoveFailHighPercentage(mv))); + ctx->sPlyInfo[ctx->uPly].iExtensionAmount = iExtend; + INC(ctx->sCounters.tree.u64HistoryPrunes); } // @@ -1147,8 +1151,9 @@ Return value: // if ((iExtend < 0) && (iScore >= iBeta)) { - uDepth += ONE_PLY; + uDepth -= iExtend; // undo the full reduction, whatever its magnitude ctx->sPlyInfo[ctx->uPly].iExtensionAmount = 0; + INC(ctx->sCounters.tree.u64HistoryPruneReSearches); iScore = -Search(ctx, -iBeta, -iAlpha, uDepth); } UnmakeMove(ctx, mv); |