/** Copyright (c) Scott Gasch Module Name: searchsup.c Abstract: Search support routines. See also search.c, root.c, and split.c. Author: Scott Gasch (scott.gasch@gmail.com) 06 Oct 2005 Revision History: **/ #include "chess.h" extern SCORE g_iRootScore[2]; extern ULONG g_uHardExtendLimit; extern ULONG g_uIterateDepth; void UpdatePV(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv) /** Routine description: Update the principle variation at this depth. Parameters: SEARCHER_THREAD_CONTEXT *ctx, MOVE mv Return value: void **/ { PLY_INFO *this = &(ctx->sPlyInfo[ctx->uPly]); PLY_INFO *next = (this + 1); ULONG u = ctx->uPly; ASSERT(u < MAX_PLY_PER_SEARCH); this->PV[u] = mv; u++; // HASHMOVE/RECOGNMOVE/DRAWMOVE/MATEMOVE are sentinels, not real // moves -- WalkPV (util.c) treats any of them as a hard PV // truncation point and asserts the slot right after one is // always a zero terminator. Copying the child ply's PV tail // forward below would instead leave whatever move happens to // already be sitting in that reused sPlyInfo slot (sPlyInfo[] is // shared across every node that ever occupies this ply, never // zeroed between unrelated nodes) -- if some earlier, unrelated // node at this same ply also once wrote the same sentinel there // and nothing since overwrote it, that stale leftover reproduces // the sentinel value a second time in a row and trips the assert // (util.c:1093, found via debug_smoke_test.sh under MP). Hard- // terminate immediately instead of inheriting the child's tail. if ((mv.uMove == HASHMOVE.uMove) || (mv.uMove == RECOGNMOVE.uMove) || (mv.uMove == DRAWMOVE.uMove) || (mv.uMove == MATEMOVE.uMove)) { if (u < MAX_PLY_PER_SEARCH) { this->PV[u].uMove = 0; } return; } while(u < MAX_PLY_PER_SEARCH) { this->PV[u] = next->PV[u]; if (0 == this->PV[u].uMove) { break; } u++; } } FLAG CheckInputAndTimers(IN SEARCHER_THREAD_CONTEXT *ctx) /** Routine description: This code is called from search when the total number of nodes searched is a multiple of g_MoveTimer.uNodeCheckMask. Its job is to check for user input waiting on the input queue and to check to see if we are over a time limit. Parameters: void Return value: static FLAG : TRUE if the search should terminate and unroll, FALSE if the search can continue **/ { double dTimeStamp; // // See if there's user input to process. // if ((ctx->uThreadNumber == 0) && (NumberOfPendingInputEvents() != 0)) { ParseUserInput(TRUE); // // If the user input can be handled in the middle of the // search then it will have been. If it cannot be handled // without stopping the search then ParseUserInput will flip // this bit in the MoveTimer to tell us (any any other // searcher threads) to stop and unroll. // if (WE_SHOULD_STOP_SEARCHING) { return(TRUE); } } // // Also check time limits now. // if (-1 != g_MoveTimer.dSoftTimeLimit) { dTimeStamp = SystemTimeStamp(); if ((g_MoveTimer.bvFlags & TIMER_CURRENT_OBVIOUS) || (g_MoveTimer.bvFlags & TIMER_CURRENT_WONT_UNBLOCK)) { Trace("OBVIOUS MOVE / WON'T UNBLOCK --> stop searching now\n"); g_MoveTimer.bvFlags |= TIMER_STOPPING; return(TRUE); } if (dTimeStamp > g_MoveTimer.dSoftTimeLimit) { // // If we have exceeded the soft time limit, move now unless... // if ((!(g_MoveTimer.bvFlags & TIMER_JUST_OUT_OF_BOOK)) && (!(g_MoveTimer.bvFlags & TIMER_ROOT_POSITION_CRITICAL)) && (!(g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FL)) && (!(g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FH)) && (!(g_MoveTimer.bvFlags & TIMER_MANY_ROOT_FLS)) && (g_MoveTimer.bvFlags & TIMER_SEARCHING_FIRST_MOVE)) { Trace("SOFT TIMER (%3.1f sec) --> " "stop searching now\n", dTimeStamp - g_MoveTimer.dStartTime); g_MoveTimer.bvFlags |= TIMER_STOPPING; return(TRUE); } } // // If we have exceeded the hard limit, we have to move no matter // what. // if (dTimeStamp > g_MoveTimer.dHardTimeLimit) { Trace("HARD TIMER (%3.1f sec) --> " "stop searching now\n", dTimeStamp - g_MoveTimer.dStartTime); g_MoveTimer.bvFlags |= TIMER_STOPPING; return(TRUE); } } // // Also check raw node count limit here. // if (g_Options.u64MaxNodeCount != 0ULL && ctx->sCounters.tree.u64TotalNodeCount > g_Options.u64MaxNodeCount) { Trace("NODE COUNT LIMIT (limit %llu, searched %llu) " "--> stop searching now\n", g_Options.u64MaxNodeCount, ctx->sCounters.tree.u64TotalNodeCount); g_MoveTimer.bvFlags |= TIMER_STOPPING; return(TRUE); } return(FALSE); } FLAG ThreadUnderTerminatingSplit(IN SEARCHER_THREAD_CONTEXT *ctx) { ULONG u; // // A thread can be nested in more than one split at once (a helper // thread can itself call StartParallelSearch while inside // HelpSearch for an outer split), so pSplitInfo[] is a stack, not // a single slot -- slot 0 is the outermost split this thread is // part of, later slots are progressively more nested ones. Any of // them terminating means this thread's current work is moot, so // all populated slots must be checked, not just the first one // found. // for (u = 0; u < NUM_SPLIT_PTRS_IN_CONTEXT; u++) { if ((ctx->pSplitInfo[u] != NULL) && (ctx->pSplitInfo[u]->fTerminate == TRUE)) { return(TRUE); } } return(FALSE); } INT 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: True pre-LMR/pre-counter-move baseline: original binary history pruning (fixed -ONE_PLY), no graded table, no PV-parent guard, no 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. **/ { ASSERT(ctx->uPly > 0); ASSERT(mv.uMove); ASSERT((uMoveNum > 0) || (uLegalMoves == 0)); if ((!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0])) && (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) && ((ctx->uPly < 3) || (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) && !IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1]))) && (GetMoveFailHighPercentage(mv, NULL) <= 10)) { ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)); return(-ONE_PLY); } return(0); } SCORE DecodeMoveValueEstimate(IN MOVE mv, IN SCORE iRawValue, IN MOVE_SCORING_SCHEME eScheme) /** Routine description: generate.c has (at least) four distinct conventions for packing sMoveStack[].iValue (see MOVE_SCORING_SCHEME's own comment, chess.h), plus two more that aren't generate.c tier encodings at all (RescoreMovesViaSearch's real eval-axis score, and root.c's node- count/score composite). This function is the one place that knows how to turn a raw iValue back into an eval-axis (100=1-pawn) material estimate, given which scheme produced it -- every caller that needs an actual value rather than just a tier/leftover classification should go through here rather than inlining its own guess at the encoding. Parameters: IN MOVE mv, IN SCORE iRawValue, IN MOVE_SCORING_SCHEME eScheme Return value: SCORE **/ { switch (eScheme) { case MOVE_SCORING_IID_RESCORED: // Already a real, searched eval-axis score (reflects an // entire subtree, not just the immediate exchange) -- // trust it exactly as-is. return(iRawValue); case MOVE_SCORING_NORMAL: case MOVE_SCORING_QSEARCH_NO_CHECKS: // Identical +120 flat move-ordering bias plus small // MVV-LVA tie-break nudges for winning/even captures and // promotions -- harmless for sorting, but wrong on the // eval axis until backed out. if ((iRawValue >= SORT_THESE_FIRST) && IS_CAPTURE_OR_PROMOTION(mv)) { ASSERT(iRawValue > 0); iRawValue &= STRIP_OFF_FLAGS; iRawValue -= MOVE_SCORE_ORDERING_BIAS(mv); return(iRawValue); } // All quiet moves (including killer/killer-mate quiet // moves, which can reach SORT_THESE_FIRST or the killer- // tier bits via generate.c's ordering bonuses with no // relation to a move's real eval-axis value) collapse to // 0 here -- correct, since a quiet move's ordering bonus // carries no such estimate. A genuinely negative raw value // (a losing capture, scored without any tier flag) passes // through MIN0 unchanged, preserving its real (negative) // material estimate. // // FUTURE WORK: 0 is uniform across every quiet move, which // throws away signal we plausibly have. Two candidate // refinements, deliberately not implemented yet (each needs // its own isolated A/B, not bundled together): // 1. A small flat bonus (tested at +10: net wash, moved // solves from confident_quick to hard_quick rather than // a clear win/loss -- see RESULTS.md) for killer/ // killer-mate moves, on the theory that a move which // already caused a cutoff elsewhere in the tree is more // likely to be good than an untested quiet shuffle. // 2. eval.c square-delta scoring (e.g. PAWN_CENTRALITY_BONUS/ // KNIGHT_CENTRALITY_BONUS[cTo]-[cFrom]) for a directional, // if not strictly accurate, signal on ordinary quiet // moves -- eval.c's real value is far more than per-square // tables (mobility, king safety, pawn structure), so this // would only ever be directionally suggestive, not exact. return(MIN0(iRawValue)); case MOVE_SCORING_QSEARCH_CHECKS: // Same +120 convention, plus two QSearch-only ordering // nudges baked into the same value by // _ScoreQSearchMovesInclChecks: +4 for a checking move, // +64 for a same-square recapture. The checking-move term // is backed out here; the same-square-recapture term isn't // (this function doesn't receive mvLast) -- a known, // small (<=64, well under a minor piece) residual // imprecision for that specific case, not silently wrong // by an unbounded amount the way the pre-fix code was for // escapes. if ((iRawValue >= SORT_THESE_FIRST) && IS_CAPTURE_OR_PROMOTION(mv)) { ASSERT(iRawValue > 0); iRawValue &= STRIP_OFF_FLAGS; iRawValue -= MOVE_SCORE_ORDERING_BIAS(mv); if (IS_CHECKING_MOVE(mv)) { iRawValue -= 4; } return(iRawValue); } return(MIN0(iRawValue)); case MOVE_SCORING_ESCAPE: // _ScoreAllEscapes' winning-capture encoding uses a // DIFFERENT bias than _ScoreAllMoves (no +120) plus an // IS_KING(mv.pMoved) right-shift that's lossy -- can't be // inverted exactly. Even captures are tagged FIRST_KILLER, // not SORT_THESE_FIRST, so they would not even reach a // capture-decode branch keyed on that bit. Rather than try // to invert either packed encoding, just recompute the // cheap raw material estimate directly from the move's own // fields -- exactly what _ScoreAllEscapes itself computes // as ITS OWN first-pass estimate before ever calling SEE // (deliberately not re-invoking SEE here -- same axis, // just cheaper and not dependent on reversing a lossy // encoding). if (IS_CAPTURE_OR_PROMOTION(mv)) { return((SCORE)(PIECE_VALUE(mv.pCaptured) - PIECE_VALUE(mv.pMoved))); } return(0); case MOVE_SCORING_ROOT: default: // Not a generate.c tier encoding at all -- a node-count/ // score composite (root.c), only ever populates ply 0's // move stack. No current caller asks to decode a root-ply // move here; fail loudly rather than silently return a // number that looks plausible but isn't. ASSERT(FALSE); return(0); } } SCORE ComputeMoveScore(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, IN ULONG uMoveNum) { SCORE iMoveScore = (PIECE_VALUE(mv.pCaptured) + PIECE_VALUE(mv.pPromoted)); if (uMoveNum != (ULONG)-1) { ASSERT(uMoveNum < MAX_MOVE_STACK); ASSERT(IS_SAME_MOVE(mv, ctx->sMoveStack.mvf[uMoveNum].mv)); ASSERT(ctx->uPly > 0); // Every current caller (search.c's EFP check, and // ComputeMoveExtension's two ComputeMoveScore() call sites) only // reaches here after MakeMove(ctx, mv) has already succeeded, so // ctx->uPly is always the *child's* ply here -- uMoveNum indexes // the parent's move list, i.e. ctx->uPly - 1, not ctx->uPly. That's // the ply whatever scoring pass ran (generate.c's scorers, // RescoreMovesViaSearch) actually scored, so that's the ply // whose eMoveScoringScheme is authoritative here. iMoveScore = DecodeMoveValueEstimate( mv, ctx->sMoveStack.mvf[uMoveNum].iValue, ctx->sPlyInfo[ctx->uPly - 1].eMoveScoringScheme); } return(iMoveScore); } SCORE GetMoveSee(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, IN ULONG uMoveNum) /** Routine description: SEE for a checking move or a non-pawn capture, used by ComputeMoveExtension's callers (Search, HelpSearch, and eventually QSearch) to decide how much to extend/reduce a check, and (as of the recapture-extension soundness gate) to judge a recapture too. One call site, one SEE per move regardless of how many of ComputeMoveExtension's gates end up wanting it -- SEE is one of the hottest routines in the tree, so callers compute this at most once per move and pass the single result into ComputeMoveExtension via iMoveSee, rather than each gate calling it independently. Must be computed on the PRE-move position -- see.c's exchange walk needs the piece still sitting on cFrom, and by the time ComputeMoveExtension runs the move has already been played. Move generation/scoring (_ScoreAllMoves, _ScoreAllEscapes in generate.c) already runs a real SEE on this same (pos, mv) pair whenever it scores an ambiguous capture or promotion, and stashes the sign in the move's MVF_SEE_KNOWN/MVF_SEE_NONNEGATIVE flags. Reuse that instead of walking the exchange (GetAttacks()) again. Only the sign matters to any caller of ComputeMoveExtension, so the cached value is coarsened to 0/-1. On a cache miss, use SeeFastSign (see.c) instead of a real SEE() call -- same reasoning as the cache-hit path above (only the sign ever reaches ComputeMoveExtension, both of its own iMoveSee checks are plain `< 0`/`>= 0`), but for the miss case there was no cached value to fall back to at all, so this always used to pay for a full SEE() exchange walk (list-build, heap, x-ray discovery) just to throw away everything but the sign. SeeFastSign is correctness-tested against real SEE()'s sign across thousands of random positions (testsee.c's TestSeeFastSign) and measured at 0.40x-0.65x SEE()'s own cycles/call, coarsened to the same 0/-1 convention as the cache-hit path for consistency. Parameters: SEARCHER_THREAD_CONTEXT *ctx : searcher thread context MOVE mv : the checking move or capture needing a soundness read ULONG uMoveNum : mv's index in ctx->sMoveStack.mvf[], or (ULONG)-1 if mv did not come from the move stack (e.g. the hash move) Return value: SCORE **/ { BITV bvFlags; ASSERT(IS_CHECKING_MOVE(mv) || (mv.pCaptured != NULL)); if (uMoveNum != (ULONG)-1) { ASSERT(uMoveNum < MAX_MOVE_STACK); ASSERT(IS_SAME_MOVE(mv, ctx->sMoveStack.mvf[uMoveNum].mv)); bvFlags = ctx->sMoveStack.mvf[uMoveNum].bvFlags; if (bvFlags & MVF_SEE_KNOWN) { return((bvFlags & MVF_SEE_NONNEGATIVE) ? 0 : -1); } } return(SeeFastSign(&ctx->sPosition, mv) ? 0 : -1); } void ComputeMoveExtension(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta, IN ULONG uMoveNum, IN SCORE iRoughEval, IN ULONG uDepth, IN SCORE iMoveSee, IN FLAG fIsLeftoverMove, IN OUT INT *piExtend) /** Routine description: This routine is called by Search and by HelpSearch (in split.c). It's job is to assign a move-based extension for the move mv. This extension should be between -ONE_PLY (reduction) and +ONE_PLY (extension). Note: this code is executed after the move has already been played on the board! Parameters: IN SEARCHER_THREAD_CONTEXT *ctx : the searcher thread's context IN SCORE iAlpha : current alpha IN SCORE iBeta : current beta IN ULONG uMoveNum : move number in stack IN ULONG uDepth : remaining depth IN OUT INT *piExtend : extension amount (in/out) Return value: void **/ { static const SCORE _window[MAX_PLY_PER_SEARCH] = { -1, -1, 500, 500, 425, 425, 350, 350, 275, 275, 200, 200, // 0..11 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 12..23 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 24..35 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 36..47 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 48..59 150, 150, 150, 150 // 60..63 }; POSITION *pos = &ctx->sPosition; MOVE mvLast = ctx->sPlyInfo[ctx->uPly-2].mv; MOVE mv = ctx->sPlyInfo[ctx->uPly-1].mv; ULONG uColor = GET_COLOR(mv.pMoved); SCORE iMoveScore; #ifdef DEBUG int iM; // // Preconditions // ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); ASSERT(ctx->uPly >= 2); ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH); ASSERT(mv.uMove); ASSERT(*piExtend >= 0); #endif // Checking move extension. Crafty-style soundness gate: a check // that's really just a losing sacrifice (SEE < 0) still gets a small // consolation extension rather than none at all -- SEE can't see // multi-move combinations, so a "losing" sacrifice check is sometimes // actually a winning sham sacrifice a few moves later, and giving it // zero search priority risks missing exactly those. It just doesn't // get to compound the way a materially sound check does. if (IS_CHECKING_MOVE(mv)) { ASSERT(InCheck(pos, pos->uToMove)); INC(ctx->sCounters.extension.uCheck); if (iMoveSee < 0) { *piExtend += QUARTER_PLY; INC(ctx->sCounters.extension.uCheckByQuarterPly[QUARTER_PLY / QUARTER_PLY]); } else { if (pos->uNonPawnMaterial[FLIP(pos->uToMove)] > (VALUE_KING + VALUE_BISHOP)) { *piExtend += THREE_QUARTERS_PLY; INC(ctx->sCounters.extension.uCheckByQuarterPly[THREE_QUARTERS_PLY / QUARTER_PLY]); } else { *piExtend += QUARTER_PLY; INC(ctx->sCounters.extension.uCheckByQuarterPly[QUARTER_PLY / QUARTER_PLY]); } } } // Pawn push extension. RANK7/RANK2 already mean "one step from // promotion", so the pawn is a passer by definition -- no separate // passed-pawn test needed. Two cheap, eval-independent refinements // (both read only incrementally-maintained POSITION bitboards, no // Eval()/pawn-hash dependency, no sig-check needed): // // 1. Skip entirely if the promotion square itself is already // occupied (friend or foe) -- a push that can just be captured // or that's blocked from ever queening isn't worth the ply. // 2. The size of the bonus depends on whether the pawn's own // king/rook/queen actually defends it on cTo, not just // whether the king happens to be nearby (a king 2 squares // away that can't recapture doesn't help this pawn at all). if (IS_PAWN(mv.pMoved) && (RANK7(mv.cTo) || RANK2(mv.cTo))) { ULONG uPawnColor = GET_COLOR(mv.pMoved); COOR cPromo = mv.cTo + ((uPawnColor == WHITE) ? 0x10 : -0x10); if (!(pos->bbOccupied & COOR_TO_BB(cPromo))) { *piExtend += HALF_PLY; if (!fIsLeftoverMove || ((g_KingAttacksBB[mv.cTo] & COOR_TO_BB(KingPosition(pos, uPawnColor))) || (_RookAttacksBB(mv.cTo, pos->bbOccupied) & (pos->bbPieces[uPawnColor][ROOK] | pos->bbPieces[uPawnColor][QUEEN])) || (_BishopAttacksBB(mv.cTo, pos->bbOccupied) & pos->bbPieces[uPawnColor][QUEEN]))) { *piExtend += QUARTER_PLY; INC(ctx->sCounters.extension.uPawnPushByQuarterPly[THREE_QUARTERS_PLY / QUARTER_PLY]); } else { INC(ctx->sCounters.extension.uPawnPushByQuarterPly[HALF_PLY / QUARTER_PLY]); } INC(ctx->sCounters.extension.uPawnPush); } } // Responses to check extensions: if (IS_CHECKING_MOVE(mvLast)) { ASSERT(IS_ESCAPING_CHECK(mv)); iMoveScore = iRoughEval + ComputeMoveScore(ctx, mv, uMoveNum); // This is forced and cheap (1 move at the parent node). if (ONE_LEGAL_MOVE(ctx, ctx->uPly - 1) && CountKingSafetyDefects(&ctx->sPosition, uColor) > 2) { FLAG fBigBonus = (iMoveScore + VALUE_KNIGHT > iAlpha); *piExtend += (QUARTER_PLY + HALF_PLY * fBigBonus); INC(ctx->sCounters.extension.uOneLegalMove); INC(ctx->sCounters.extension.uOneLegalMoveByQuarterPly[ fBigBonus ? (THREE_QUARTERS_PLY / QUARTER_PLY) : (QUARTER_PLY / QUARTER_PLY)]); } // One "good" way to response to check? Kinda dodgy but "works". if (!fIsLeftoverMove && mv.pCaptured && (iRoughEval + 300 < iAlpha) && (iMoveScore + 50 > iAlpha)) { *piExtend += ONE_PLY; INC(ctx->sCounters.extension.uSingularReplyToCheck); } } // These last ones only happen if we are close to the root score. ASSERT(_window[ctx->uPly] > 0); if ((iRoughEval >= (g_iRootScore[uColor] - _window[ctx->uPly] * 2)) && (iRoughEval <= (g_iRootScore[uColor] + _window[ctx->uPly] * 2))) { // Endgame extension if ((ctx->sPlyInfo[1].uTotalNonPawns > 2) && ((TotalNonPawnCount(pos, BLACK) + TotalNonPawnCount(pos, WHITE)) == 2)) { if ((mv.pCaptured && !IS_PAWN(mv.pCaptured)) || (mvLast.pCaptured && !IS_PAWN(mvLast.pCaptured))) { *piExtend += HALF_PLY; INC(ctx->sCounters.extension.uEndgame); } } // Recapture extension. Own tighter (1x) window restored -- // measured on ECM.721 (ringers): sharing the outer 2x window // grew this position's recapture-fire count 6.8x vs HEAD // (17,569,874 -> 34,337,674 total nodes), far more than the // ~2x growth every other extension category saw from stacking // alone -- all in refuted alternative lines, not the winning // PV (which has zero recaptures on it). The 2x window did // recover ECM.735/ECM.443 by making trade-dense *correct* // lines eligible, but it's a net loss on positions where the // expensive trades are all in the lines being ruled out // instead. Back to the tighter window as the better tradeoff. if ((iRoughEval >= (g_iRootScore[uColor] - _window[ctx->uPly])) && (iRoughEval <= (g_iRootScore[uColor] + _window[ctx->uPly])) && (uDepth < THREE_PLY)) { if (!fIsLeftoverMove && mv.pCaptured && !IS_PAWN(mv.pCaptured) && (iMoveSee >= 0) && ((PIECE_VALUE(mv.pCaptured) == PIECE_VALUE(mvLast.pCaptured)) || ((mvLast.pPromoted) && (mv.cTo == mvLast.cTo)))) { *piExtend += HALF_PLY; INC(ctx->sCounters.extension.uRecapture); } } } // Don't let extensions add up to > 1 ply #ifdef DEBUG iM = MIN(ONE_PLY, *piExtend); #endif ASSERT(!(*piExtend & 0x80000000)); *piExtend = MINU(ONE_PLY, *piExtend); ASSERT(iM == *piExtend); // Scale back extensions that are very far from the root. Table // built in root.c from g_uIterateDepth (see its own construction // there for the exact arithmetic -- this is just a summary, keep // the two in sync): // // ┌─────────────────────────┬───────────┬────────────────────────────────┐ // │ ply range (× iterate │ reduction │ net effect │ // │ depth) │ │ │ // ├─────────────────────────┼───────────┼────────────────────────────────┤ // │ u < 1.5× │ 0 │ full extension kept │ // ├─────────────────────────┼───────────┼────────────────────────────────┤ // │ 1.5× ≤ u < 1.875× │ -1/4 ply │ │ // ├─────────────────────────┼───────────┼────────────────────────────────┤ // │ 1.875× ≤ u < 2.25× │ -1/2 ply │ │ // ├─────────────────────────┼───────────┼────────────────────────────────┤ // │ 2.25× ≤ u < 3× │ -3/4 ply │ only a +1 ply extension │ // │ │ │ can survive here │ // ├─────────────────────────┼───────────┼────────────────────────────────┤ // │ u ≥ 3× (hard limit) │ -all ply │ no extensions beyond here │ // └─────────────────────────┴───────────┴────────────────────────────────┘ // // NOTE: check extension in qsearch is handled differently, see search.c. // ASSERT(ctx->uPly != 0); ASSERT(ctx->uPly <= MAX_PLY_PER_SEARCH); *piExtend -= g_uExtensionReduction[ctx->uPly-1]; #ifdef DEBUG iM = MAX(0, *piExtend); #endif *piExtend = MAX0(*piExtend); ASSERT(iM == *piExtend); ctx->sPlyInfo[ctx->uPly-1].iExtensionAmount = *piExtend; ASSERT((0 <= *piExtend) && (*piExtend <= ONE_PLY)); } #ifdef DO_IID SCORE RescoreMovesViaSearch(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uDepth, IN SCORE iAlpha, IN SCORE iBeta) /** Routine description: This is my implementation of "internal iterative deepening". It's not really IID because it doesn't recurse on the same position. This code is called when we are at a PV node and have no hash move and no good capture from the generator. Instead of relying on only history / killer heuristics to order the moves instead we reduce the depth by two ply and search all the moves generated. The scores that come out of the reduced-depth search are then used to order the moves at the regular-depth search. This is somewhat recursive because the first move considered by the reduced-depth search may also have no hash move / good capture and invoke the whole process again. Parameters: IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uDepth, IN SCORE iAlpha, IN SCORE iBeta Return value: SCORE **/ { ULONG x, uBegin, uEnd; MOVE mv; SCORE iScore; SCORE iBestScore = -INFINITY_SCORE; ULONG uBest; FLAG fFailHigh = FALSE; SCORE rgScores[MAX_MOVES_PER_PLY]; // // Preconditions // ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); ASSERT(uDepth >= (IID_R_FACTOR + ONE_PLY)); // // Compute next depth. // // This used to recurse here first (call itself at this same // ctx->uPly, before the loop below), on the theory that an even // shallower rescore's *side effects* -- hash/killer/history table // population -- would help the loop below's own -Search() calls // find cutoffs faster. Measured (see lmr_testing/RESULTS.md): removing // it entirely produced a bit-identical result on all three test // suites (ecm_ringers/confident_quick/hard_quick). Its own writes to // iValue were always fully overwritten by this same call's loop // right after it (same ctx->uPly, same move-stack range), so it had // no way to help other than those side effects, and empirically it // wasn't -- just wasted nodes. Removed. uDepth -= (IID_R_FACTOR + ONE_PLY); ASSERT(uDepth < MAX_DEPTH_PER_SEARCH); // // Search the moves and remember the scores in a scratch array, NOT // directly into mvf[].iValue -- we don't yet know if we'll get an // honest score for every move at this ply (a fail-high partway // through means we stop early, deliberately, without searching the // rest). Committing partial data into iValue and then patching the // gaps with a sentinel (this function used to write -INFINITY_SCORE into // every unsearched move) makes the whole ply look "rescored" to // downstream code when it isn't really -- see the fail-high handling // below for why that matters. // uBegin = ctx->sMoveStack.uBegin[ctx->uPly]; uEnd = ctx->sMoveStack.uEnd[ctx->uPly]; ASSERT((uEnd - uBegin) <= MAX_MOVES_PER_PLY); for (x = uBest = uBegin; x < uEnd; x++) { SelectBestNoHistory(ctx, x); mv = ctx->sMoveStack.mvf[x].mv; mv.bvFlags |= WouldGiveCheck(ctx, mv); if (TRUE == MakeMove(ctx, mv)) { if (-INFINITY_SCORE == iBestScore) { iScore = -Search(ctx, -iBeta, -iAlpha, uDepth); } else { iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uDepth); if (iScore > iAlpha) { iScore = -Search(ctx, -iBeta, -iAlpha, uDepth); } } UnmakeMove(ctx, mv); rgScores[x - uBegin] = iScore; if (iScore > iBestScore) { uBest = x; iBestScore = iScore; if (iScore >= iBeta) { fFailHigh = TRUE; break; } } } else { // Genuinely illegal (pseudo-legal but leaves king in check) // -- this isn't "unknown," we know for a fact it's worthless // and the caller will skip it too when MakeMove fails again. rgScores[x - uBegin] = -INFINITY_SCORE; } } if (FALSE == fFailHigh) { // We have an honest, fully-searched score for every move at // this ply -- commit them all and let downstream code // (ComputeMoveScore, the main search loop's move-selection // call) trust iValue as a real eval-axis score. for (x = uBegin; x < uEnd; x++) { ctx->sMoveStack.mvf[x].iValue = rgScores[x - uBegin]; } ctx->sPlyInfo[ctx->uPly].eMoveScoringScheme = MOVE_SCORING_IID_RESCORED; } else { // We only know one honest thing: uBest is good enough to have // failed high at reduced depth. We do NOT have honest scores // for the rest (deliberately -- searching them would burn nodes // solely to confirm what we've already decided to do, which is // play uBest). Rather than inventing eval-axis values for moves // we never examined (the old code wrote -INFINITY_SCORE into all of // them, including -- until fixed -- overwriting uBest's own // just-computed score), leave every move's original generate.c // ordering value completely untouched and just bump uBest into // killer-tier territory so the normal (non-rescored) selection // path -- SelectBestWithHistory/NoHistory -- picks it first, the // same trick generate.c uses for a real killer move. Do NOT // change eMoveScoringScheme: this ply's iValue is back to being // whatever generate.c scheme originally scored it, not real // scores, for every move including uBest (whose bump is itself // just an ordering flag, not part of its own eval-axis value). ctx->sMoveStack.mvf[uBest].iValue |= FIRST_KILLER; } ASSERT(IS_VALID_SCORE(iBestScore)); return(iBestScore); } #endif FLAG MateDistancePruningCutoff(IN ULONG uPly, IN FLAG fInCheck, IN OUT SCORE *piBestScore, IN OUT SCORE *piAlpha, IN OUT SCORE *piBeta) /** Routine description: This idea (shamelessly?) "borrowed" from Fruit. The idea is that the worst score we can return from any node in the tree is if we are in checkmate right now (indeed, if we're not in check right now than the worst score we can return is mated-in-2-ply). Likewise the best score we can return from here is mate-in-1-ply. Use these facts to attempt to narrow the alpha..beta window. Indeed there are some cases where we can prune this entire tree branch. Parameters: ULONG uPly : ply from root FLAG InCheck : are we in check? SCORE *piBestScore : pointer to bestscore SCORE *piAlpha : pointer to alpha SCORE *piBeta : pointer to beta Return value: FLAG : TRUE if we can prune the branch outright, FALSE otherwise **/ { SCORE iScore = MATED_SCORE(uPly + 2 * !fInCheck); // // Do the alpha side // if (*piAlpha < iScore) { *piAlpha = iScore; if (iScore >= *piBeta) { *piBestScore = iScore; return(TRUE); } } // // Do the beta side // iScore = -1 * MATED_SCORE(uPly + 1); if (iScore < *piBeta) { *piBeta = iScore; if (iScore <= *piAlpha) { *piBestScore = iScore; return(TRUE); } } return(FALSE); } void DumpPlyInfoStack(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta) /** Routine description: Dump some information about the current search line; mainly here as a debugging aide. Note: this will not work on an MP searcher thread that is under a split node. Parameters: SEARCHER_THREAD_CONTEXT *ctx : searcher context to dump Return value: void **/ { ULONG u, v; POSITION *pos = GetRootPosition(); CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; char *p = PositionToFen(pos); PLY_INFO *q; FLAG fSeenQ = FALSE; SCORE iEval; static SEARCHER_THREAD_CONTEXT temp; InitializeSearcherContext(pos, &temp); Trace("Iterate Depth: %2u\tCurrent Ply: %2u\n", g_uIterateDepth, ctx->uPly); Trace("Qsearch Check: %2u\tCurrent Qdepth: %2u\n", pf->uQsearchCheckDepth, pf->uQsearchDepth); Trace("Current a..b: %d .. %d\n", iAlpha, iBeta); if (NULL != p) { Trace("Root: %s\n", p); SystemFreeMemory(p); } Trace("\n"); Trace("move\t number\t exten\t eval b.keval w.keval Danger Squares\n" "----------------------------------------------------------------------------\n"); ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH); for (u = 0; u < ctx->uPly; u++) { q = &ctx->sPlyInfo[u]; ASSERT(PositionsAreEquivalent(&q->sPosition, &temp.sPosition)); if ((FALSE == fSeenQ) && (q->fInQsearch == TRUE)) { p = PositionToFen(&temp.sPosition); if (NULL != p) { Trace("\nHorizon: %s\n\n", p); SystemFreeMemory(p); } fSeenQ = TRUE; } Trace("%02u.%-6s ", u, MoveToSan(q->mv, &temp.sPosition)); for (v = ctx->sMoveStack.uBegin[u]; v < ctx->sMoveStack.uEnd[u]; v++) { if (IS_SAME_MOVE(q->mv, ctx->sMoveStack.mvf[v].mv)) { Trace("%u/%u", v - ctx->sMoveStack.uBegin[u] + 1, MOVE_COUNT(ctx, u)); } } Trace("\t"); if (FALSE == MakeMove(&temp, q->mv)) { Trace("Illegal move?!\n"); return; } if (q->iExtensionAmount != 0) { Trace("%-3u\t", q->iExtensionAmount); } else { Trace(" \t"); } iEval = Eval(&temp, -INFINITY_SCORE, +INFINITY_SCORE, NULL); Trace("%5s (%+2d) | ", ScoreToString(iEval), temp.sPosition.iMaterialBalance[temp.sPosition.uToMove] / 100); Trace("%5s (%2u) | ", ScoreToString(temp.sPlyInfo[temp.uPly].iKingScore[BLACK]), CountKingSafetyDefects(&temp.sPosition, BLACK)); Trace("%5s (%2u) ", ScoreToString(temp.sPlyInfo[temp.uPly].iKingScore[WHITE]), CountKingSafetyDefects(&temp.sPosition, WHITE)); Trace("\n"); } p = PositionToFen(&ctx->sPosition); if (NULL != p) { Trace("\n"); Trace("Now: %s\n", p); SystemFreeMemory(p); } } FLAG CommonSearchInit(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piAlpha, IN OUT SCORE *piBeta, IN OUT SCORE *piScore) /** Routine description: A set of common code that is called by Search and QSearch. It does the following: 1. Increment the total node counter 2. Clears pi->mvBest and cDanger squares 3. Possibly check for user input or timer expiration 4. Checks to see if the position is a draw 5. Makes sure ctx->uPly is not too deep 6. Sets pi->fInCheck 7. Does mate-distance pruning Parameters: IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piAlpha, IN OUT SCORE *piBeta, IN OUT SCORE *piScore Return value: FLAG : TRUE if the search node should be aborted (return *piScore) FALSE otherwise (*piAlpha, *piBeta possibly adjusted) **/ { PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; FLAG fRet = TRUE; ASSERT(*piAlpha < *piBeta); // // Increment node count and see if we need to check input / timer // ctx->sCounters.tree.u64TotalNodeCount++; ASSERT(ctx->sCounters.tree.u64TotalNodeCount > 0); if ((ctx->sCounters.tree.u64TotalNodeCount & g_MoveTimer.uNodeCheckMask) == 0) { (void)CheckInputAndTimers(ctx); } // // Make sure that the time allotted to search in has not expired // and (if this is an MP search) that we are still doing relevant work. // if (WE_SHOULD_STOP_SEARCHING) { // 2026-09-18: same staleness hazard as the IsDraw/too-deep // paths below -- clear this ply's own PV[] slot too, not just // mvBest. See the IsDraw branch's comment for the full // mechanism (an ancestor's UpdatePV blindly copies this row // forward assuming it's fresh). pi->mvBest.uMove = 0; pi->PV[ctx->uPly].uMove = 0; *piScore = INVALID_SCORE; goto end; } // // Set fInCheck in this ply info struct // pi->fInCheck = (IS_CHECKING_MOVE((pi-1)->mv) != 0); ASSERT((pi->fInCheck && (InCheck(&ctx->sPosition, ctx->sPosition.uToMove))) || (!pi->fInCheck && (!InCheck(&ctx->sPosition, ctx->sPosition.uToMove)))); // // See if this position is a draw -- checked before the too-deep // bailout below on purpose: a position can be simultaneously // "too deep" (hit the ply/qsearch-extend-limit ceiling) and // genuinely drawn (repetition/50-move), and a draw is a known, // exact fact about the position, not an estimate -- it would be // strictly worse to throw that away for an alpha/Eval() // approximation just because we also happened to run out of // search room at the same node. // if (TRUE == IsDraw(ctx)) { // Every early exit from this function must clear pi->mvBest // itself, since the real reset further down is never reached // from here. Found via a DEBUG-build assertion failure: // TryNullmovePruning reading (pi+1)->mvBest as if it reflected // the null-move probe's own search, when it was actually stale // data left by a completely unrelated earlier node that once // occupied the same ply slot and bailed out via this exact path // without ever being cleared. pi->mvBest.uMove = 0; INC(ctx->sCounters.tree.u64LeafCount); *piScore = g_iDrawScore[ctx->sPosition.uToMove]; // 2026-09-18: pi->PV[ctx->uPly] has the exact same staleness // hazard as pi->mvBest above, but was only ever cleared // conditionally, via UpdatePV(ctx, DRAWMOVE) -- and only when // the draw score actually falls in the open (alpha, beta) // window. When it doesn't, this ply's PV[] row is left // whatever an unrelated earlier node last wrote there. // sPlyInfo[] rows are shared/reused across every node that // ever occupies a given ply (see UpdatePV's own sentinel-case // comment), so a later ancestor's UpdatePV can blindly copy // that stale row forward via `this->PV[u] = next->PV[u]`, // trusting its zero-terminator as proof of freshness -- // splicing a leftover move from a completely different // subtree onto the real line. This is the root cause of a // WalkPV/MakeMove assertion failure (move.c:881, // "ASSERT(!IS_EMPTY(pCaptured))" -- a move that's real // *somewhere* but whose capture target is empty on the // actual board) reproduced against tests/cross_sectional_ // 200k.ep_. Clear unconditionally so a non-window draw score // can't leave this row stale. if ((*piAlpha < *piScore) && (*piScore < *piBeta)) { UpdatePV(ctx, DRAWMOVE); } else { pi->PV[ctx->uPly].uMove = 0; } DTTRACE(""); goto end; } // // Make sure we have not exceeded max ply; note that since this // is checked at the beginning of search/qsearch and if we let // the past they will call MakeMove this must cut off one ply // before the hard limit. // if ((ctx->uPly >= (MAX_PLY_PER_SEARCH - 1)) || (ctx->sSearchFlags.uQsearchDepth >= g_uHardExtendLimit)) { #ifdef PERF_COUNTERS if (ctx->uPly >= (MAX_PLY_PER_SEARCH - 1)) { INC(ctx->sCounters.tree.u64TooDeepPlyLimit); } else { INC(ctx->sCounters.tree.u64TooDeepQsearchExtendLimit); } #endif // Was an unconditional *piScore = *piBeta -- an unearned // fail-high claim ("this line is at least beta") with zero // evidence behind it, right at the moment we're giving up // because we ran out of room to actually determine anything. // A fail-low (return alpha) is the honest "couldn't prove // this helps" posture every other give-up path in this engine // uses. When NOT in check we can do better than a bare // fail-low, though: fall back to a real Eval() call, the same // convention normal QSearch's own stand-pat uses at its // horizon. NOT when in check -- IS_CHECKING_MOVE((pi-1)->mv) // is the same cheap (no board scan) check pi->fInCheck itself // uses a few lines below -- Eval() on an in-check position is // exactly the thing QSearchFromCheckNoStandPat's entire // design exists to avoid trusting (see its header comment): // static material/positional terms can't tell "checked with a // totally safe escape" from "checked and actually in danger." if (pi->fInCheck) { *piScore = *piAlpha; pi->iEval = INVALID_SCORE; } else { *piScore = Eval(ctx, *piAlpha, *piBeta, NULL); pi->iEval = *piScore; } // See the IsDraw branch above -- same staleness hazard, same // fix -- this path returns a live, legitimate score (either a // real Eval() call or *piAlpha) that absolutely can raise an // ancestor's alpha, and is reached constantly (any node // against the ply ceiling or qsearch-extend limit), making it // the most likely real source of the reproduced WalkPV // staleness bug (see the IsDraw branch's comment for the full // mechanism and the move.c:881 assert it produces). pi->mvBest.uMove = 0; pi->PV[ctx->uPly].uMove = 0; DTTRACE(""); goto end; } // // Erase deeper killer moves // if (ctx->uPly + 2 < MAX_PLY_PER_SEARCH) { ctx->mvKiller[ctx->uPly + 2][0].uMove = 0; ctx->mvKiller[ctx->uPly + 2][1].uMove = 0; } // // This code is for a debug option where I dump paths from root // to leaf along with extensions and evals at each node in the // path for debugging/brainstorming purposes. // pi->PV[ctx->uPly].uMove = 0; pi->mvBest.uMove = 0; pi->iExtensionAmount = 0; pi->iEval = INVALID_SCORE; #if 0 if ((g_uIterateDepth > 5) && (ctx->uPly > 2.5 * g_uIterateDepth)) { DumpPlyInfoStack(ctx, *piAlpha, *piBeta); } #endif // // Do mate-distance pruning // if (TRUE == MateDistancePruningCutoff(ctx->uPly, pi->fInCheck, piScore, piAlpha, piBeta)) { ASSERT(*piScore != -INFINITY_SCORE); ASSERT((*piScore <= *piAlpha) || (*piScore >= *piBeta)); goto end; } #ifdef DEBUG pi->iAlpha = *piAlpha; pi->iBeta = *piBeta; #endif // Classic PVS node typing (see NODE_TYPE's definition in chess.h). // Centralized here rather than in each caller's move loop // (search.c, root.c, split.c) since CommonSearchInit is the one // place both Search() and QSearch() funnel through -- a wide // window is unambiguously PV regardless of move number (this // covers "first move of a PV node" for free, no need to track // which move number got us here); a narrow window's type depends // only on the PARENT's own type, not on move number either: a CUT // parent's children are ALL (expected to fail low, must search // everything to prove it), and both a PV parent's non-first // children AND an ALL parent's children are CUT (expected to fail // high). The ctx->uPly==0 guard is defensive only -- root is // always called with a wide window in practice, so the width check // above already handles it. if (*piBeta != *piAlpha + 1) { pi->eNodeType = NODE_PV; } else if (ctx->uPly == 0) { pi->eNodeType = NODE_CUT; } else { NODE_TYPE eParentType = ctx->sPlyInfo[ctx->uPly - 1].eNodeType; pi->eNodeType = (NODE_CUT == eParentType) ? NODE_ALL : NODE_CUT; } fRet = FALSE; end: ASSERT(IS_VALID_FLAG(fRet)); return(fRet); } ULONG SelectNullmoveRFactor(SEARCHER_THREAD_CONTEXT *ctx, INT uDepth) { ULONG u; ULONG uMaxPiecesPerSide = MAXU(TotalNonPawnCount(&ctx->sPosition, WHITE), TotalNonPawnCount(&ctx->sPosition, BLACK)); ASSERT(uMaxPiecesPerSide <= 16); if (uMaxPiecesPerSide < 3) { // Sparse material on the mover's side: stay with the // conservative, non-growing reduction rather than risk a // zugzwang-prone position getting an aggressive R. (The // TotalNonPawnCount < 4 verification search in // TryNullmovePruning is the other half of this safety net.) u = TWO_PLY; } else { // Crafty-style growth: R = 3 + depth / 6 (in whole plies), // scaled into our fractional-ply depth units. u = THREE_PLY + ((uDepth / (6 * ONE_PLY)) * ONE_PLY); } return(u); } FLAG WeShouldTryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx, SCORE iAlpha, SCORE iBeta, SCORE iEval, SCORE iImprovement, ULONG uNullDepth) /** Routine description: Two-stage try/skip decision, replacing the old flat >2-non-pawn- piece gate plus per-depth eval-margin table. Calibrated from a 30K-position, sd-10, ~9-billion-attempt null-move precision/recall/ EV harness (2026-09-24, two revisions -- see nullmove_calib/run_2026-09-24_sd10_30k_v2/, the second and authoritative one). iImprovement and uNullDepth are currently unused: the Stage 1 thresholds below are flat, not depth- or improvement-scaled, and Stage 2 doesn't need its own gate at all (see below). Kept in the signature to avoid touching call sites. Stage 1 (safety): is a null-move fail-high here even trustworthy? Gated on the MOVER's own non-pawn piece count -- TotalNonPawnCount (pos, pos->uToMove), NOT MAX(white,black) as an earlier revision of this gate (and of the calibration harness that measured it) used. Zugzwang is a property of the side being given the free "pass", so the opponent's material shouldn't matter -- confirmed empirically: (maxMaterial=6+, moverMaterial=2) measured a 0.30% false-positive rate, indistinguishable from the worst low-material cells overall, despite "6+" sounding safe. A materially-heavier opponent does not protect a mover that is itself thin on material. Measured false-positive rate (a null fail-high the real search didn't confirm) by mover's own material x eval-vs-beta deficit: deficit<-300 -300..-100 -100..0 0..100 100..300 300+ mover 0-1 pcs: 5.57% 1.35% 0.82% 1.02% 0.28% 0.12% mover 2 pcs: 3.73% 0.19% 0.31% 0.32% 0.02% 0.01% mover 3-5 pcs: 0.91% 0.20% 0.09% 0.002% 0.001% 0.0005% mover 6+ pcs: 0.02% 0.002% 0.001% 0.0002% 0.0001% 0.0001% 6+ pieces is safe (<=0.02%) at EVERY deficit measured, even the most negative -- no deficit floor needed there at all. 2 pieces is actually salvageable (0.01-0.02%, comparable to the safest cells overall) once deficit >= 100, unlike a flatly-disabled <=2 rule would assume -- but <=1 piece never gets safe (worst case 0.12% at its *best* deficit band), so that tier is disabled outright rather than deficit-gated. Stage 2 (profitability/EV): given Stage 1 passes, is trying still worth the reduced-depth probe's node cost? Checked directly against the same run's EV data (EV = successRate*(realLoopCost-nullProbeCost) - (1-successRate)*nullProbeCost, in nodes saved per attempt) across every (depth, material) cell that survives the Stage 1 gate above: EV was strongly positive everywhere measured, from low single digits at shallow depth up to tens of thousands of nodes at deep probes, never negative. Stage 1 is already doing essentially all the discriminating work, so Stage 2 currently just returns TRUE unconditionally once Stage 1 passes -- no separate EV threshold is justified by this data. Revisit if a future, deeper or wider calibration run finds a safe-but-unprofitable pocket this one didn't sample. Parameters: SEARCHER_THREAD_CONTEXT *ctx, SCORE iAlpha, SCORE iBeta, SCORE iEval, SCORE iImprovement, ULONG uNullDepth Return value: FLAG **/ { POSITION *pos = &ctx->sPosition; PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; ULONG uMoverPiecesPerSide; SCORE iDeficit; ASSERT(IS_VALID_SCORE(iAlpha) && IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); ASSERT(IS_VALID_SCORE(iEval)); ASSERT(uNullDepth < MAX_PLY_PER_SEARCH * ONE_PLY); if ((FALSE == pf->fAvoidNullmove) && (FALSE == pi->fInCheck) && (iBeta != +INFINITY_SCORE) && (NODE_PV != pi->eNodeType)) { uMoverPiecesPerSide = TotalNonPawnCount(pos, pos->uToMove); iDeficit = iEval - iBeta; // ---- Stage 1: safety ---- if (uMoverPiecesPerSide <= 1) { return FALSE; // never measured safe, even at its best deficit } if ((uMoverPiecesPerSide == 2) && (iDeficit < 100)) { return FALSE; } if ((uMoverPiecesPerSide <= 5) && (iDeficit < -100)) { return FALSE; } // 6+ pieces: no deficit floor -- safe everywhere measured. // ---- Stage 2: efficiency/EV ---- // EV is strongly positive at every depth/material cell that // survives Stage 1 (see routine comment) -- nothing further to // gate on here today. return TRUE; } return FALSE; } FLAG TryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx, FLAG *pfThreat, SCORE iAlpha, SCORE iBeta, ULONG uNullDepth, INT *piOrigExtend, SCORE *piNullScore) { static INT _bm_by_piece[7] = { -1, -1, QUARTER_PLY, QUARTER_PLY, HALF_PLY, HALF_PLY, -1 }; POSITION *pos = &ctx->sPosition; PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; SCORE iVerifyScore; MOVE mv; MOVE mvRef; ASSERT(IS_VALID_SCORE(iAlpha) && IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); // TODO: more experiments with quick null // Ok, do it. ASSERT(!InCheck(pos, pos->uToMove)); VERIFY(MakeMove(ctx, NULLMOVE)); ASSERT(pos->u64NonPawnSig != pi->sPosition.u64NonPawnSig); ASSERT(pos->uToMove != pi->sPosition.uToMove); INC(ctx->sCounters.tree.u64NullMoves); // (Reduced depth) search under the nullmove; don't allow two // nullmoves in a row. ASSERT(pf->fAvoidNullmove == FALSE); pf->fAvoidNullmove = TRUE; *piNullScore = -Search(ctx, -iBeta, -iBeta + 1, uNullDepth); pf->fAvoidNullmove = FALSE; // Check the results if (*piNullScore >= iBeta) { UnmakeMove(ctx, NULLMOVE); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); // If there are very few pieces on the board, launch a // separate "verification search". if ((TotalNonPawnCount(pos, pos->uToMove) < 4) && (pf->fVerifyNullmove == TRUE)) { ASSERT(pf->fAvoidNullmove == FALSE); uNullDepth -= ONE_PLY; if (uNullDepth > MAX_DEPTH_PER_SEARCH) uNullDepth = 0; pf->fVerifyNullmove = FALSE; iVerifyScore = Search(ctx, iAlpha, iBeta, uNullDepth); pf->fVerifyNullmove = TRUE; if (iVerifyScore < iBeta) { // The nullmove failed high but the verify search // did not; we are in zug so extend. *piOrigExtend += ONE_PLY; INC(ctx->sCounters.extension.uZugzwang); return FALSE; } } // Nullmove succeeded and either no need to verify or verify // succeeded too. INC(ctx->sCounters.tree.u64NullMoveSuccess); if (*piNullScore > +NMATE) *piNullScore = +NMATE; return TRUE; } // Nullmove failed... mv = (pi+1)->mvBest; if (mv.uMove) { // See what we can learn from the move that refuted our nullmove. ASSERT(SanityCheckMove(pos, mv)); ASSERT(GET_COLOR(mv.pMoved) == pos->uToMove); ASSERT(ctx->uPly >= 2); // If we make a nullmove that fails because we lose a // piece, remember that the piece in question is in danger. if ((mv.pCaptured) && !IS_PAWN(mv.pCaptured)) { ASSERT(GET_COLOR(mv.pCaptured) == FLIP(pos->uToMove)); ASSERT(mv.pCaptured == pos->rgSquare[mv.cTo].pPiece); // Victim belongs to FLIP(pos->uToMove) here, i.e. the // mover at ctx->uPly - 1 (see RecordEnprisePieceAtPly). RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, mv.cTo); mvRef = ctx->mvNullmoveRefutations[ctx->uPly - 2]; if ((mvRef.uMove) && (mvRef.pCaptured == mv.pCaptured) && (mvRef.pMoved == mv.pMoved) && (mvRef.cTo != mv.cTo)) { ASSERT(GET_COLOR(mvRef.pCaptured) == FLIP(pos->uToMove)); ASSERT(mvRef.pCaptured); ASSERT(_bm_by_piece[PIECE_TYPE(mv.pCaptured)] > 0); ASSERT(_bm_by_piece[PIECE_TYPE(mv.pCaptured)] <= ONE_PLY); *piOrigExtend += _bm_by_piece[PIECE_TYPE(mv.pCaptured)]; INC(ctx->sCounters.extension.uBotvinnikMarkoff); } ctx->mvNullmoveRefutations[ctx->uPly] = mv; } else if (!IS_CAPTURE_OR_PROMOTION(mv)) { // A quiet move refuting our nullmove is itself decent // evidence that the move is strong here -- not enough to // extend on (that's the capture-only Botvinnik-Markoff // case above), but worth remembering as a fallback guess // for _NewKillerMove's empty-slot backfill, which is only // useful when this is actually a quiet move: a killer // slot only ever gets matched against generated quiet // candidates (IS_SAME_MOVE compares the pCaptured/ // pPromoted bits too), so storing a capture there (the // old unconditional behavior) could never match anything // and was silently dead. // // Deliberately a *separate* array from mvNullmoveRefutations, // not a shared slot -- that one is read two plies later // (ctx->uPly - 2, above) expecting a capture, to detect the // same-piece-two-different-squares Botvinnik-Markoff pattern. // Writing a quiet move into that same slot would silently // clobber the capture history the extension depends on. ctx->mvNullmoveQuietRefutations[ctx->uPly] = mv; } // This is an idea from Tord Romstad on ccc: if we are below a // history reduced node and we try a nullmove and the nullmove // fails low and the move that refuted the nullmove involves // the same piece moved in the reduced move at ply-1 then bail // out of the reduced depth search now and research at full // depth. The move that was reduced had some tactical // significance. ASSERT(IS_ON_BOARD(mv.cFrom)); if ((mv.cFrom == (pi-1)->mv.cTo) && ((pi-1)->iExtensionAmount < 0)) { ASSERT(GET_COLOR(mv.pMoved) == GET_COLOR((pi-1)->mv.pMoved)); UnmakeMove(ctx, NULLMOVE); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); *piNullScore = iAlpha - 1; return TRUE; } } // If we do nothing we are mated-in-n, therefore this is a // dangerous position so extend. This is Bruce Moreland's idea // originally. if (*piNullScore <= -NMATE) { if (mv.uMove && !IS_CAPTURE_OR_PROMOTION(mv)) { ASSERT(SanityCheckMove(pos, mv)); ASSERT(GET_COLOR(mv.pMoved) == pos->uToMove); UpdateDynamicMoveOrdering(ctx, uNullDepth + TWO_PLY, mv, *piNullScore, 0); } *pfThreat = TRUE; } UnmakeMove(ctx, NULLMOVE); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); return FALSE; } #ifdef DEBUG FLAG SanityCheckMoves(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uCurrent, IN ULONG uType) /** Routine description: Support routine to sanity check that: 1. The moves before uCurrent on the move stack were all marked as searched (or pruned) 2. The moves after uCurrent on the move stack are all zero value moves and not checking moves. Parameters: SEARCHER_THREAD_CONTEXT *ctx, ULONG uCurrent, ULONG uType Return value: FLAG **/ { ULONG x; if (WE_SHOULD_STOP_SEARCHING) { return(TRUE); } // // Check moves yet to be searched // if (uType & VERIFY_AFTER) { for (x = uCurrent; x < ctx->sMoveStack.uEnd[ctx->uPly]; x++) { ASSERT(ctx->sMoveStack.mvf[x].iValue <= 0); ASSERT(!IS_CHECKING_MOVE(ctx->sMoveStack.mvf[x].mv)); } } // // Check moves already searched // if (uType & VERIFY_BEFORE) { for (x = uCurrent - 1; ((x >= ctx->sMoveStack.uBegin[ctx->uPly]) && (x != (ULONG)-1)); x--) { ASSERT(ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED); } } return(TRUE); } #endif