From dbf71219abeb51d386b0f7294f1664f2906d2b82 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Sun, 30 Aug 2026 18:51:38 -0700 Subject: Plumb iImprovement into LMR and futiltiy and parallel search. Fix a bug (iEval) in HelpSearch This commit changes the heuristics for: nullmove pruning, LMR, and EFP slightly. --- src/chess.h | 22 +++++++++------ src/search.c | 24 +++++++++------- src/searchsup.c | 75 +++++++++++++++++++++++++------------------------ src/split.c | 87 +++++++++++++++++++++++++++++---------------------------- 4 files changed, 111 insertions(+), 97 deletions(-) (limited to 'src') diff --git a/src/chess.h b/src/chess.h index 367100f..8a1185a 100755 --- a/src/chess.h +++ b/src/chess.h @@ -935,6 +935,8 @@ typedef struct _SPLIT_INFO INT iPositionExtend; // positional extension SCORE iAlpha; // original alpha at split SCORE iBeta; // beta at split + SCORE iEval; // static eval at split + SCORE iImprovement; // eval improvement since ply-2 (may be negative) CUMULATIVE_SEARCH_FLAGS sSearchFlags; // flags at split time // output from the split node @@ -2399,20 +2401,21 @@ InitLMRTable(void); INT GetLMRReduction(IN SCORE iRoughEval, - IN SCORE iAlpha, - IN SCORE iBeta, - IN SEARCHER_THREAD_CONTEXT *ctx, - IN ULONG uRemainingDepth, - IN ULONG uLegalMoves, - IN MOVE mv, - IN ULONG uMoveNum, - IN INT iExtend); + IN SCORE iAlpha, + IN SCORE iBeta, + IN SCORE iImprovement, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN ULONG uRemainingDepth, + IN ULONG uLegalMoves, + IN MOVE mv, + IN ULONG uMoveNum, + IN INT iExtend); FLAG WeShouldTryNullmovePruning(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta, - IN SCORE iRoughEval, + IN SCORE iEval, IN SCORE iImprovement, IN ULONG uNullDepth); @@ -2914,6 +2917,7 @@ SCORE StartParallelSearch(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piAlpha, IN SCORE iBeta, + IN SCORE iImprovement, IN OUT SCORE *piBestScore, IN OUT MOVE *pmvBest, IN ULONG uMoveNum, diff --git a/src/search.c b/src/search.c index 3879d9f..4a153aa 100755 --- a/src/search.c +++ b/src/search.c @@ -165,7 +165,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, MOVE mvLast = (pi-1)->mv; SCORE iBestScore = -INFINITY; SCORE iInitialAlpha; - SCORE iRoughEval; + SCORE iEval; MOVE mv, mvBest, mvHash; ULONG x = 0; SCORE iScore; @@ -337,19 +337,21 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, } // Maybe do nullmove pruning - pi->iEval = iRoughEval = GetRoughEvalScore(ctx, iAlpha, iBeta, FALSE); + pi->iEval = iEval = GetRoughEvalScore(ctx, iAlpha, iBeta, FALSE); SCORE iImprovement = 0; if (ctx->uPly > 1) { - iImprovement = (iRoughEval - ctx->sPlyInfo[ctx->uPly - 2].iEval); + iImprovement = (iEval - ctx->sPlyInfo[ctx->uPly - 2].iEval); } + + GENERATE_NO_MOVES; if (!fSkipNull && !fThreat && WeShouldTryNullmovePruning(ctx, iAlpha, iBeta, - iRoughEval, + iEval, iImprovement, uNextDepth)) { @@ -525,16 +527,16 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, { ASSERT(uDepth >= THREE_QUARTERS_PLY); if ((uDepth <= ONE_PLY + THREE_QUARTERS_PLY) && - (iRoughEval + VALUE_KNIGHT <= iAlpha)) + (iEval + VALUE_KNIGHT + iImprovement <= iAlpha)) { - uFutilityMargin = (iAlpha - iRoughEval) / 2; + uFutilityMargin = (iAlpha - iEval) / 2; ASSERT(uFutilityMargin); } else if ((uDepth > ONE_PLY + THREE_QUARTERS_PLY) && (uDepth <= TWO_PLY + THREE_QUARTERS_PLY) && - (iRoughEval + VALUE_ROOK <= iAlpha)) + (iEval + VALUE_ROOK + iImprovement <= iAlpha)) { - uFutilityMargin = (iAlpha - iRoughEval) / 2; + uFutilityMargin = (iAlpha - iEval) / 2; ASSERT(uFutilityMargin); } } @@ -649,6 +651,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, iScore = StartParallelSearch(ctx, &iAlpha, iBeta, + iImprovement, &iBestScore, &mvBest, (x - 1), @@ -703,7 +706,7 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, iAlpha, iBeta, (x - 1), // Note: x==0 if doing mvHash - iRoughEval, + iEval, uDepth, iCheckSee, &iExtend); @@ -721,9 +724,10 @@ Search(IN SEARCHER_THREAD_CONTEXT *ctx, // Decide how much (if any) to reduce this move's depth -- // graded LMR. { - INT iLMR = GetLMRReduction(iRoughEval, + INT iLMR = GetLMRReduction(iEval, iAlpha, iBeta, + iImprovement, ctx, uDepth, uLegalMoves, diff --git a/src/searchsup.c b/src/searchsup.c index d2cbbbd..9ad4303 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -188,15 +188,16 @@ ThreadUnderTerminatingSplit(IN SEARCHER_THREAD_CONTEXT *ctx) INT -GetLMRReduction(IN SCORE iRoughEval, - IN SCORE iAlpha, - IN SCORE iBeta, - IN SEARCHER_THREAD_CONTEXT *ctx, - IN ULONG uRemainingDepth, - IN ULONG uLegalMoves, - IN MOVE mv, - IN ULONG uMoveNum, - IN INT iExtend) +GetLMRReduction(IN SCORE iEval, + IN SCORE iAlpha, + IN SCORE iBeta, + IN SCORE iImprovement, + IN SEARCHER_THREAD_CONTEXT *ctx, + IN ULONG uRemainingDepth, + IN ULONG uLegalMoves, + IN MOVE mv, + IN ULONG uMoveNum, + IN INT iExtend) /** Routine description: @@ -206,6 +207,8 @@ Routine description: counter-move exemption. Kept under the GetLMRReduction name so search.c/split.c's call sites need no changes. + Note: the move has already been made by the time we get here. + Return value: INT : 0 if no reduction, else -ONE_PLY. @@ -215,6 +218,7 @@ Return value: ASSERT(ctx->uPly > 0); ASSERT(mv.uMove); ASSERT((uMoveNum > 0) || (uLegalMoves == 0)); + if ((uRemainingDepth >= TWO_PLY) && (FALSE == ctx->sPlyInfo[ctx->uPly - 1].fPvNode) && (uLegalMoves > 5) && @@ -230,6 +234,9 @@ Return value: (GetMoveFailHighPercentage(mv, NULL) <= 10)) { ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); + if (iImprovement <= 40) { + return(-(ONE_PLY + QUARTER_PLY)); + } return(-ONE_PLY); } return(0); @@ -369,15 +376,14 @@ Return value: } -void -ComputeMoveExtension(IN SEARCHER_THREAD_CONTEXT *ctx, - IN SCORE iAlpha, - IN SCORE iBeta, - IN ULONG uMoveNum, - IN SCORE iRoughEval, - IN ULONG uDepth, - IN SCORE iCheckSee, - IN OUT INT *piExtend) +void ComputeMoveExtension(IN SEARCHER_THREAD_CONTEXT *ctx, + IN SCORE iAlpha, + IN SCORE iBeta, + IN ULONG uMoveNum, + IN SCORE iRoughEval, + IN ULONG uDepth, + IN SCORE iCheckSee, + IN OUT INT *piExtend) /** Routine description: @@ -482,13 +488,13 @@ Return value: { ASSERT(IS_ESCAPING_CHECK(mv)); iMoveScore = iRoughEval + ComputeMoveScore(ctx, mv, uMoveNum); - + // One legal move in reply to check... if (ONE_LEGAL_MOVE(ctx, ctx->uPly - 1) && - CountKingSafetyDefects(&ctx->sPosition, uColor) > 1) + CountKingSafetyDefects(&ctx->sPosition, uColor) > 1) { *piExtend += (QUARTER_PLY + - HALF_PLY * + HALF_PLY * (iMoveScore + VALUE_KNIGHT > iAlpha)); INC(ctx->sCounters.extension.uOneLegalMove); } @@ -511,7 +517,7 @@ Return value: { // Endgame extension if ((ctx->sPlyInfo[1].uTotalNonPawns > 2) && - ((pos->uNonPawnCount[BLACK][0] + + ((pos->uNonPawnCount[BLACK][0] + pos->uNonPawnCount[WHITE][0]) == 2)) { if ((mv.pCaptured && !IS_PAWN(mv.pCaptured)) || @@ -529,7 +535,7 @@ Return value: if (uDepth <= THREE_PLY) { if ((mv.pCaptured) && !IS_PAWN(mv.pCaptured) && - ((PIECE_VALUE(mv.pCaptured) == + ((PIECE_VALUE(mv.pCaptured) == PIECE_VALUE(mvLast.pCaptured)) || ((mvLast.pPromoted) && (mv.cTo == mvLast.cTo)))) { @@ -1092,11 +1098,11 @@ SelectNullmoveRFactor(SEARCHER_THREAD_CONTEXT *ctx, FLAG WeShouldTryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx, SCORE iAlpha, SCORE iBeta, - SCORE iRoughEval, - SCORE iImprovement, - ULONG uNullDepth) + SCORE iEval, + SCORE iImprovement, + ULONG uNullDepth) { - static SCORE iSkipNullMargins[] = { + static SCORE iSkipShallowNullIfThisFarBelowAlpha[] = { 700, 950, 1110, 1150, 1190, 1230, 1270, 0 }; POSITION *pos = &ctx->sPosition; @@ -1113,20 +1119,17 @@ FLAG WeShouldTryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx, (pos->uNonPawnCount[pos->uToMove][0] > 2) && (FALSE == pi->fInCheck) && (iBeta != +INFINITY) && - (FALSE == pi->fPvNode)) // <--- TODO: test this one please... + (FALSE == pi->fPvNode)) { if (uNullDepth <= 6 * ONE_PLY) { u = uNullDepth / ONE_PLY; ASSERT(u <= 6); - SCORE iMargin = iSkipNullMargins[u]; - if (iImprovement > 0) - { - iMargin -= iImprovement; - iMargin = MAX(0, iMargin); - } - if ((iRoughEval + iMargin <= iAlpha) || - ((iRoughEval + iMargin / 2 <= iAlpha) && + SCORE iMargin = iSkipShallowNullIfThisFarBelowAlpha[u]; + iMargin -= iImprovement; // Note: if improving, makes null more likely + iMargin = MAX(0, iMargin); // if not, less likely. + if ((iEval + iMargin <= iAlpha) || + ((iEval + iMargin / 2 <= iAlpha) && (ValueOfMaterialInTroubleAfterNull(ctx, pos->uToMove)))) { return FALSE; diff --git a/src/split.c b/src/split.c index 8bc4e60..b3fc659 100755 --- a/src/split.c +++ b/src/split.c @@ -246,7 +246,7 @@ Return value: v++) { ctx->sMoveStack.mvf[v] = g_SplitInfo[u].mvf[v]; - ASSERT(SanityCheckMove(&ctx->sPosition, + ASSERT(SanityCheckMove(&ctx->sPosition, g_SplitInfo[u].mvf[v].mv)); } @@ -459,6 +459,7 @@ SCORE StartParallelSearch(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piAlpha, IN SCORE iBeta, + IN SCORE iImprovement, IN OUT SCORE *piBestScore, IN OUT MOVE *pmvBest, IN ULONG uMoveNum, @@ -565,6 +566,8 @@ Return value: memcpy(&(g_SplitInfo[u].sRootPosition), GetRootPosition(), sizeof(POSITION)); + g_SplitInfo[u].iEval = ctx->sPlyInfo[ctx->uPly].iEval; + g_SplitInfo[u].iImprovement = iImprovement; #if DEBUG g_SplitInfo[u].uSplitPly = ctx->uPly; memcpy(&(g_SplitInfo[u].sSplitPosition), @@ -579,7 +582,7 @@ Return value: // useless. Before we grab any helper threads, see if we // need to bail out of this split. // - if (g_MoveTimer.bvFlags & TIMER_STOPPING) + if (g_MoveTimer.bvFlags & TIMER_STOPPING) { g_uNumSplitsAvailable++; g_SplitInfo[u].uNumThreadsHelping = 0; @@ -690,11 +693,11 @@ Return value: // Update the context of the thread that is initiating the // split with a pointer to the split info node we are using. // - for (uSplitNum = 0; - uSplitNum < NUM_SPLIT_PTRS_IN_CONTEXT; - uSplitNum++) + for (uSplitNum = 0; + uSplitNum < NUM_SPLIT_PTRS_IN_CONTEXT; + uSplitNum++) { - if (ctx->pSplitInfo[uSplitNum] == NULL) + if (ctx->pSplitInfo[uSplitNum] == NULL) { ctx->pSplitInfo[uSplitNum] = &(g_SplitInfo[u]); break; @@ -726,7 +729,7 @@ Return value: if (g_fExitProgram) break; } - // + // // Note: past this point we are the only ones using the // split until we return it to the pool by making its // refcount zero again. @@ -848,7 +851,7 @@ Parameters: MOVE mv : move it just searched SCORE iScore : score of the move's subtree ULONG u : split node number - + Return value: static void @@ -856,13 +859,13 @@ Return value: **/ { ULONG v; - + AcquireSpinLock(&(g_SplitInfo[u].uLock)); // // See if this split is shutting down // - if (TRUE == g_SplitInfo[u].fTerminate) + if (TRUE == g_SplitInfo[u].fTerminate) { ReleaseSpinLock(&(g_SplitInfo[u].uLock)); return; @@ -909,8 +912,8 @@ Return value: } -static void -_SetFinalStats(IN SEARCHER_THREAD_CONTEXT *ctx, +static void +_SetFinalStats(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG u) /** @@ -934,13 +937,13 @@ Return value: // Before we stop searching this node, update some stuff. // AcquireSpinLock(&(g_SplitInfo[u].uLock)); - + // // Counters to persist in the main counter struct via the split. // - g_SplitInfo[u].sCounters.tree.u64TotalNodeCount += + g_SplitInfo[u].sCounters.tree.u64TotalNodeCount += ctx->sCounters.tree.u64TotalNodeCount; - g_SplitInfo[u].sCounters.tree.u64BetaCutoffs += + g_SplitInfo[u].sCounters.tree.u64BetaCutoffs += ctx->sCounters.tree.u64BetaCutoffs; g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove += ctx->sCounters.tree.u64BetaCutoffsOnFirstMove; @@ -954,11 +957,11 @@ Return value: // // TODO: Any other counters we care about? // - + // // IDEA: Save the killers from this context to bring back to main // - + // // Decrement threadcount in this split. Note: the main thread // incremented it by two. @@ -970,18 +973,18 @@ Return value: } -static MOVE -_GetNextParallelMove(OUT SCORE *piAlpha, - OUT SCORE *piBestScore, +static MOVE +_GetNextParallelMove(OUT SCORE *piAlpha, + OUT SCORE *piBestScore, OUT ULONG *puMoveNumber, IN ULONG u) /** - + Routine description: Retrieve the next parallel move to search at the split node. Also update alpha and bestscore. - + Parameters: SCORE *piAlpha : current alpha @@ -995,7 +998,7 @@ Return value: **/ { MOVE mv = {0}; - + AcquireSpinLock(&(g_SplitInfo[u].uLock)); if (g_SplitInfo[u].fTerminate) { @@ -1012,7 +1015,7 @@ Return value: #ifdef DEBUG ASSERT(!(g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags & MVF_MOVE_SEARCHED)); - g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags |= + g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags |= MVF_MOVE_SEARCHED; ASSERT(mv.uMove); ASSERT(SanityCheckMove(&g_SplitInfo[u].sSplitPosition, mv)); @@ -1029,8 +1032,8 @@ Return value: } -void -HelpSearch(IN OUT SEARCHER_THREAD_CONTEXT *ctx, +void +HelpSearch(IN OUT SEARCHER_THREAD_CONTEXT *ctx, IN ULONG u) /** @@ -1063,7 +1066,7 @@ Return value: SCORE iCheckSee; #ifdef DEBUG POSITION board; - + memcpy(&board, &ctx->sPosition, sizeof(POSITION)); ASSERT(PositionsAreEquivalent(&board, &g_SplitInfo[u].sSplitPosition)); #endif @@ -1072,21 +1075,24 @@ Return value: iBeta = g_SplitInfo[u].iBeta; uOrigDepth = g_SplitInfo[u].uDepth; ctx->sSearchFlags = g_SplitInfo[u].sSearchFlags; + SCORE iEval = g_SplitInfo[u].iEval; + SCORE iImprovement = g_SplitInfo[u].iImprovement; + do { iExtend = iOrigExtend; uDepth = uOrigDepth; ASSERT(ctx->uPly == g_SplitInfo[u].uSplitPly); - + mv = _GetNextParallelMove(&iAlpha, - &iBestScore, + &iBestScore, &uMoveNum, u); if (mv.uMove == 0) break; // Split is terminating ASSERT(IS_VALID_SCORE(iBestScore)); ASSERT(uMoveNum < MAX_MOVES_PER_PLY); - ASSERT(IS_SAME_MOVE(mv, + ASSERT(IS_SAME_MOVE(mv, ctx->sMoveStack.mvf[ctx->sMoveStack.uBegin[ctx->uPly]+uMoveNum].mv)); ASSERT(uDepth <= MAX_DEPTH_PER_SEARCH); ASSERT(IS_VALID_SCORE(iAlpha)); @@ -1094,7 +1100,7 @@ Return value: ASSERT(iAlpha < iBeta); ASSERT(iExtend >= -ONE_PLY); ASSERT(iExtend <= +ONE_PLY); - + // SEE on the PRE-move position -- see search.c's identical comment. iCheckSee = 0; if (IS_CHECKING_MOVE(mv)) @@ -1105,25 +1111,21 @@ Return value: uMoveNum); } - if (MakeMove(ctx, mv)) + if (TRUE == MakeMove(ctx, mv)) { - ASSERT((IS_CHECKING_MOVE(mv) && - InCheck(&ctx->sPosition, ctx->sPosition.uToMove)) || - (!IS_CHECKING_MOVE(mv) && - !InCheck(&ctx->sPosition, ctx->sPosition.uToMove))); - iRoughEval = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE); + ASSERT((IS_CHECKING_MOVE(mv) && InCheck(&ctx->sPosition, ctx->sPosition.uToMove)) || + (!IS_CHECKING_MOVE(mv) && !InCheck(&ctx->sPosition, ctx->sPosition.uToMove))); // Compute extension ComputeMoveExtension(ctx, iAlpha, iBeta, - (ctx->sMoveStack.uBegin[ctx->uPly - 1] + - uMoveNum), - iRoughEval, + (ctx->sMoveStack.uBegin[ctx->uPly - 1] + uMoveNum), + iEval, uDepth, iCheckSee, &iExtend); - + // // Cap total extension plies spent on this line, same as the // non-split move loop in search.c does. @@ -1139,9 +1141,10 @@ Return value: // Decide how much (if any) to reduce this move's depth. // { - INT iLMR = GetLMRReduction(iRoughEval, + INT iLMR = GetLMRReduction(iEval, iAlpha, iBeta, + iImprovement, ctx, uDepth, (g_SplitInfo[u].uAlreadyDone + -- cgit v1.3