/** Copyright (c) Scott Gasch Module Name: search.c Abstract: Recursive chess tree searching. See also split.c. "A type 1 node is also called a PV node. The root of the tree is a type-1 node, and the *first* successor of a type-1 node is a type-1 node also. A type-1 node must have all branches examined, but it is unique in that we don't know anything about alpha and beta yet, because we haven't searched the first move to establish them. A type 2 node is either (a) a successor of any type-3 node, or, (b) it's any successor (other than the first) of a type-1 node. With perfect move ordering, the first branch at a type-2 node will "refute" the move made at the previous ply via the alpha/beta algorithm. This node requires good move ordering, because you have to find a move good enough that your opponent would not play the move he chose that led to this position. If you try a poor move first, it won't produce a cutoff, and you have to search another move (or more) until you find the "good" move that would make him not play his move. A type-3 node follows a type-2 node. Here, you have to try every move at your disposal. Since your opponent (at the previous ply) has played a "strong" move (supposedly the "best" move) you are going to have to try every move you have in an effort to refute this move. None will do so (unless your opponent tried some poor move first due to incorrect move ordering). Here, move ordering is not worth the trouble, since the ordering won't let you avoid searching some moves. Of course, with the transposition / refutation table, ordering might help you get more "hits" if your table is not large enough... As you can see, at type-1 nodes you have to do good move ordering to choose that "1" move (or to choose that one out of a very few) that is good enough to cause a cutoff, while avoiding choosing those that are no good. At a type-1 node, the same thing applies. If you don't pick the best move first (take the moves at the root for example) you will search an inferior move, establish alpha or beta incorrectly, and thereby increase the size of the total tree by a *substantial* amount. By the way, some authors call type-1 nodes "PV" nodes, type-2 nodes "CUT" nodes, and type-3 nodes "ALL" nodes. These make it easier to read, but, unfortunately, I "cut my teeth" on the Knuth/Moore paper and think in terms of type 1,2,3." --Bob Hyatt, r.g.c.c Author: Scott Gasch (scott.gasch@gmail.com) 21 May 2004 Revision History: $Id: search.c 345 2007-12-02 22:56:42Z scott $ **/ #include "chess.h" extern ULONG g_uIterateDepth; extern FLAG g_fCanSplit[MAX_PLY_PER_SEARCH]; #define TRY_HASH_MOVE (0) #define GENERATE_MOVES (1) #define PREPARE_TO_TRY_MOVES (2) #define TRY_GENERATED_MOVES (3) // EFP's fail-high-history exemption: below EFP_FH_MIN_SAMPLES // observations, GetMoveFailHighPctThousandths's result isn't trusted // enough to override the static-eval-based decision either way. // THOUSANDTHS, not whole percent, since 2026-10-02's rename -- 100 // thousandths == 10%, unchanged in effect from the old whole-percent // EFP_FH_PRUNE_THRESHOLD of 10. #define EFP_FH_MIN_SAMPLES (5) #define EFP_FH_PRUNE_THRESHOLD_PCT_THOUSANDTHS (10000) // 10% // 2026-10-02: the joint-table-driven graduated-LMR decision itself // (bucket helpers, _JointTablePredictedFHThousandths/_JointTableExtraPlies, // JOINT_EXTRA_TIER*_THOUSANDTHS, the floor/cap clamp) moved into // GetLMRReduction (searchsup.c) -- this file used to make that // decision as post-processing on top of GetLMRReduction's own // baseline, split across two files/two inconsistent dynamic checks // purely to minimize the original diff against HEAD's LMR. The move // loop below now just calls GetLMRReduction once and uses its result. // // EstimateHangingMaterialCp/HangCpBucket/GapCpBucket/MoveNumBucket/ // DepthBucket moved there too but are no longer file-static -- the // measurement/collection block further below (gated on // fPruneReduceEligible alone, independent of the LMR decision -- this // is what's still generating the next round of g_uJointFHThousandths // data) still needs them, so they're declared in chess.h and called // from here unchanged in behavior, just by their new (un-underscored) // public names. #if (defined(PERF_COUNTERS) && defined(PRUNE_VERIFY)) || defined(PRUNE_LIVE) // Band a deep-prune candidate by the predicted FH% the decision was // made on (thousandths of a percent; post-Wilson-re-bake that value // already encodes the cell's own sample confidence -- data.c header). // Banding by the decision variable is what lets one run answer "is // 'prune if predicted <= K' sound" for every candidate K at once. #if defined(PERF_COUNTERS) && defined(PRUNE_VERIFY) static ULONG PruneVerifyBand(ULONG uPredicted) { if (uPredicted == 0) return 0; if (uPredicted == 1) return 1; if (uPredicted == 2) return 2; if (uPredicted <= 5) return 3; if (uPredicted <= 10) return 4; if (uPredicted <= 50) return 5; if (uPredicted <= 500) return 6; return 7; } #endif // Mirror of searchsup.c's file-static _ShipDepthBucket. Duplicated // rather than exported because this is calibration-only code that // should leave no trace in a normal build; if PRUNE_VERIFY ever // graduates to something permanent, hoist the real one into chess.h // instead of keeping two copies. static ULONG ShipDepthBucketPublic(ULONG uRawDepthBucket) { if (uRawDepthBucket <= 9) return uRawDepthBucket; if (uRawDepthBucket <= 13) return 10; return 11; } #define JOINT_TABLE_SENTINEL_PUBLIC (0xFFFF) static ULONG ShipLateBucketPublic(ULONG uRawLateBucket) { if ((uRawLateBucket >= 2) && (uRawLateBucket <= 13)) return uRawLateBucket - 2; if (uRawLateBucket <= 21) return 12; if (uRawLateBucket <= 31) return 13; return 14; } // _JointTablePredictedFHThousandths (searchsup.c, declared in chess.h) // is called directly from this file's hoisted per-move lookup block // below -- no local mirror, unlike ShipDepthBucketPublic/ // ShipLateBucketPublic above, which really do need file-local // standalone copies (see that function's own note on why). // Local mirrors of searchsup.c's file-static AttemptsBucket/RateBucket // (calibration-only; see ShipDepthBucketPublic's note on duplication). #if defined(PERF_COUNTERS) && defined(PRUNE_VERIFY) static ULONG PvAttBucket(ULONG uAttempts) { if (0 == uAttempts) return 0; if (1 == uAttempts) return 1; if (2 == uAttempts) return 2; if (uAttempts <= 4) return 3; if (uAttempts <= 9) return 4; if (uAttempts <= 24) return 5; if (uAttempts <= 99) return 6; return 7; } static ULONG PvRateBucket(ULONG uPct) { if (0 == uPct) return 0; if (uPct <= 100) return 1; if (uPct <= 400) return 2; if (uPct <= 900) return 3; if (uPct <= 1900) return 4; if (uPct <= 4900) return 5; if (uPct <= 9900) return 6; return 7; } #endif #define PRUNE_LIVE_SENTINEL JOINT_TABLE_SENTINEL_PUBLIC #define PruneLivePredict PruneVerifyPredict static ULONG PruneVerifyPredict(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, IN ULONG uMoveNum, IN ULONG uLegalMoves, IN SCORE iAlpha, IN SCORE iEval, IN ULONG uDepth, IN BITBOARD bbMinor[2], IN BITBOARD bbRook[2], OUT ULONG *puShipDepth) { SCORE iHangCp = EstimateHangingMaterialCp(ctx, mv, uMoveNum, bbMinor, bbRook); ULONG uDumb = HangCpBucket(iHangCp); ULONG uShipD = ShipDepthBucketPublic(DepthBucket(uDepth / ONE_PLY)); *puShipDepth = uShipD; if (1 == uDumb) { return JOINT_TABLE_SENTINEL_PUBLIC; } return g_uJointFHThousandths[uShipD][uDumb] [GapCpBucket((SCORE)(iAlpha - iEval))] [ShipLateBucketPublic(MoveNumBucket(uLegalMoves))]; } #endif #ifdef JOINT_EXTRA_VERIFY // 2026-09-28: buckets the FULLY (base + extra) reduced search's actual // remaining depth by EFP's own two-tier margin-schedule boundaries // (search.c's "selective futility"/"extended futility" tiers, keyed to // ONE_PLY+THREE_QUARTERS_PLY and TWO_PLY+THREE_QUARTERS_PLY -- see that // code's own comment) rather than plain whole-ply buckets. The // depth-bucketed silent-miss calibration showed a spike specifically // at whole-ply-bucket "remaining depth 2", which straddles both EFP // tier boundaries -- this re-buckets on the ACTUAL boundaries to test // whether the spike is really an EFP-tier-window effect (a different // pruning mechanism behaving differently in that specific band) rather // than "shallower is chaotic" in the simple monotonic sense. static ULONG _PostReduceDepthBucketEfpAligned(ULONG uNextDepthRaw) { if (uNextDepthRaw < ONE_PLY) { return 0; // shouldn't happen given the JOINT_EXTRA_MIN_REMAINING_DEPTH floor -- safety net } if (uNextDepthRaw <= (ONE_PLY + THREE_QUARTERS_PLY)) { return 1; // EFP "selective futility" tier active } if (uNextDepthRaw <= (TWO_PLY + THREE_QUARTERS_PLY)) { return 2; // EFP "extended futility" tier active } if (uNextDepthRaw <= (TWO_PLY + THREE_QUARTERS_PLY + TWO_PLY)) { return 3; // no EFP, but still nearby } return 4; // no EFP, comfortably deeper } #endif // EXPERIMENT: is history+continuation evidence predictive of a // countermove match's own FH%? See chess.h's CM_EVIDENCE_BUCKETS // comment. Buckets by log-ish bands rather than linear, since evidence // values span 0 to ~STRIP_OFF_FLAGS*2 (~16.7M). #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION static ULONG _CMEvidenceBucket(ULONG uEvidence) { static const ULONG uFloors[CM_EVIDENCE_BUCKETS] = { 0, 1, 100, 1000, 10000, 100000, 1000000 }; ULONG i; for (i = CM_EVIDENCE_BUCKETS; i > 0; i--) { if (uEvidence >= uFloors[i - 1]) { return(i - 1); } } return(0); } #endif #ifdef TEST_NULL // // Null-move try/avoid calibration harness. // // Question: given the current data (precision >99.9% almost everywhere, // false-positive/"null-move lie" risk concentrated by material and // deficit, EV strongly positive almost everywhere once restricted to // the safe region), can a two-stage try/skip policy do better than // today's flat material threshold + per-depth eval-margin table? // // Stage 1 (safety): is a null-move fail-high here even trustworthy? // Stage 2 (profitability/EV): given it's safe, is it worth the cost? // // fThreat, fSkipNull, and en-prise/trapped-piece state were bucketed in // an earlier revision of this harness (2026-09-24 run, saved under // nullmove_calib/run_2026-09-24_sd10_30k/) and shown to be either // already-validated non-tunable binary gates (fThreat/fSkipNull -- both // clearly reduce EV and precision/recall when set, and both already // gate the call to WeShouldTryNullmovePruning in Search(), so there's // no threshold left to calibrate) or not a safety signal at all // (en-prise/trapped predicts *lower recall*, not higher false-positive // risk -- a Stage 2, not Stage 1, concern). None of the three are // bucketed here; fThreat==FALSE && fSkipNull==FALSE are folded into // this probe's structural eligibility instead, matching production. // // This revision instead resolves two open questions from that first // run: // // 1. Is MAX(white,black) non-pawn piece count or the MOVER's own // count (TotalNonPawnCount(pos, pos->uToMove)) the better // Stage-1 safety predictor? Zugzwang is a property of the side // being given the free "pass", so mover-only is the more // causally-motivated signal, but the first run only measured // MAX(both) -- bucket both, jointly, and let the false-positive- // rate data settle it. // 2. The first run bucketed the *real* search's cost (the Stage-2 EV // calc's "cost of the alternative") by the null probe's own post- // reduction depth (uNullDepth), which is only meaningful via // whatever R schedule (SelectNullmoveRFactor) happened to be // compiled in at the time -- useless for evaluating a *different* // R schedule later. The real search's cost is fundamentally a // function of the OUTER, pre-reduction uDepth (how much real work // remains), not of uNullDepth at all. Bucket both depths // separately: uNullDepth for the probe's own cost (cost1), uDepth // for the real alternative's cost (cost2) -- decoupling the two // cost models from any particular R formula. // // Ground truth (did this node *really* fail high) is read off the same // iBestScore-vs-iBeta comparison Search() already computes at its // "end:" label for the NODE_PV/NODE_CUT/NODE_ALL surprise counters just // above this block; we piggyback on that rather than duplicating it. // The diagnostic probe is a self-contained MakeMove(NULLMOVE) -> reduced // Search() -> UnmakeMove, deliberately *not* reusing TryNullmovePruning, // so its verification-search/extension side effects (meant only for a // probe whose result production actually trusts) never fire here. Like // any double-search diagnostic, it also warms the hash/history tables // along its own subtree before the real move loop runs at the same // node -- a known, unavoidable side effect of measuring this way. // // This roughly doubles node cost at every non-PV node under TEST_NULL, // so it's a diagnostic-only build flag (gmake TEST_NULL=1 ...), never // part of the normal GENETIC=1 PERF_COUNTERS=1 MP=1 SIXTYFOUR=1 profile, // and should only be run against a calibration corpus at a shallow // fixed depth, not self-play or the full engine pools. // // Buckets are a mixed-radix index over five dimensions: // // index = nullDepthB * (NC_DEPTH_BUCKETS*NC_DEFICIT_BUCKETS*NC_MATERIAL_BUCKETS*NC_MATERIAL_BUCKETS) // + outerDepthB * (NC_DEFICIT_BUCKETS*NC_MATERIAL_BUCKETS*NC_MATERIAL_BUCKETS) // + deficitB * (NC_MATERIAL_BUCKETS*NC_MATERIAL_BUCKETS) // + maxMaterialB* (NC_MATERIAL_BUCKETS) // + moverMaterialB // // root.c's dump loop decodes this same layout when printing results. // static ULONG _NullCalibDepthBucket(ULONG uSomeDepth) // generic: used for both uNullDepth and uDepth { ULONG uPlies = uSomeDepth / ONE_PLY; if (uPlies >= NC_DEPTH_BUCKETS - 1) return(NC_DEPTH_BUCKETS - 1); // 16+ return(uPlies); } static ULONG _NullCalibDeficitBucket(SCORE iDeficit) // iEval - iBeta { if (iDeficit < -300) return(0); if (iDeficit < -100) return(1); if (iDeficit < 0) return(2); if (iDeficit < 100) return(3); if (iDeficit < 300) return(4); return(5); } static ULONG _NullCalibMaterialBucket(ULONG uPiecesPerSide) // generic: used for both MAX(both) and mover-only { if (uPiecesPerSide <= 1) return(0); if (uPiecesPerSide == 2) return(1); if (uPiecesPerSide <= 5) return(2); return(3); } static ULONG _NullCalibBucketIndex(ULONG uNullDepth, // probe's own post-reduction depth (cost1 axis) ULONG uOuterDepth, // real node's pre-reduction depth (cost2 axis) SCORE iDeficit, ULONG uMaxPiecesPerSide, // MAX(white,black) ULONG uMoverPiecesPerSide) // TotalNonPawnCount(pos, pos->uToMove) { ULONG uNullDepthB = _NullCalibDepthBucket(uNullDepth); ULONG uOuterDepthB = _NullCalibDepthBucket(uOuterDepth); ULONG uDeficitB = _NullCalibDeficitBucket(iDeficit); ULONG uMaxMaterialB = _NullCalibMaterialBucket(uMaxPiecesPerSide); ULONG uMoverMaterialB = _NullCalibMaterialBucket(uMoverPiecesPerSide); ULONG uIndex = uNullDepthB; uIndex = uIndex * NC_DEPTH_BUCKETS + uOuterDepthB; uIndex = uIndex * NC_DEFICIT_BUCKETS + uDeficitB; uIndex = uIndex * NC_MATERIAL_BUCKETS + uMaxMaterialB; uIndex = uIndex * NC_MATERIAL_BUCKETS + uMoverMaterialB; ASSERT(uIndex < NC_TOTAL_BUCKETS); return(uIndex); } #endif #ifdef DEBUG #define VERIFY_HASH_HIT \ ASSERT(IS_VALID_SCORE(iScore)); \ ASSERT(((ULONG)sHash.uDepth << 4) >= uDepth); \ switch (sHash.bvFlags & HASH_FLAG_VALID_BOUNDS) \ { \ case HASH_FLAG_LOWER: \ ASSERT(iScore >= iBeta); \ ASSERT(iScore > -NMATE); \ ASSERT(iScore <= +NMATE); \ break; \ case HASH_FLAG_UPPER: \ ASSERT(iScore <= iAlpha); \ ASSERT(iScore < +NMATE); \ ASSERT(iScore >= -NMATE); \ break; \ case HASH_FLAG_EXACT: \ ASSERT((-NMATE <= iScore) && \ (iScore <= +NMATE)); \ break; \ default: \ ASSERT(FALSE); \ } #else #define VERIFY_HASH_HIT #endif /** Routine description: This is the full-width portion of the main chess tree search. In general, its job is to ask the move generator to make a list of all the moves possible at the board position in ctx, to make each move in turn, and to search each resulting position recursively. Parameters: SEARCHER_THREAD_CONTEXT *ctx : the context to search in SCORE iAlpha : the lower bound of the interesting score window SCORE iBeta : the upper bound of the interesting score window ULONG uDepth : the depth remaining before QSearch is invoked Return value: SCORE : a score Also affects the transposition table, searcher context, and just about every other large data structure in the engine... **/ SCORE FASTCALL Search(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta, IN ULONG uDepth) { POSITION *pos = &ctx->sPosition; PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; #ifdef DEBUG ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); ASSERT(ctx->uPly > 0); memcpy(&pi->sPosition, pos, sizeof(POSITION)); #endif CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; ASSERT(IS_VALID_FLAG(pf->fAvoidNullmove)); ASSERT(IS_VALID_FLAG(pf->fVerifyNullmove)); // Jump directly to Qsearch if remaining depth is low enough. // This is the only place Qsearch is entered. Lowered from ONE_PLY to // THREE_QUARTERS_PLY to match the check extension's new flat amount // (searchsup.c's ComputeMoveExtension) -- a lone check (or short run // of them) still buys exactly one extra full-width ply as before, but // a long unbroken chain now pays QUARTER_PLY of real cost per check // instead of extending for free. root.c compensates by trimming the // same QUARTER_PLY off the per-iteration depth budget so this doesn't // just add a blanket 1/4 ply to every search. SCORE iBestScore; if (uDepth < THREE_QUARTERS_PLY) { pf->fCouldStandPat[BLACK] = pf->fCouldStandPat[WHITE] = FALSE; pf->uQsearchNodes = pf->uQsearchDepth = 0; pf->uQsearchCheckDepth = QPLIES_OF_NON_CAPTURE_CHECKS; pi->fInQsearch = TRUE; iBestScore = QSearch(ctx, iAlpha, iBeta); ASSERT(pf->uQsearchNodes < 20000); ASSERT(pf->uQsearchDepth == 0); goto end; } pi->fInQsearch = FALSE; iBestScore = -INFINITY_SCORE; MOVE mvLast = (pi-1)->mv; ASSERT((mvLast.uMove != 0) || (pf->fAvoidNullmove == TRUE)); SCORE iInitialAlpha = iAlpha; SCORE iEval; MOVE mv, mvBest, mvHash; ULONG x = 0; SCORE iScore; INT iPositionalExtend = 0; INT iExtend; ULONG uNextDepth; ULONG uNullR; ULONG uLegalMoves = 0; FLAG fIsLeftoverMove = FALSE; // Stamped once below, right after this node's own Eval() call and // before any MakeMove in the move loop changes pos's live // signature out from under it -- see EstimateHangingMaterialCp's // comment (above _CMEvidenceBucket) for why this matters: bbMinor // Attacks/bbRookAttacks are only trustworthy when they were // written by a full, non-lazy Eval() call for THIS exact position. FLAG fParentAttackTablesAreFresh; // 2026-09-28: snapshotted into LOCAL (stack) storage at the same // point fParentAttackTablesAreFresh is captured -- pos->bbMinor // Attacks/bbRookAttacks themselves are NOT safe to read later in // the move loop, because every recursive Search() call made while // trying an earlier sibling move also calls Eval() on ITS OWN // position, overwriting these same shared pos-> fields, and // UnmakeMove does not restore them (they're eval scratch space, // not real position state -- unlike u64NonPawnSig/u64PawnSig, // which UnmakeMove DOES restore, which is exactly why the // signature check above kept reporting "fresh" long after the // underlying bitboards had been clobbered by a completely // unrelated node deep in an earlier sibling's subtree). Confirmed // empirically: every single real fail-high sampled in the queen- // attacked-by-rook bucket turned out to have NO actual rook // attacking the destination square once checked by hand -- this // is why. Local copies can't be touched by recursion. BITBOARD bbMinorAttacksSnapshot[2]; BITBOARD bbRookAttacksSnapshot[2]; // 2026-09-30: single shared "would we ever consider pruning or // reducing this move" eligibility gate -- the unified gate EFP and // LMR both consult now (formerly two separately-coded, slightly // different checklists), plus the losing-capture admission rule // the FH-table work has been testing (the old, separate gates // excluded ALL captures/promotions unconditionally; this // deliberately admits losing ones, via the SEE sign generate.c // already cached on the move, matching the population the joint // table was actually trained on -- see lmr_testing/SPEC.md's // "gate-1" section). Computed ONCE per move, unconditionally (not // just under PERF_COUNTERS -- it now gates live search behavior in // every build profile), so a move that should never actually be // pruned or reduced (a check, a check-escape, a PV node, an // already-extended move, a node-wide threat, a mate-magnitude // alpha) is excluded up front rather than patched around // downstream. Note this deliberately does NOT include LMR's old // uLegalMoves > 5 floor -- that requirement is dropped as part of // unifying onto this gate, per direct instruction, since it was // LMR-specific rather than part of the shared "unremarkable move" // definition gate-1 describes. FLAG fMoveIsPruneReduceEligible = FALSE; ULONG uRawDepthB; #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION FLAG fThisMoveIsCountermoveMatch = FALSE; ULONG uCMEvidenceBucket = 0; #endif #ifdef PERF_COUNTERS ULONG uThisMoveHangBucket = 0; ULONG uThisMoveGapBucket = 0; ULONG uThisMoveNumBucket = 0; ULONG uThisMoveDepthBucket = 0; // 2026-09-28: which joint-extra-reduction tier (0 == none, the // GetLMRReduction baseline only) fired for THIS move, if any -- // stashed at decision time (LMR call site) and consulted again // later, at the re-search-on-fail-high check, purely for the // calibration counters below. Never influences search behavior by // itself. ULONG uThisMoveJointExtraTier = 0; FLAG fThisMoveJointExtraEligible = FALSE; #endif HASH_ENTRY sHash; FLAG fHashHit; FLAG fThreat; FLAG fSkipNull; FLAG fIsDraw; ULONG uStage = TRY_HASH_MOVE; ULONG u; FLAG fTryEFPHere = FALSE; FLAG fThisMoveEFPPruned; FLAG fThisMoveLMPPruned; SCORE iMoveSee; #ifdef TEST_NULL FLAG fNullCalibEligible = FALSE; FLAG fNullCalibProbeFH = FALSE; ULONG uNullCalibBucket = 0; UINT64 uNullCalibProbeNodeCost = 0; UINT64 uNullCalibFirstMoveNodeCost = 0; UINT64 uNullCalibRealLoopNodeCost = 0; UINT64 uNullCalibNodesBeforeRealLoop = 0; #endif mvBest.uMove = 0; // Common initialization code (which may cause a cutoff or change the // bounds or decide that we need to stop searching now). if (TRUE == CommonSearchInit(ctx, &iAlpha, &iBeta, &iBestScore)) { goto end; } DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta); pi->eMoveScoringScheme = MOVE_SCORING_NORMAL; ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) || (!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck))); // Prepare next depth for nullmove and hashtable lookup uNullR = SelectNullmoveRFactor(ctx, uDepth); uNextDepth = uDepth - uNullR - ONE_PLY; if (uNextDepth > MAX_DEPTH_PER_SEARCH) uNextDepth = 0; // Check the transposition table. This may give us a cutoff // without doing any work if we have previously stored the score // of this position in the hash. It also may set mvHash even if // it can't give us a cutoff. It also may set fSkipNull (see // below) based on uNextDepth to inform us that a nullmove search // is unlikely to succeed here. mvHash.uMove = 0; fHashHit = HashLookup(ctx, uDepth, uNextDepth, iAlpha, iBeta, &fThreat, &fSkipNull, &mvHash, &iScore, &sHash); if (TRUE == fHashHit) { VERIFY_HASH_HIT; u = sHash.bvFlags & HASH_FLAG_VALID_BOUNDS; if (0 != mvHash.uMove) { // This is an idea posted by Dieter Brusser on CCC: If we // get a hash hit that leads to a draw then only accept it // if it has a score of zero, allows us to fail high when // a draw would also have allowed a fail high, or allows a // fail low when a draw would also have allowed a failed // low. VERIFY(MakeMove(ctx, mvHash)); fIsDraw = IsDraw(ctx); UnmakeMove(ctx, mvHash); if ((FALSE == fIsDraw) || (iScore == g_iDrawScore[pos->uToMove]) || ((u == HASH_FLAG_LOWER) && (iScore >= iBeta) && (g_iDrawScore[pos->uToMove] >= iBeta)) || ((u == HASH_FLAG_UPPER) && (iScore <= iAlpha) && (g_iDrawScore[pos->uToMove] <= iAlpha))) { // If the hash move leads to a draw, the score actually // produced by playing it is g_iDrawScore[pos->uToMove] // (from the mover's point of view), not the stale iScore // recorded along whatever non-repeating path originally // stored this entry -- the checks above only established // that the draw score clears the same bound iScore does, // not that iScore itself is an accurate value to return. SCORE iRetScore = fIsDraw ? g_iDrawScore[pos->uToMove] : iScore; if ((iAlpha < iRetScore) && (iRetScore < iBeta)) { UpdatePV(ctx, HASHMOVE); } iBestScore = iRetScore; goto end; } } else { // The hash move is empty. Either this is an upper bound // in which case we have no best move since the node that // generated it was a fail low -or- this is a lower bound // recorded after a null move search. In the latter case // we only accept the cutoff if we are considering null // moves at this node too. ASSERT(u != HASH_FLAG_EXACT); if ((HASH_FLAG_UPPER == u) || (FALSE == pf->fAvoidNullmove)) { ASSERT(((u == HASH_FLAG_UPPER) && (iScore <= iAlpha)) || ((u == HASH_FLAG_LOWER) && (iScore >= iBeta))); iBestScore = iScore; goto end; } } } // Probe interior node recognizers; allow probes of ondisk EGTB files // if we're shallow (near the root, where a first-touch mmap()/disk // read is affordable) -- always probe there -- *or*, deeper, only // if this exact position's lookup is likely resident (mincore()- // gated for 6-man material; a handful of popcounts and one atomic // load for 3-5 man -- see probe.c's EgtbProbeLikelyResident and // CLAUDE.md). That residency check itself is deferred into // RecognLookup (EGTB_PROBE_IF_RESIDENT), not computed here, so it's // skipped entirely at any node a cheap interior recognizer already // resolves -- see RecognLookup's own header comment. switch(RecognLookup(ctx, &iScore, (ctx->uPly <= (g_uIterateDepth / 2)) ? EGTB_PROBE_ALWAYS : EGTB_PROBE_IF_RESIDENT)) { case UNRECOGNIZED: break; case RECOGN_EXACT: if ((iAlpha < iScore) && (iScore < iBeta)) { UpdatePV(ctx, RECOGNMOVE); } iBestScore = iScore; goto end; case RECOGN_EGTB: if ((iAlpha < iScore) && (iScore < iBeta)) { UpdatePV(ctx, EGTBMOVE); } iBestScore = iScore; goto end; case RECOGN_LOWER: if (iScore >= iBeta) { iBestScore = iScore; goto end; } break; case RECOGN_UPPER: if (iScore <= iAlpha) { iBestScore = iScore; goto end; } break; #ifdef DEBUG default: ASSERT(FALSE); #endif } // Maybe do nullmove pruning pi->iEval = iEval = Eval(ctx, iAlpha, iBeta, &(pi->iPositional)); SCORE iImprovement = 0; if (ctx->uPly > 1) { iImprovement = (iEval - ctx->sPlyInfo[ctx->uPly - 2].iEval); } // If the Eval call above was a full eval (i.e. not lazy or super // lazy), there are usable attack bitboards. We'll consult them // below to determine if moves likely lose material but grab this // NOW, before any MakeMoves or recursion. fParentAttackTablesAreFresh = (pi->u64FullEvalSig == (pos->u64NonPawnSig ^ pos->u64PawnSig)); if (TRUE == fParentAttackTablesAreFresh) { bbMinorAttacksSnapshot[WHITE] = pos->bbMinorAttacks[WHITE]; bbMinorAttacksSnapshot[BLACK] = pos->bbMinorAttacks[BLACK]; bbRookAttacksSnapshot[WHITE] = pos->bbRookAttacks[WHITE]; bbRookAttacksSnapshot[BLACK] = pos->bbRookAttacks[BLACK]; } else { bbMinorAttacksSnapshot[WHITE] = bbMinorAttacksSnapshot[BLACK] = 0; bbRookAttacksSnapshot[WHITE] = bbRookAttacksSnapshot[BLACK] = 0; } GENERATE_NO_MOVES; #ifdef TEST_NULL // See _NullCalibBucketIndex's comment above for the full design. // Structural eligibility only -- deliberately does *not* consult // fSkipNull/fThreat/WeShouldTryNullmovePruning's margin table or // material threshold, since those are exactly the heuristics this // harness exists to evaluate. Note: like any double-search // diagnostic, this probe's recursive Search() call warms the hash // and history/countermove tables along its own subtree before the // real move loop below runs at this same node -- a known, // unavoidable side effect of measuring this way, not a bug. // // MUST run after GENERATE_NO_MOVES, not before: that macro is what // sets ctx->sMoveStack.uBegin[ctx->uPly+1] (from uEnd[ctx->uPly]), // and recursing into ctx->uPly+1 before it runs uses a stale // leftover index from whatever unrelated node last occupied that // ply slot -- crashed hard (MVF_MOVE_SEARCHED-already-set asserts, // corrupting a real, in-flight move a few frames up) the first time // this was tried with the block placed above GENERATE_NO_MOVES. fNullCalibEligible = ((FALSE == pf->fAvoidNullmove) && (FALSE == pi->fInCheck) && (iBeta != +INFINITY_SCORE) && (NODE_PV != pi->eNodeType) && (FALSE == fThreat) && (FALSE == fSkipNull)); if (fNullCalibEligible) { ULONG uMaxPiecesPerSide = MAXU(TotalNonPawnCount(pos, WHITE), TotalNonPawnCount(pos, BLACK)); ULONG uMoverPiecesPerSide = TotalNonPawnCount(pos, pos->uToMove); SCORE iNullCalibScore; UINT64 u64NodesBefore; uNullCalibBucket = _NullCalibBucketIndex(uNextDepth, uDepth, (SCORE)(iEval - iBeta), uMaxPiecesPerSide, uMoverPiecesPerSide); VERIFY(MakeMove(ctx, NULLMOVE)); pf->fAvoidNullmove = TRUE; u64NodesBefore = ctx->sCounters.tree.u64TotalNodeCount; iNullCalibScore = -Search(ctx, -iBeta, -iBeta + 1, uNextDepth); uNullCalibProbeNodeCost = ctx->sCounters.tree.u64TotalNodeCount - u64NodesBefore; pf->fAvoidNullmove = FALSE; UnmakeMove(ctx, NULLMOVE); if (!WE_SHOULD_STOP_SEARCHING) { // Direct increments, not INC() -- these calibration counters // must not depend on PERF_COUNTERS also being defined; a // TEST_NULL=1 build without PERF_COUNTERS=1 would otherwise // silently collect nothing (INC() is a no-op without it). fNullCalibProbeFH = (iNullCalibScore >= iBeta); ctx->sCounters.tree.u64NCAttempts[uNullCalibBucket]++; ctx->sCounters.tree.u64NCNullProbeNodeSum[uNullCalibBucket] += uNullCalibProbeNodeCost; if (fNullCalibProbeFH) { ctx->sCounters.tree.u64NCNullFH[uNullCalibBucket]++; } } else { fNullCalibEligible = FALSE; // don't commit ground truth either } // Snapshot right here, before production's own null-move logic // and the real move loop below -- the delta read at "end:" is // the true total cost of however this node actually gets // resolved from this point on (whether that's production's own // separate null success, one real move, or several). if (fNullCalibEligible) { uNullCalibNodesBeforeRealLoop = ctx->sCounters.tree.u64TotalNodeCount; } } #endif if (!fSkipNull && !fThreat && WeShouldTryNullmovePruning(ctx, iAlpha, iBeta, iEval, iImprovement, uNextDepth)) { ULONG uNullRBucket = uNullR / ONE_PLY; if (uNullRBucket >= NULL_R_BUCKETS) { uNullRBucket = NULL_R_BUCKETS - 1; } #ifdef PERF_COUNTERS INC(ctx->sCounters.tree.u64NullMoveTriesByR[uNullRBucket]); #endif if (TryNullmovePruning(ctx, &fThreat, iAlpha, iBeta, uNextDepth, &iPositionalExtend, &iScore, uNullRBucket)) { if (iScore > iBeta) { StoreLowerBound(mvHash, pos, iScore, uDepth, FALSE); } iBestScore = iScore; goto end; } } // Maybe increment positional extension level b/c of nullmove search // or hash table results. if (fThreat) { iPositionalExtend += HALF_PLY; INC(ctx->sCounters.extension.uMateThreat); } // Main search loop, try moves under this position. Before we get // into the move loop, save the extensions merited by this // position in the tree (pre-move) and the original search flags. // Also clear the avoid null bit in the search flags -- we were // either told to avoid it or not but there is no need to avoid it // for the rest of the line... pf->fAvoidNullmove = FALSE; do { ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); // Becase we want to try the hash move before generating any // moves (in case it fails high and we can avoid the work) we // have this ugly crazy looking switch statement... switch(uStage) { case TRY_HASH_MOVE: uStage++; x = 0; ASSERT(iBestScore == -INFINITY_SCORE); ASSERT(uLegalMoves == 0); if (mvHash.uMove != 0) { mv = mvHash; break; } // else fall through case GENERATE_MOVES: ASSERT(ctx->uPly > 0); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); x = ctx->sMoveStack.uBegin[ctx->uPly]; uStage++; if (IS_CHECKING_MOVE(mvLast)) { ASSERT(InCheck(pos, pos->uToMove)); GenerateMoves(ctx, mvHash, GENERATE_ESCAPES); if (MOVE_COUNT(ctx, ctx->uPly)) { // TODO: Experiment with removing these extensions. #if 0 if (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1) { iPositionalExtend += QUARTER_PLY; INC(ctx->sCounters.extension.uMultiCheck); } else if (NUM_KING_MOVES(ctx, ctx->uPly) == 0) { iPositionalExtend += QUARTER_PLY; INC(ctx->sCounters.extension.uNoLegalKingMoves); } #endif if (ONE_LEGAL_MOVE(ctx, ctx->uPly) && CountKingSafetyDefects(pos, pos->uToMove) > 2) { iPositionalExtend += HALF_PLY; INC(ctx->sCounters.extension.uOneLegalMove); } } } else { ASSERT(!InCheck(pos, pos->uToMove)); GenerateMoves(ctx, mvHash, GENERATE_ALL_MOVES); } // The threat/multi-check/no-legal-king-move bonuses above // are independent and can stack past ONE_PLY; clamp the // combined per-position extension to what the rest of the // code (e.g. split.c's HelpSearch) assumes is the max for // a single node. iPositionalExtend = MIN(iPositionalExtend, ONE_PLY); // fall through case PREPARE_TO_TRY_MOVES: ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]); ASSERT((uLegalMoves == 0) || ((uLegalMoves == 1) && (mvHash.uMove))); #ifdef DO_IID if (MOVE_COUNT(ctx, ctx->uPly)) { SelectBestNoHistory(ctx, x); // EXPERIMENT: If we got no best move from the // hash table and the best move we got from the // generator looks crappy (i.e. is not a winning // or even capture/promotion, AND not a killer -- // a killer move already proved itself elsewhere in // the tree, unlike an untested quiet move, so it // doesn't need IID's help) then rescore the moves // we generated at this ply using a shallower // search. "Internal Iterative Deepening" or // something like it. if ((NODE_PV == pi->eNodeType) && (mvHash.uMove == 0) && (ctx->sMoveStack.mvf[x].iValue < SORT_THESE_FIRST) && (0 == (ctx->sMoveStack.mvf[x].iValue & (FIRST_KILLER | SECOND_KILLER | THIRD_KILLER | FOURTH_KILLER))) && (uDepth >= FOUR_PLY)) { ASSERT(uDepth >= (IID_R_FACTOR + ONE_PLY)); ASSERT(ctx->sSearchFlags.fAvoidNullmove == FALSE); ctx->sSearchFlags.fAvoidNullmove = TRUE; RescoreMovesViaSearch(ctx, uDepth, iAlpha, iBeta); ctx->sSearchFlags.fAvoidNullmove = FALSE; } } #endif // Decide whether to do EFP; see below. ASSERT(FALSE == fTryEFPHere); if ((iEval < iAlpha) && (pi->eNodeType != NODE_PV) && (ctx->uPly >= 2) && (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0)) { fTryEFPHere = TRUE; } uStage++; uRawDepthB = DepthBucket(uDepth / ONE_PLY); ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]); // fall through case TRY_GENERATED_MOVES: if (x < ctx->sMoveStack.uEnd[ctx->uPly]) { ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]); #ifdef PERF_COUNTERS // Reset every iteration, BEFORE the LMR decision // block (below) can set it for this move -- without // this, a move that skips the extra-reduction // branch entirely (e.g. GetLMRReduction's own // baseline didn't fire) would silently inherit and // re-report a PRIOR move's stale tier at the // re-search-check site later in this same // iteration... except stale across ITERATIONS, not // within one -- this reset must happen before this // iteration's own LMR decision, not after. fThisMoveJointExtraEligible = FALSE; #endif // Always fully select the best remaining move, // regardless of tier -- retired the old // NumLeftoverMovesToSelect budget (a depth-indexed // cutoff on how many "leftover", i.e. sub-GOOD_MOVE, // moves were worth a full SelectBestWithHistory scan // before taking the remainder in whatever order it // sat in) once this session's evidence-calibration // work (see chess.h's COUNTERMOVE_EVIDENCE_THRESHOLD/ // FLEE_BONUS) showed the leftover pool has real, // findable signal -- countermove matches and // continuation-history-backed quiet moves both fail // high at rates well above the pool's average -- so // a bailout budget was discarding real information // for a node-count savings that didn't hold up // net-net once measured properly (solve counts and // leftover fail-high rates, not raw node counts, // which are too noisy on small suites to trust // alone). GOOD_MOVE itself is still meaningful here: // it's generate.c's own quality floor (below every // killer tier and SORT_THESE_FIRST's winning/even- // capture range), used below only to classify a // move as "leftover" for EFP eligibility and // instrumentation, not to gate how it's searched. // // On an IID-rescored ply, iValue is a real eval-axis // score (see RescoreMovesViaSearch/ComputeMoveScore) // -- GOOD_MOVE is meaningless on that axis, so this // never classifies an IID-rescored move as a // leftover (matches pre-retirement behavior). if (MOVE_SCORING_IID_RESCORED == pi->eMoveScoringScheme) { SelectBestNoHistory(ctx, x); // mv's score is search-based // WouldGiveCheck already computed in RescoreMovesViaSearch mv = ctx->sMoveStack.mvf[x].mv; } else { SelectBestWithHistory(ctx, x); mv = ctx->sMoveStack.mvf[x].mv; mv.bvFlags |= WouldGiveCheck(ctx, mv); ctx->sMoveStack.mvf[x].mv = mv; // re-store WouldGiveCheck's result fIsLeftoverMove = (ctx->sMoveStack.mvf[x].iValue < GOOD_MOVE); } #ifdef DEBUG ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED)); ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED; #endif #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION // Countermove evidence calibration -- ongoing check // that COUNTERMOVE_EVIDENCE_THRESHOLD (chess.h) is // still well-calibrated: log every countermove- // matched move tried, bucketed by its own // accumulated history+continuation evidence. fThisMoveIsCountermoveMatch = FALSE; if ((!IS_CAPTURE_OR_PROMOTION(mv)) && (ctx->uPly > 0) && (0 != (pi - 1)->mv.uMove) && (IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX((pi - 1)->mv)][0]) || IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX((pi - 1)->mv)][1]))) { ULONG uEvidence = g_HistoryCounters[mv.pMoved][mv.cTo] + g_ContinuationHistory[(MOVE_TO_CONT_KEY((pi - 1)->mv) * CONT_KEY_RANGE) + MOVE_TO_CONT_KEY(mv)]; fThisMoveIsCountermoveMatch = TRUE; uCMEvidenceBucket = _CMEvidenceBucket(uEvidence); } #endif // Note: x is the index of the NEXT move to be // considered, this move's index is (x-1). x++; break; } // else fall through default: goto no_more_moves; } ASSERT(mv.uMove); ASSERT(SanityCheckMove(pos, mv)); #ifdef MP // Can we search the remaining moves in parallel? Note: // uDepth can legitimately be < ONE_PLY here (fractional // depth from a reduction) -- uDepth/ONE_PLY - 1 would // underflow (ULONG) in that case, which is exactly why the // uDepth >= ONE_PLY check below short-circuits before the // g_fCanSplit[] indexing ever evaluates it. if (((uLegalMoves >= 2) && fIsLeftoverMove) && (0 != g_uNumHelpersAvailable) && (MOVE_SCORING_IID_RESCORED != pi->eMoveScoringScheme) && (FALSE == fTryEFPHere) && (uDepth >= ONE_PLY) && (TRUE == g_fCanSplit[uDepth / ONE_PLY - 1]) && (MOVE_COUNT(ctx, ctx->uPly) > 4)) { ASSERT(pf->fAvoidNullmove == FALSE); ASSERT(uStage == TRY_GENERATED_MOVES); ASSERT(x != 0); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); ASSERT(iBestScore <= iAlpha); ctx->sMoveStack.mvf[x-1].bvFlags &= ~MVF_MOVE_SEARCHED; iScore = StartParallelSearch(ctx, &iAlpha, iBeta, iImprovement, &iBestScore, &mvBest, (x - 1), iPositionalExtend, uDepth); ASSERT(iAlpha < iBeta); ASSERT((IS_SAME_MOVE(pi->PV[ctx->uPly], mvBest)) || (iScore <= iAlpha) || (iScore >= iBeta)); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); #ifdef DEBUG VerifyPositionConsistency(pos, FALSE); #endif if (IS_VALID_SCORE(iScore)) { pi->mvBest = mvBest; if (iBestScore >= iBeta) { // // The split failed high. StartParallelSearch leaves // iAlpha untouched on this path (see its own // comment), so falling through to no_more_moves' // generic iAlpha-moved classifier would misread // this as a fail-low/exact-score case -- skipping // UpdateDynamicMoveOrdering entirely and storing // the fail-high score as an (inverted-sense, // unsound) upper bound instead of a lower bound. // Handle it explicitly here instead, matching the // non-split fail-high branch above -- except for // uCurrent: mvBest may have been found by a helper // thread with its own separate ctx->sMoveStack, not // this (originating) thread's, so passing this // thread's own move index (the non-split call's // convention) doesn't identify mvBest's position in // any coherent move array. Pass 0 to skip the // "decrement history for moves tried earlier at // this node" loop entirely -- there's no single // thread-local move sequence to decrement across a // split, so it's dropped rather than fed a bogus // index (which previously tripped this exact // assert in dynamic.c: mvf[uCurrent] wasn't // mvBest). The killer/counter-move/history-increment // side of the update below is unaffected. // UpdateDynamicMoveOrdering(ctx, uDepth, mvBest, iBestScore, 0); StoreLowerBound(mvBest, pos, iBestScore, uDepth, fThreat); if (mvBest.pCaptured && !IS_PAWN(mvBest.pCaptured) && (iBeta < +NMATE)) { ASSERT(ctx->uPly > 0); RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, mvBest.cTo); } goto end; } goto no_more_moves; } else { ASSERT(WE_SHOULD_STOP_SEARCHING); iBestScore = iScore; goto end; } ASSERT(FALSE); } #endif // SEE must be computed on the PRE-move position -- see.c's // exchange walk needs the piece still sitting on cFrom. // ComputeMoveExtension uses it for two soundness gates: the // check extension (Crafty-style: don't extend a checking move // that's really just a losing sacrifice) and the recapture // extension (don't extend a "recapture" that actually loses // material). uDepth <= THREE_PLY mirrors the recapture // extension's own depth gate -- cheap to test here since // uDepth is already loop-invariant, and it keeps this from // computing a SEE on every single non-pawn capture at every // depth. One call per move regardless of which gate(s) end up // wanting it -- SEE is too hot a routine to pay for twice. iMoveSee = 0; if (IS_CHECKING_MOVE(mv) || (mv.pCaptured && !IS_PAWN(mv.pCaptured) && (uDepth <= THREE_PLY))) { iMoveSee = GetMoveSee(ctx, mv, (uStage == TRY_GENERATED_MOVES) ? (x - 1) : (ULONG)-1); } if (TRUE == MakeMove(ctx, mv)) { uLegalMoves++; ASSERT((IS_CHECKING_MOVE(mv) && InCheck(pos, pos->uToMove)) || (!IS_CHECKING_MOVE(mv) && !InCheck(pos, pos->uToMove))); // Compute per-move extension (as opposed to per-position // extensions which are represented by iPositionalExtend). iExtend = iPositionalExtend; ComputeMoveExtension(ctx, iAlpha, iBeta, (x - 1), // Note: x==0 if doing mvHash iEval, uDepth, iMoveSee, fIsLeftoverMove, &iExtend); ASSERT((uLegalMoves > 1) ? (x != 0) : TRUE); fMoveIsPruneReduceEligible = CanWeReduceOrPruneMove(ctx, mv, x, uLegalMoves, iExtend, iAlpha, fThreat, fIsLeftoverMove); fThisMoveLMPPruned = FALSE; fThisMoveEFPPruned = FALSE; if (TRUE == fMoveIsPruneReduceEligible) { // In here we consider: // - LMP (late move pruning), // - EFP (extended futility pruning), and // - LMR (late move reduction). // // All of these have their own conditions for firing but they // are based on dynamic signals about the move. Compute these // once, here, at the top instead of N times, below. // Dynamic move ordering FH attempt and FH/attempts: ULONG uFHAttempts = 0; ULONG uFHPctThousandths = GetMoveFailHighPctThousandths(mv, &uFHAttempts); // Our 4D prediction table, given: late, hang, // remaining depth, and gap to alpha will give us a // pessimistic FH% prediction for the move. Compute // the buckets needed to look it up. Note: depth // bucket is per-node and was already computed (once) // above. // The amount of material this move seems to hang. SCORE iHangCp = EstimateHangingMaterialCp(ctx, mv, (x - 1), bbMinorAttacksSnapshot, bbRookAttacksSnapshot); ULONG uRawDumbB = HangCpBucket(iHangCp); // Gap from iEval to current iAlpha bucket. ULONG uRawGapB = GapCpBucket((SCORE)(iAlpha - iEval)); // Late move number bucket. ULONG uRawLateB = MoveNumBucket(uLegalMoves); // Given the above signals, the (pessimistic) // predicted FH% of mv in thousandths of a percent. // i.e. 100 = 100/1000 = 0.1% (1/10th of a percent). // // A normal fIsLeftoverMove move has a FH% rate of // about 0.4% but this is misleading -- the population // is actually bimodal, split between moves near 0% // and moves legitimately much higher. // // uPredictedFH can also be 0xFFFF, a sentinel value // meaning "I don't know". This happens when there's // not enough data (never, anymore) or when the // buckets are noisy (e.g. "dumb" bucket 1 is crazy, // no signal). ULONG uPredictedFH = _JointTablePredictedFHThousandths( uRawDepthB, uRawDumbB, uRawGapB, uRawLateB); // Late move pruning; skip searching under this move? // Because this is a prune, we only do it when we are // extremely confident. That said, we do it at any // remaining depth. The more depth remaining the // better... fThisMoveLMPPruned = ShouldLatePrune( ctx, uDepth, uLegalMoves, uFHAttempts, uFHPctThousandths, uPredictedFH); // Extended futility pruning (EFP); this is an idea // proposed by Ernst Heinz (Scalable Search in // Computer Chess, papers). It only operates near the // horizon between search/qsearch and prunes moves // when we are far enough below alpha that we think // normal qsearch/lazy eval pruning will get this line // in 1-2 ply anyway. We have "enhanced" it in a // couple of ways: // - Using iHangCp so that moves that seem to lose // material (according to the SEE/IID/attack // tables in eval) are easier to prune. // - Allowing the uPredictFH (4D table signal) to // veto EFP when it thinks a quiet move actually // seems like it might FH here. if (TRUE == fTryEFPHere) { ASSERT(uDepth >= THREE_QUARTERS_PLY); // or we'd be in qsearch already SCORE iEstimatedMoveValue = (iEval + iImprovement - iHangCp); if (((uDepth <= ONE_PLY + THREE_QUARTERS_PLY) && (iEstimatedMoveValue + VALUE_KNIGHT <= iAlpha)) || ((uDepth > ONE_PLY + THREE_QUARTERS_PLY) && (uDepth <= TWO_PLY + THREE_QUARTERS_PLY) && (iEstimatedMoveValue + VALUE_ROOK <= iAlpha))) { fThisMoveEFPPruned = (uFHAttempts < EFP_FH_MIN_SAMPLES) || (uFHPctThousandths <= EFP_FH_PRUNE_THRESHOLD_PCT_THOUSANDTHS); fThisMoveEFPPruned = fThisMoveEFPPruned && (uPredictedFH == 0xFFFF || uPredictedFH < 300); #if 0 if (fThisMoveEFPPruned && uPredictedFH != 0xFFFF && uPredictedFH > 100) { // Which branch of EstimateHangingMaterialCp // actually produced iHangCp. Named exactly // by eMoveScoringScheme when mv is a // capture/promotion (the only case that // routes through ComputeMoveScore at all) -- // MOVE_SCORING_ESCAPE is the one to watch: // its capture formula is (mv.pCaptured) - // (mv.pMoved), with NO IS_KING(mv.pMoved) // guard the way EstimateHangingMaterialCp's // own non-capture path has (searchsup.c:300) // -- a king capturing the checking piece // (an ordinary, often-forced escape move) // subtracts VALUE_KING (INFINITY_SCORE) // as if it were real material, producing a // huge bogus "hang" estimate. const char *szHangSource; if (!IS_CAPTURE_OR_PROMOTION(mv)) { szHangSource = "quiet-move heuristic (pawn/king/minor/rook attack, or none)"; } else { switch (ctx->sPlyInfo[ctx->uPly - 1].eMoveScoringScheme) { case MOVE_SCORING_NORMAL: szHangSource = "MOVE_SCORING_NORMAL (SEE/tier)"; break; case MOVE_SCORING_ESCAPE: szHangSource = "MOVE_SCORING_ESCAPE (raw pCaptured-pMoved, no king guard)"; break; case MOVE_SCORING_QSEARCH_CHECKS: szHangSource = "MOVE_SCORING_QSEARCH_CHECKS (SEE/tier)"; break; case MOVE_SCORING_QSEARCH_NO_CHECKS: szHangSource = "MOVE_SCORING_QSEARCH_NO_CHECKS (SEE/tier)"; break; case MOVE_SCORING_IID_RESCORED: szHangSource = "MOVE_SCORING_IID_RESCORED (real searched score)"; break; default: szHangSource = "UNKNOWN eMoveScoringScheme"; break; } } Trace("Board _AFTER_ the move (%s):\n", MoveToIcs(mv)); DumpPosition(pos); Trace("iEval = %d\n", iEval); Trace("iAlpha = %d\n", iAlpha); Trace("iHangCp = %d (source: %s, pMoved=%d pCaptured=%d pPromoted=%d)\n", iHangCp, szHangSource, mv.pMoved, mv.pCaptured, mv.pPromoted); Trace("uGapBucket = %u\n", uRawGapB); Trace("uRawDepthB = %d\n", uRawDepthB); Trace("uRawDumbB = %d\n", uRawDumbB); Trace("uRawLateB = %d\n", uRawLateB); Trace("PREDICTED FH% = %u / 1000 %\n", uPredictedFH); Trace("HERE -- EFP says 'prune' be it looks dodgy?\n\n\n"); } #endif } } // If neither LMP nor EFP fired, we are going to search below // this move. But if the move is very late, we might reduce // the depth of the search a bit. LMR = late move reductions. // We never reduce a move such that it drops directly into // QSearch though; hence the TWO_PLY requirement below. if ((FALSE == fThisMoveLMPPruned) && (FALSE == fThisMoveEFPPruned) && (uDepth > TWO_PLY)) { ULONG uExtraTier = 0; INT iLMR = GetLMRReduction(ctx, uDepth, uLegalMoves, mv, iExtend, uFHAttempts, uFHPctThousandths, uPredictedFH, &uExtraTier); if (iLMR < 0) { ASSERT(iExtend == 0); iExtend = iLMR; #ifdef PERF_COUNTERS uThisMoveJointExtraTier = uExtraTier; fThisMoveJointExtraEligible = TRUE; INC(ctx->sCounters.tree.u64JointExtraTries[uExtraTier]); #endif } } } // LMP, EFP, LMR -- move pruning and reduction if ((TRUE == fThisMoveEFPPruned) || (TRUE == fThisMoveLMPPruned)) { #ifdef PERF_COUNTERS if (fThisMoveEFPPruned) { INC(ctx->sCounters.tree.u64EFPPruned); } else if (fThisMoveLMPPruned) { INC(ctx->sCounters.tree.u64LMPPruned); } #endif UnmakeMove(ctx, mv); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); continue; } #ifdef PERF_COUNTERS if (TRUE == fIsLeftoverMove) { INC(ctx->sCounters.tree.u64LeftoverTries); // 2026-09-28: gated on fPruneReduceEligible now, // not just fIsLeftoverMove -- excludes checks, // check-escapes, PV nodes, already-extended moves, // threat nodes, and mate-magnitude alpha up front, // matching HEAD's own EFP/LMR eligibility gates // (see that flag's declaration comment). Captures // and quiet moves both flow into the SAME buckets // again -- back to measuring the combined signal, // now with the contaminating populations removed // instead of split apart to isolate them. Computed // here (before UnmakeMove) and reused at the // FH-side increment below -- calling this again // after UnmakeMove would evaluate the WRONG // (restored, side-to-move-flipped-back) position. // 2026-10-03: this whole 4D-collection block is now // gated on FH_TABLE_COLLECTION rather than riding // along with PERF_COUNTERS. It is COLLECTION // instrumentation -- it exists to build // g_uJointFHThousandths, not to report on a normal // search -- and CLAUDE.md already says // FH_TABLE_COLLECTION is deliberately kept out of // the standard profile precisely because this // measurably costs nps. This block escaped that // gating. // // It is not a counter increment: it calls // EstimateHangingMaterialCp per eligible move, which // does real attack-bitboard work. It was also being // computed TWICE per move in any build that also had // a prune gate enabled, since that gate needs the // same hang bucket -- which inflated the candidate's // nps deficit in the PRUNE_LIVE self-play match // (-6.0% vs head) and made that match mildly unfair // to the candidate. #ifdef FH_TABLE_COLLECTION if (TRUE == fPruneReduceEligible) { SCORE iHangCp; INC(ctx->sCounters.tree.u64EligibleLeftoverTries); iHangCp = EstimateHangingMaterialCp( ctx, mv, x - 1, bbMinorAttacksSnapshot, bbRookAttacksSnapshot); uThisMoveHangBucket = HangCpBucket(iHangCp); INC(ctx->sCounters.tree.u64HangEstimateTries[uThisMoveHangBucket]); // "Down axis": how far below alpha is this // node's own static eval? Same eligibility // gate as the dumb axis -- iAlpha/iEval are // both plain node-local SCOREs (not shared, // mutable pos-> fields like bbRookAttacks // was), so no snapshot/staleness concern here. uThisMoveGapBucket = GapCpBucket( (SCORE)(iAlpha - iEval)); INC(ctx->sCounters.tree.u64GapEstimateTries[uThisMoveGapBucket]); // "Late axis": this move's own 1-based ordinal // position among moves actually tried here. uThisMoveNumBucket = MoveNumBucket(uLegalMoves); INC(ctx->sCounters.tree.u64MoveNumEstimateTries[uThisMoveNumBucket]); // "Depth axis": remaining search depth at // this node, before this move's own // extension/reduction. uThisMoveDepthBucket = DepthBucket(uDepth / ONE_PLY); INC(ctx->sCounters.tree.u64DepthEstimateTries[uThisMoveDepthBucket]); // Joint 4D cell, same four bucket indices, in // addition to (not instead of) the marginals // above -- keeps the marginals live this run as // a cheap cross-check that the joint reduces to // what we already understand. INC(ctx->sCounters.tree.u64JointTries [uThisMoveDepthBucket][uThisMoveHangBucket] [uThisMoveGapBucket][uThisMoveNumBucket]); } #endif } #endif // PERF_COUNTERS #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION // Deliberately its own gate, not nested under PERF_COUNTERS // above -- see MOI_INC/MOVE_ORDERING_EVIDENCE_COLLECTION // comment (chess.h). if (TRUE == fThisMoveIsCountermoveMatch) { MOI_INC(ctx->sCounters.tree.u64CMEvidenceTries[uCMEvidenceBucket]); } #endif // Record the extension/reduction actually applied to // THIS move, unconditionally -- not just when it's // negative. Leaving this stale from whatever earlier // move at this ply last happened to set it let a child // node checking "was my parent's move reduced" via // (pi-1)->iExtensionAmount < 0 read a leftover value // from a completely different sibling move, not the // one actually played. pi->iExtensionAmount = iExtend; // Compute the next search depth for this move/subtree. uNextDepth = uDepth - ONE_PLY + iExtend; if (uNextDepth >= MAX_DEPTH_PER_SEARCH) { uNextDepth = 0; } pf->iCumulativeExtend += iExtend; ASSERT(pf->fAvoidNullmove == FALSE); if (iBestScore == -INFINITY_SCORE) { // First move, full a..b window. ASSERT(uLegalMoves == 1); #ifdef TEST_NULL // Cost side of the null-move calibration harness' // try-vs-skip EV estimate: this is the "R=0" // alternative the null probe (see above) is being // weighed against -- the real first move's own // full-depth subtree cost. uLegalMoves==1 guarantees // this fires exactly once per node. if (fNullCalibEligible) { UINT64 u64NodesBeforeFirstMove = ctx->sCounters.tree.u64TotalNodeCount; iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); uNullCalibFirstMoveNodeCost = ctx->sCounters.tree.u64TotalNodeCount - u64NodesBeforeFirstMove; } else #endif iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); } else { // Moves 2..N, try a minimal window search iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uNextDepth); if ((iAlpha < iScore) && (iScore < iBeta)) { iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); } } // Research deeper if history pruning failed if ((iExtend < 0) && (iScore >= iBeta)) { #ifdef PERF_COUNTERS // Calibration for the joint-extra-reduction tiers // above: did the tier this move was assigned (0 == // GetLMRReduction's baseline only, 1-3 == extra // plies the table added) actually predict a // re-search here? If low-predicted-FH tiers show an // ELEVATED research rate rather than a lower one, // that's the distribution-shift failure this // project's history keeps producing, caught here // (a suite run) instead of in a self-play match. if (TRUE == fThisMoveJointExtraEligible) { INC(ctx->sCounters.tree.u64JointExtraResearch[uThisMoveJointExtraTier]); } #endif uNextDepth -= iExtend; // undo the full reduction, whatever its magnitude pi->iExtensionAmount = 0; iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); } #if defined(PERF_COUNTERS) && defined(JOINT_EXTRA_VERIFY) // "Silent miss" shadow verification -- only reachable // when the branch above did NOT fire, i.e. this move's // extra-reduced score was < beta and so triggered no // real re-search. Would removing just the EXTRA plies // (restoring the depth HEAD's own baseline -ONE_PLY // reduction alone would have used) have found a // fail-high we're about to silently miss? Full // coverage, every extra-reduced move that reaches here // -- see GNUmakefile's JOINT_EXTRA_VERIFY comment for // why this is calibration-only, never a normal build. else if ((TRUE == fThisMoveJointExtraEligible) && (uThisMoveJointExtraTier > 0)) { ULONG uShadowDepth = uNextDepth + (uThisMoveJointExtraTier * ONE_PLY); SCORE iShadowScore; #ifdef NEUTRALIZE_NULL_BAILOUT // 2026-09-29: searchsup.c's null-move "history- // reduced bailout" branch (Tord Romstad idea) reads // (pi-1)->iExtensionAmount -- OUR OWN reduction on // mv -- to decide whether to fabricate a "please // re-search me" placeholder score instead of a // real one. In a real move-loop search that's // correct: the fabricated score negates up to // exactly iBeta+1 one level up, which search.c's // own re-search-on-fail-high machinery correctly // interprets and acts on. Our shadow verification // is a bespoke one-off Search() call with no such // wrapper, so we'd misread that signal as a // genuinely-computed fail-high. Temporarily zero // OUR OWN pi->iExtensionAmount so this one specific // check can't fire for mv -- everything deeper in // the shadow subtree still goes through the normal // move loop (with its wrapper intact) if the same // mechanism legitimately fires there for some // other, unrelated reduced move. INT iSavedExtensionAmount = pi->iExtensionAmount; pi->iExtensionAmount = 0; #endif iShadowScore = -Search(ctx, -iBeta, -iAlpha, uShadowDepth); #ifdef NEUTRALIZE_NULL_BAILOUT pi->iExtensionAmount = iSavedExtensionAmount; #endif #ifdef SILENT_MISS_TRACE // UpdatePV is only ever called on the iScore > // iAlpha branch that does NOT also fail high // (search.c's main move loop) -- a beta cutoff // jumps straight to "end" without touching the PV // array at all, since a fail-high score is only a // lower bound, not a real line. Since our whole // diagnostic signal IS a fail-high (iShadowScore >= // iBeta), WalkPV would always come back empty here // -- not useful. What DOES get written on a cutoff // is the hash table (StoreLowerBound, just before // that same "end" jump), so walk a short hash // chain instead, the same side-effect-free idiom // FinishPVTailFromHash (util.c) already uses for // exactly this purpose. CHAR szShadowPV[SMALL_STRING_LEN_CHAR] = ""; { MOVE mvChain[8]; ULONG uChainLen = 0; MOVE mvNext; while ((uChainLen < 8) && (0 != (mvNext = GetPonderMove(pos)).uMove)) { strncat(szShadowPV, MoveToSan(mvNext, pos), ARRAY_LENGTH(szShadowPV) - strlen(szShadowPV) - 1); strncat(szShadowPV, " ", ARRAY_LENGTH(szShadowPV) - strlen(szShadowPV) - 1); mvChain[uChainLen++] = mvNext; if (FALSE == MakeMove(ctx, mvNext)) { uChainLen--; break; } } while (uChainLen > 0) { UnmakeMove(ctx, mvChain[--uChainLen]); } } #endif // EFP-tier-aligned bucket for the FULLY (base + // extra) reduced search's actual remaining depth -- // see _PostReduceDepthBucketEfpAligned's comment. ULONG uPostReduceDepthBucket = _PostReduceDepthBucketEfpAligned(uNextDepth); INC(ctx->sCounters.tree.u64JointExtraVerifyTries [uThisMoveJointExtraTier][uPostReduceDepthBucket]); if (iShadowScore >= iBeta) { INC(ctx->sCounters.tree.u64JointExtraVerifySilentMiss [uThisMoveJointExtraTier][uPostReduceDepthBucket]); if (iShadowScore == (iBeta + 1)) { INC(ctx->sCounters.tree.u64JointExtraVerifyNullBailoutSignature [uThisMoveJointExtraTier]); } #ifdef SILENT_MISS_TRACE // pos currently reflects the position AFTER mv // (MakeMove already ran earlier this // iteration, UnmakeMove hasn't run yet) -- // pi->sPosition (the pre-move parent) is // DEBUG-only, not available in a release // build, so print the POST-move FEN plus the // move in coordinate notation (MoveToIcs takes // just the move, no pre-move disambiguation // context needed) rather than SAN. Trace("SILENT_MISS_TRACE tier=%u bucket=%u " "uNextDepth=%lu uShadowDepth=%lu " "alpha=%d beta=%d " "realScore=%d shadowScore=%d " "move=%s postMoveFen=\"%s\" " "shadowRefutation=\"%s\"\n", uThisMoveJointExtraTier, uPostReduceDepthBucket, uNextDepth, uShadowDepth, iAlpha, iBeta, iScore, iShadowScore, MoveToIcs(mv), PositionToFen(pos), szShadowPV); #endif } } #endif #if defined(PERF_COUNTERS) && defined(PRUNE_VERIFY) // The audited move has now had its ordinary search. If // it failed high, the deep-prune gate would have thrown // away a move that actually raised beta -- a silent // miss, attributed to the band/depth the decision was // made in. The margin is accumulated so that // boundary-noise clears (a score that only just beats a // tight inherited PVS window, JOINT_EXTRA_VERIFY's // documented false-positive class) can be separated // from real misses afterwards rather than hand-traced. if (TRUE == fVerifyFlagged) { if (iScore >= iBeta) { INC(ctx->sCounters.tree.u64PruneVerifyFailHigh [uVerifyBand][uVerifyDepthB]); if (uVerifyBand <= 4) { INC(ctx->sCounters.tree.u64PruneVerifyDynMiss [uVerifyAttB][uVerifyRateB]); } ctx->sCounters.tree.u64PruneVerifyMarginSum [uVerifyBand][uVerifyDepthB] += (UINT64)(iScore - iBeta); #ifdef SILENT_MISS_TRACE // pos is the POST-move position here (UnmakeMove // has not run yet) -- same convention as the // JOINT_EXTRA_VERIFY trace above. // 2026-10-03: log the DYNAMIC signals alongside // the static prediction, so a real miss can be // interrogated for "what would have saved us, and // at what threshold". Motivated by the band-0 // miss at // 6k1/p4p1p/3p2q1/2p1rP2/2P3p1/P7/1P1Qn1PK/3R1R2, // Qg6 -- a move whose queen only LOOKS hung // (White is losing too badly to take it; best // line grabs the e2 knight and White is -14 at // depth 19), i.e. a genuine structural // mispredict of the dumbness axis, which no // amount of sampling conservatism in the static // table can catch. // // fhpct/fhatt: this exact move identity's own // observed rate and sample count // (GetMoveFailHighPctThousandths) -- answers // "what GetMoveFailHigh threshold would have // vetoed this". // cm: countermove-table level -- 0 none, 1 slot // 0 match, 2 slot 1 match, against the move // played two plies back (the index // generate.c's _ScoreAllMoves uses). // hist/cont: accumulated history and // continuation-history evidence for this // [piece][to]. // killer: 1 if this ply's killer, 2 if ply-3's. { ULONG uDynAtt = 0; ULONG uDynPct = GetMoveFailHighPctThousandths(mv, &uDynAtt); ULONG uCmLevel = 0; ULONG uHist = g_HistoryCounters[mv.pMoved][mv.cTo]; ULONG uKiller = 0; if (ctx->uPly >= 2) { MOVE mvPrev = ctx->sPlyInfo[ctx->uPly - 2].mv; if (0 != mvPrev.uMove) { ULONG uCi = MOVE_TO_INDEX(mvPrev); if (IS_SAME_MOVE(mv, ctx->mvCounter[uCi][0])) uCmLevel = 1; else if (IS_SAME_MOVE(mv, ctx->mvCounter[uCi][1])) uCmLevel = 2; } } if (IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0]) || IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) { uKiller = 1; } else if ((ctx->uPly >= 3) && (IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) || IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1]))) { uKiller = 2; } Trace("PRUNEMISS pred=%u band=%u depthb=%u " "alpha=%d beta=%d score=%d margin=%d " "fhpct=%u fhatt=%u cm=%u hist=%u killer=%u " "mv=%s postfen=%s\n", uVerifyPred, uVerifyBand, uVerifyDepthB, iAlpha, iBeta, iScore, (iScore - iBeta), uDynPct, uDynAtt, uCmLevel, uHist, uKiller, MoveToIcs(mv), PositionToFen(pos)); } #endif } } #endif UnmakeMove(ctx, mv); pf->iCumulativeExtend -= iExtend; ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); if (WE_SHOULD_STOP_SEARCHING) { iBestScore = iScore; goto end; } // Check results ASSERT(iBestScore <= iAlpha); ASSERT(iAlpha < iBeta); if (iScore > iBestScore) { iBestScore = iScore; mvBest = mv; pi->mvBest = mv; if (iScore > iAlpha) { if (iScore >= iBeta) { #ifdef PERF_COUNTERS if (TRUE == fIsLeftoverMove) { INC(ctx->sCounters.tree.u64LeftoverFH); // Gated on fPruneReduceEligible now, // matching the tries side -- must // match exactly, or this would reuse a // stale bucket left over from a // different (eligible) move for one // that never got a bucket computed // this iteration. if (TRUE == fMoveIsPruneReduceEligible) { INC(ctx->sCounters.tree.u64EligibleLeftoverFH); INC(ctx->sCounters.tree.u64HangEstimateFH[uThisMoveHangBucket]); INC(ctx->sCounters.tree.u64GapEstimateFH[uThisMoveGapBucket]); INC(ctx->sCounters.tree.u64MoveNumEstimateFH[uThisMoveNumBucket]); INC(ctx->sCounters.tree.u64DepthEstimateFH[uThisMoveDepthBucket]); INC(ctx->sCounters.tree.u64JointFH [uThisMoveDepthBucket][uThisMoveHangBucket] [uThisMoveGapBucket][uThisMoveNumBucket]); } } #endif // PERF_COUNTERS #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION if (TRUE == fThisMoveIsCountermoveMatch) { MOI_INC(ctx->sCounters.tree.u64CMEvidenceFH[uCMEvidenceBucket]); } #endif // Update history and killers list and store in // the transposition table. UpdateDynamicMoveOrdering(ctx, uDepth, mv, iScore, x); StoreLowerBound(mv, pos, iScore, uDepth, fThreat); // A fail-high capturing a non-pawn piece is // search-proven evidence that piece was en // prise -- but the victim belongs to the // *other* side, i.e. whoever is to move at // ctx->uPly - 1 (ply parity), not here -- // "despite the move you're about to make, // this piece stays in trouble." Skip near // mate: a fail-high there means the whole // subtree is winning regardless of this // particular piece, not that it was // specifically hanging. if (mv.pCaptured && !IS_PAWN(mv.pCaptured) && (iBeta < +NMATE)) { ASSERT(ctx->uPly > 0); RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, mv.cTo); } KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1); ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); goto end; } else { #ifdef PERF_COUNTERS if (TRUE == fIsLeftoverMove) { INC(ctx->sCounters.tree.u64LeftoverAlpha); } #endif // PV move... UpdatePV(ctx, mv); iAlpha = iScore; } } } } } while(1); // foreach move no_more_moves: ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); // Detect checkmates and stalemates if (0 == uLegalMoves) { if (pi->fInCheck) { ASSERT(IS_CHECKING_MOVE(mvLast)); ASSERT(InCheck(pos, pos->uToMove)); iBestScore = MATED_SCORE(ctx->uPly); if ((iAlpha < iBestScore) && (iBestScore < iBeta)) { INC(ctx->sCounters.tree.u64LeafCount); UpdatePV(ctx, MATEMOVE); } ASSERT(iBestScore <= -NMATE); goto end; } else { iBestScore = g_iDrawScore[pos->uToMove]; if ((iAlpha < iBestScore) && (iBestScore < iBeta)) { INC(ctx->sCounters.tree.u64LeafCount); UpdatePV(ctx, DRAWMOVE); } goto end; } } // Not checkmate/stalemate; store the result of this search in the // hash table. // Do not store exact hash scores for nodes where we pruned (EFP/LMP) // some moves. if (iAlpha != iInitialAlpha) { ASSERT(mvBest.uMove != 0); UpdateDynamicMoveOrdering(ctx, uDepth, mvBest, iBestScore, 0); StoreExactScore(mvBest, pos, iBestScore, uDepth, fThreat, ctx->uPly); } else { // IDEA: "I am very well aware of the fact, that the scores // you get back outside of the window, are not trustable at // all. Still, I have mentioned the case, of all scores being // losing mate scores, but one is not. This move will be good // to try first. I have seen this, by investigating multi MB // large tree dumps, so it is not only there in theory. Often, // even with fail soft, I of course will also get multiple // moves with the same score (alpha). But then one can see the // "best" move as an additional killer move. It was most // probably the killer move anyway, when this position was // visited the last time. I cannot see a reason, why trying // such a move early could hurt. And I do see reductions of // tree sizes. I don't try upper-bound moves first. I try them // (more or less) after the good captures, and together with // the killer moves, but before history moves." // --Ed Schroder StoreUpperBound(pos, iBestScore, uDepth, fThreat); } // else: fail-low (iAlpha == iInitialAlpha) AND fAnyMoveEFPPruned -- // no sound bound in either direction to store (the skipped move // could have raised the true value above iBestScore, so it's not a // valid upper bound; there's no mvBest to offer as a lower bound // either, since nothing beat alpha). Store nothing rather than // cache an unsound result. end: ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING); ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); #ifdef TEST_NULL // Commit the calibration record stashed at the diagnostic probe // site above, now that iBestScore's fate against iBeta (this // node's real, ground-truth fail-high outcome) is known. if (fNullCalibEligible && (!WE_SHOULD_STOP_SEARCHING) && IS_VALID_SCORE(iBestScore)) { // Direct increments -- see the probe site's comment on why // these can't use INC(). FLAG fRealFH = (iBestScore >= iBeta); if (fRealFH) { ctx->sCounters.tree.u64NCRealFH[uNullCalibBucket]++; if (fNullCalibProbeFH) { ctx->sCounters.tree.u64NCBothFH[uNullCalibBucket]++; } } else if (fNullCalibProbeFH) { // False positive: the null-move probe predicted a fail-high // that the real move loop didn't confirm -- exactly the // "null-move lie" case that a low-material verification // search exists to catch in production. Dump a capped // number of example FENs per bucket (same "capped FEN // sampler" idea as eval.c's MARGINSAFETY_EXCEEDED logging) // so these can be inspected by hand for genuine zugzwang // our TotalNonPawnCount safety net is missing, vs. ordinary // search noise. static ULONG uFalsePositiveFenSamples[NC_TOTAL_BUCKETS]; if (uFalsePositiveFenSamples[uNullCalibBucket] < 5) { CHAR *pszFen = PositionToFen(pos); if (NULL != pszFen) { uFalsePositiveFenSamples[uNullCalibBucket]++; Trace("NULLCALIB_FALSE_POSITIVE bucket=%lu depth=%lu " "fen=%s\n", uNullCalibBucket, uDepth, pszFen); SystemFreeMemory(pszFen); } } } ctx->sCounters.tree.u64NCFirstMoveNodeSum[uNullCalibBucket] += uNullCalibFirstMoveNodeCost; uNullCalibRealLoopNodeCost = ctx->sCounters.tree.u64TotalNodeCount - uNullCalibNodesBeforeRealLoop; ctx->sCounters.tree.u64NCRealLoopNodeSum[uNullCalibBucket] += uNullCalibRealLoopNodeCost; } #endif DTLeaveNode(ctx, FALSE, iBestScore, mvBest); return(iBestScore); } /** Routine description: This routine is called by QSearch, the select part of the recursive search code. Its job is to determine if a move generated is worth searching. Parameters: SEARCHER_THREAD_CONTEXT *ctx : searcher context ULONG uMoveNum : the move number we are considering SCORE iFutility : the futility line Return value: FLAG : TRUE if the move is worth considering, FALSE if it can be skipped **/ #ifdef CALIBRATE_QSEARCH_FUTILITY // 2026-09-08: measures whether _ShouldWeConsiderThisMove's futility // gates are set correctly, by -- at the moment a move would be // rejected -- actually searching it anyway (fully unpruned, via // ctx->fDiagUnprunedSubtree) and checking whether it would genuinely // have raised alpha. Never changes real search behavior: the // diagnostic re-search's result is used only to log a sample, then // discarded (same non-interference pattern as CALIBRATE_MARGIN_SAFETY // in eval.c). // // Bucketed by (gate, margin-neutral distance short of the relevant // threshold, piPositional bucket, which Eval() tier supplied // piPositional) so a single run answers several questions at once: // is the margin itself wide enough (distance-vs-surprise-rate curve // within a gate), does piPositional actually predict surprises // (compare curves across piPositional buckets at the same distance), // and does that answer differ by tier (super-lazy vs regular-lazy vs // full eval). #define QFUT_DIST_BUCKETS (6) #define QFUT_POS_BUCKETS (4) static UINT64 g_uQFutTries[QFUT_GATE_COUNT][QFUT_DIST_BUCKETS][QFUT_POS_BUCKETS][EVAL_POSITIONAL_SOURCE_COUNT]; static UINT64 g_uQFutSurprises[QFUT_GATE_COUNT][QFUT_DIST_BUCKETS][QFUT_POS_BUCKETS][EVAL_POSITIONAL_SOURCE_COUNT]; static ULONG _QFutDistanceBucket(IN SCORE iDistance) /* iDistance: how far short of the relevant threshold this move was (positive = short; a move that actually cleared the bar never gets here, so this should always be > 0, but negative/zero is folded into bucket 0 defensively rather than asserting -- a measurement harness should never crash a calibration run over its own bucketing edge case). */ { if (iDistance <= 25) return(0); if (iDistance <= 50) return(1); if (iDistance <= 100) return(2); if (iDistance <= 200) return(3); if (iDistance <= 400) return(4); return(5); } static ULONG _QFutPositionalBucket(IN SCORE iPositional) { if (iPositional < 0) return(0); if (iPositional < 25) return(1); if (iPositional < 75) return(2); return(3); } static void _QFutDiagnoseReject(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uMoveNum, IN SCORE iAlpha, IN SCORE iBeta, IN SCORE iPositional, IN ULONG uPositionalSource, IN ULONG uGate, IN SCORE iDistance, IN FLAG fGeneratedChecks) /** Routine description: A move is about to be rejected by one of _ShouldWeConsiderThisMove's futility gates. Before rejecting it for real, search it anyway (fully unpruned) to see whether it would actually have raised alpha, and log the outcome. The diagnostic search's result is discarded -- this function never changes what the caller does. Return value: void **/ { MOVE mv; SCORE iScore; ULONG uDistBucket, uPosBucket; // Never diagnose from inside an already-diagnostic (fully // unpruned) subtree -- structurally shouldn't happen anyway, since // nothing gets rejected while fDiagUnprunedSubtree is set, but // guard explicitly rather than relying on that. if (TRUE == ctx->fDiagUnprunedSubtree) { return; } ASSERT(uGate < QFUT_GATE_COUNT); ASSERT(uPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT); mv = ctx->sMoveStack.mvf[uMoveNum].mv; // Mirror QSearch's own move loop exactly: GenerateMoves only tags // MVF_CHECK/the checking-move bit when checks were actually being // generated this ply. Skipping this (as an earlier version of this // function did) leaves the flag unset on a move that objectively // does give check, which MakeMove/ply-info bookkeeping trusts // blindly -- the next ply's fInCheck-vs-InCheck() consistency // ASSERT (searchsup.c) catches the mismatch immediately. if (FALSE == fGeneratedChecks) { mv.bvFlags |= WouldGiveCheck(ctx, mv); } if (FALSE == MakeMove(ctx, mv)) { return; } ctx->fDiagUnprunedSubtree = TRUE; ctx->sSearchFlags.uQsearchDepth++; iScore = -QSearch(ctx, -iBeta, -iAlpha); ctx->sSearchFlags.uQsearchDepth--; ctx->fDiagUnprunedSubtree = FALSE; UnmakeMove(ctx, mv); uDistBucket = _QFutDistanceBucket(iDistance); uPosBucket = _QFutPositionalBucket(iPositional); g_uQFutTries[uGate][uDistBucket][uPosBucket][uPositionalSource]++; if (iScore > iAlpha) { g_uQFutSurprises[uGate][uDistBucket][uPosBucket][uPositionalSource]++; } } static CHAR *g_szQFutGateNames[QFUT_GATE_COUNT] = { "generic capture/promo", "checking capture/promo (VALUE_ROOK)", "quiet check (VALUE_BISHOP)", }; static CHAR *g_szQFutSourceNames[EVAL_POSITIONAL_SOURCE_COUNT] = { "full eval", "regular lazy", "super lazy", }; void DumpQSearchFutilityCalibration(void) /** Routine description: Print, per (gate, piPositional-source tier), the surprise rate (fraction of diagnostically-re-searched rejects that actually raised alpha) by distance-short-of-threshold bucket, and separately by piPositional bucket at the widest distance bucket -- read the former for "is this gate's margin wide enough," the latter (compared across piPositional buckets at a fixed distance) for "does piPositional actually predict surprises." Parameters: void Return value: void **/ { ULONG g, d, p, s; static CHAR *szDistLabel[QFUT_DIST_BUCKETS] = { "0-25", "25-50", "50-100", "100-200", "200-400", "400+" }; static CHAR *szPosLabel[QFUT_POS_BUCKETS] = { "<0", "0-25", "25-75", "75+" }; for (g = 0; g < QFUT_GATE_COUNT; g++) { Trace("QSearch futility gate: %s\n", g_szQFutGateNames[g]); for (s = 0; s < EVAL_POSITIONAL_SOURCE_COUNT; s++) { UINT64 u64TotalTries = 0; for (d = 0; d < QFUT_DIST_BUCKETS; d++) { for (p = 0; p < QFUT_POS_BUCKETS; p++) { u64TotalTries += g_uQFutTries[g][d][p][s]; } } if (0 == u64TotalTries) { continue; } Trace(" source=%s (n=%" COMPILER_LONGLONG_UNSIGNED_FORMAT "):\n", g_szQFutSourceNames[s], u64TotalTries); Trace(" by distance short of bar (summed over piPositional buckets):\n"); for (d = 0; d < QFUT_DIST_BUCKETS; d++) { UINT64 u64Tries = 0, u64Surprises = 0; for (p = 0; p < QFUT_POS_BUCKETS; p++) { u64Tries += g_uQFutTries[g][d][p][s]; u64Surprises += g_uQFutSurprises[g][d][p][s]; } if (0 == u64Tries) { continue; } Trace(" dist %8s: %6.2f%% surprise rate (n=%" COMPILER_LONGLONG_UNSIGNED_FORMAT ")\n", szDistLabel[d], 100.0 * (double)u64Surprises / (double)u64Tries, u64Tries); } Trace(" by piPositional bucket (summed over distance buckets):\n"); for (p = 0; p < QFUT_POS_BUCKETS; p++) { UINT64 u64Tries = 0, u64Surprises = 0; for (d = 0; d < QFUT_DIST_BUCKETS; d++) { u64Tries += g_uQFutTries[g][d][p][s]; u64Surprises += g_uQFutSurprises[g][d][p][s]; } if (0 == u64Tries) { continue; } Trace(" pos %6s: %6.2f%% surprise rate (n=%" COMPILER_LONGLONG_UNSIGNED_FORMAT ")\n", szPosLabel[p], 100.0 * (double)u64Surprises / (double)u64Tries, u64Tries); } // The marginals above can each look flat on their own even // when piPositional genuinely matters (its effect might // only show up at a fixed distance) -- this is the actual // Q2 answer: read a single distance row across columns. If // the percentages don't move across piPositional buckets // at a fixed distance, it isn't predictive; if they fall // as piPositional rises, it is. Trace(" cross-tab, surprise%% (rows=distance, cols=piPositional " "%s/%s/%s/%s):\n", szPosLabel[0], szPosLabel[1], szPosLabel[2], szPosLabel[3]); for (d = 0; d < QFUT_DIST_BUCKETS; d++) { UINT64 u64RowTries = 0; for (p = 0; p < QFUT_POS_BUCKETS; p++) { u64RowTries += g_uQFutTries[g][d][p][s]; } if (0 == u64RowTries) { continue; } Trace(" dist %8s:", szDistLabel[d]); for (p = 0; p < QFUT_POS_BUCKETS; p++) { UINT64 u64Tries = g_uQFutTries[g][d][p][s]; if (0 == u64Tries) { Trace(" n/a "); } else { Trace(" %5.1f%% (n=%5" COMPILER_LONGLONG_UNSIGNED_FORMAT ")", 100.0 * (double)g_uQFutSurprises[g][d][p][s] / (double)u64Tries, u64Tries); } } Trace("\n"); } } } } #endif // CALIBRATE_QSEARCH_FUTILITY // Flat bonus added to a checking capture/promotion's own (real, // winning/even) iMoveValue before comparing against iFutility -- // replaces the retired VALUE_ROOK position-level cutoff for exactly // this population (see _ShouldWeConsiderThisMove's comment at its use // site for why). Provisional -- no calibration data yet for this // specific split; re-measure with `calibrate qsearchfutility`. #define CHECK_BONUS (150) static FLAG INLINE _ShouldWeConsiderThisMove(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG uMoveNum, IN SCORE iFutility, IN FLAG fGeneratedChecks, // TotalNonPawnCount(&ctx->sPosition, // FLIP(ctx->sPosition.uToMove)) -- every // capture's pCaptured is necessarily the // opponent's piece, and uToMove doesn't // change across the move loop this is called // from (search.c's QSearch), so this is one // value for the whole loop. Hoisted out to // the caller instead of recomputed (a POPCNT // each) on every candidate move -- see // 2026-09-16 chess.h/search.c history for why // this replaced a per-call cache-with-valid- // flag branch that would have cost more than // it saved. IN ULONG uOpponentNonPawnCount #ifdef CALIBRATE_QSEARCH_FUTILITY , IN SCORE iAlpha , IN SCORE iBeta , IN SCORE iPositional , IN ULONG uPositionalSource #endif ) { #ifdef DEBUG MOVE mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv; #endif MOVE mv = ctx->sMoveStack.mvf[uMoveNum].mv; ULONG uColor; SCORE iMoveValue; // TRUE once iMoveValue holds a real, comparable SEE-derived value // (winning/even captures and promotions) rather than the raw, // not-directly-comparable generation-time score a losing capture // keeps. Used both for real control flow (the checking-move // branch below needs to know which of two populations it's // looking at) and, under CALIBRATE_QSEARCH_FUTILITY, to decide // whether a reject is worth diagnosing. FLAG fHaveMoveValue = FALSE; ASSERT(!IS_CHECKING_MOVE(mvLast)); ASSERT(!InCheck(&(ctx->sPosition), ctx->sPosition.uToMove)); if (IS_CAPTURE_OR_PROMOTION(mv)) { // IDEA: if mvLast was a promotion, try everything here? // Don't consider promotions to anything but queens unless // it's a knight and we are going for a knockout. if ((mv.pPromoted) && (!IS_QUEEN(mv.pPromoted))) { if (!IS_KNIGHT(mv.pPromoted) || !IS_CHECKING_MOVE(mv) || (FALSE == fGeneratedChecks)) { return(FALSE); } } iMoveValue = ctx->sMoveStack.mvf[uMoveNum].iValue; if (iMoveValue >= SORT_THESE_FIRST) { fHaveMoveValue = TRUE; // This function is only ever called outside of check (see // the ASSERTs above), so uMoveNum always indexes one of // QSearch's two schemes -- never MOVE_SCORING_ESCAPE. Which // of the two matters here: InclChecks bakes in a +4 // checking-move nudge NoChecks doesn't, so a raw // MOVE_SCORE_ORDERING_BIAS subtraction alone (correct for // NoChecks) silently over-values a checking capture scored // under InclChecks by 4. DecodeMoveValueEstimate (searchsup.c) // is the one place that knows the difference. iMoveValue = DecodeMoveValueEstimate( mv, iMoveValue, ctx->sPlyInfo[ctx->uPly].eMoveScoringScheme); if (mv.pCaptured) { // If there are very few pieces left on the board, // consider all captures because we could be, for // example, taking the guy's last pawn and forcing a // draw. Even though the cap looks futile the draw // might save the game... uColor = GET_COLOR(mv.pCaptured); ASSERT(OPPOSITE_COLORS(ctx->sPosition.uToMove, uColor)); ASSERT(uColor == FLIP(ctx->sPosition.uToMove)); ASSERT(uOpponentNonPawnCount == TotalNonPawnCount(&ctx->sPosition, uColor)); if ((IS_PAWN(mv.pCaptured) && FastCountBits(ctx->sPosition.bbPawns[uColor]) == 1) || (!IS_PAWN(mv.pCaptured) && uOpponentNonPawnCount == 2)) { return(TRUE); } // Also always consider "dangerous pawn" captures. if (IS_PAWN(mv.pMoved) && (((GET_COLOR(mv.pMoved) == WHITE) && RANK7(mv.cTo)) || ((GET_COLOR(mv.pMoved) == BLACK) && RANK2(mv.cTo)))) { return(TRUE); } // Don't trust the SEE alone for alpha pruning decisions. iMoveValue = MAXU(iMoveValue, PIECE_VALUE(mv.pCaptured)); // RETIRED 2026-09-08: used to give recaptures (same // captured-piece value as mvLast) a flat +100 bonus // here ("the bad trade penalty can make them look // futile sometimes"). CALIBRATE_QSEARCH_FUTILITY data // showed it wasn't testing real recaptures at all -- // this check never compared mv.cTo to mvLast.cTo, so // "recapture-shaped" meant "captured a same-valued // piece anywhere on the board," diluting genuine // recaptures (usually safe) with unrelated captures // (not specially safe) under one bonus. That mismatch // is the more likely explanation for the gate's high, // slowly-decaying surprise rate (13.25% at distance // 0-25, still 3.29% at 400+) than the constant being // merely too small. Removed rather than re-tuned; // reintroduce with a same-square check if a bonus // still looks warranted once the generic gate's own // margin is fixed. } // Otherwise, even if a move is even/winning, make sure it // brings the score up to at least somewhere near alpha. if (iMoveValue > iFutility) { return(TRUE); } } // If we get here the move was either a losing capture/prom // that checked or a "futile" winning capture/prom that may or // may not check. Be more willing to play checking captures // even if they look bad. // // RETIRED VALUE_ROOK 2026-09-08: used to judge both // populations below by a single position-level "iFutility < // VALUE_ROOK" cutoff, discarding iMoveValue entirely even // when a real one existed. CALIBRATE_QSEARCH_FUTILITY data // showed a flat, non-decaying-with-distance surprise rate // (8-16%, no better far past the threshold than right at it) // -- the signature of a position-level test standing in for a // move-level question it can't actually answer. Split into // the two populations that were being conflated: a move with // a real (winning/even) iMoveValue gets the same value-plus- // flat-bonus treatment as any other capture; a move with no // usable value (SEE already called it losing) falls back to // GetMoveSee's real tactical judgment, exactly like the // quiet-check (VALUE_BISHOP) branch already does below. if (IS_CHECKING_MOVE(mv) && (TRUE == fGeneratedChecks)) { if (TRUE == fHaveMoveValue) { FLAG fConsider = (iMoveValue + CHECK_BONUS > iFutility); #ifdef CALIBRATE_QSEARCH_FUTILITY if (FALSE == fConsider) { _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta, iPositional, uPositionalSource, QFUT_GATE_CHECK_ROOK, iFutility - (iMoveValue + CHECK_BONUS), fGeneratedChecks); } #endif return(fConsider); } { FLAG fConsider = (GetMoveSee(ctx, mv, uMoveNum) >= 0); #ifdef CALIBRATE_QSEARCH_FUTILITY if (FALSE == fConsider) { // No value-level threshold left for this // population (that's the point) -- iFutility // itself is the only position-level number left // to bucket by, used as-is rather than a // difference from some retired constant. _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta, iPositional, uPositionalSource, QFUT_GATE_CHECK_ROOK, iFutility, fGeneratedChecks); } #endif return(fConsider); } } #ifdef CALIBRATE_QSEARCH_FUTILITY // Falls through to the final reject below -- either not a // checking move, or a checking move we weren't generating // checks for this ply (rare; the generic gate is still what // decided this, so tag it the same way). if (TRUE == fHaveMoveValue) { _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta, iPositional, uPositionalSource, QFUT_GATE_GENERIC_CAPTURE, iFutility - iMoveValue, fGeneratedChecks); } #endif } else { // If we get here we have a checking move that does not // capture anything or promote anything. We are interested in // these to some depth. ASSERT(IS_CHECKING_MOVE(mv)); ASSERT(TRUE == fGeneratedChecks); #if 0 // IDEA: don't play obviously losing checks if we are already // way below alpha. if (iFutility < +VALUE_BISHOP) { return(TRUE); } #endif FLAG fConsider = (GetMoveSee(ctx, mv, uMoveNum) >= 0); #ifdef CALIBRATE_QSEARCH_FUTILITY if (FALSE == fConsider) { _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta, iPositional, uPositionalSource, QFUT_GATE_CHECK_BISHOP, iFutility, // - (SCORE)VALUE_BISHOP, fGeneratedChecks); } #endif return(fConsider); } return(FALSE); } // 2026-09-08: was one flat FUTILITY_BASE_MARGIN (150) regardless of // which Eval() exit tier produced iEval/rgiPositional this call. // CALIBRATE_QSEARCH_FUTILITY data (1500 real-game positions, // tests/twic_sample.ep_, sd 6) showed the three tiers need very // different margins to reach a similar surprise rate. Indexed by // PLY_INFO.uLastPositionalSource (set inside Eval() -- see // EVAL_POSITIONAL_SOURCE_* in chess.h). Re-derive with `calibrate // qsearchfutility` if search behavior affecting typical qsearch // iEval/iFutility gaps changes. // // 2026-09-17 re-recalibration: LAZY and SUPERLAZY re-derived (same // harness/pool/depth) after eval.c's lazy/super-lazy iPositional // stopped being flat 0 and became a real, signed p50-based estimate -- // see FUTILITY_BASE_MARGIN_LAZY/SUPERLAZY's own derivation comment in // chess.h for the full before/after surprise-rate table. FULL is // untouched (its iPositional wasn't part of that change). // // 2026-09-11: also reused (unmodified) by QSearchFromCheckNoStandPat's // own stand-pat-safety-net prune below -- moved up here so both // functions can share one definition instead of duplicating/guessing // a second margin. static const SCORE FUTILITY_BASE_MARGIN_BY_SOURCE[EVAL_POSITIONAL_SOURCE_COUNT] = { FUTILITY_BASE_MARGIN_FULL, // EVAL_POSITIONAL_SOURCE_FULL FUTILITY_BASE_MARGIN_LAZY, // EVAL_POSITIONAL_SOURCE_LAZY FUTILITY_BASE_MARGIN_SUPERLAZY, // EVAL_POSITIONAL_SOURCE_SUPERLAZY }; /** Routine description: Side to move is in check and may or may not have had a chance to stand pat at a qnode above this point. Search all legal check evasions and return a mate-in-n score if this is checkmate. Possibly extend the depth to which we generate checks under this node. If there's a stand pat qnode above us the mate-in-n will be weeded out. Parameters: IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta Return value: SCORE **/ SCORE QSearchFromCheckNoStandPat(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta) { POSITION *pos = &ctx->sPosition; CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; ULONG x, uMoveCount; SCORE iBestScore = MATED_SCORE(ctx->uPly); SCORE iScore; MOVE mv; ULONG uLegalMoves = 0; ULONG uQsearchCheckExtension = 0; ASSERT(InCheck(pos, pos->uToMove)); GenerateMoves(ctx, NULLMOVE, GENERATE_ESCAPES); uMoveCount = MOVE_COUNT(ctx, ctx->uPly); if (uMoveCount > 0) { // Consider extending the number of qsearch check-generating // plies for our opponent if this looks good -- we have not // yet been able to stand pat and they might mate us. if ((pf->uQsearchDepth < pf->uQsearchCheckDepth) && (pf->uQsearchDepth < g_uIterateDepth / 4) && (pf->fCouldStandPat[pos->uToMove] == FALSE) && (CountKingSafetyDefects(pos, pos->uToMove) > 4)) { if (ONE_LEGAL_MOVE(ctx, ctx->uPly) || (NUM_KING_MOVES(ctx, ctx->uPly) == 0) || (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1)) { uQsearchCheckExtension = 2; INC(ctx->sCounters.extension.uQExtend); } ctx->sPlyInfo[ctx->uPly].iExtensionAmount = (INT)(uQsearchCheckExtension * ONE_PLY); } } // If we could have stood pat at an ancestor node, though, then any // work we do here to determine "how bad" things really are is very // likely to be wasted effort (since, at the ancestor node, side to // move can stand pat instead of take this line's _bad_ score). // // iEval itself is computed lazily below, on the first quiet // (non-checking) move actually reached, rather than unconditionally // here -- Eval() is a real cost (full/lazy/super-lazy tiers, not // free), and _ScoreAllEscapes tiers captures/checks above quiet // moves, so a beta cutoff on an earlier capture/check is common and // means this never needs to run at all. Self-play measurement // (avg depth/nps regression vs HEAD under equal time) showed this // call's own cost was eating into the node savings this whole // mechanism exists to redirect elsewhere. SCORE rgiPositional[2]; SCORE iEval = 0; FLAG fEvalComputed = FALSE; for (x = ctx->sMoveStack.uBegin[ctx->uPly]; x < ctx->sMoveStack.uEnd[ctx->uPly]; x++) { SelectBestNoHistory(ctx, x); mv = ctx->sMoveStack.mvf[x].mv; mv.bvFlags |= WouldGiveCheck(ctx, mv); #ifdef DEBUG ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED)); ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED; #endif // See above... this is an effort to avoid wasting time // figuring out exactly "how bad" things get here if side to // move already has a "get out of jail free" card in their // pocket (in the form of a stand pat at some ancestor // position). if (TRUE == pf->fCouldStandPat[pos->uToMove] && uLegalMoves > 0 && !IS_CHECKING_MOVE(mv)) { if (FALSE == fEvalComputed) { iEval = Eval(ctx, iAlpha, iBeta, &rgiPositional); ASSERT(ctx->sPlyInfo[ctx->uPly].uLastPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT); ctx->sPlyInfo[ctx->uPly].iEval = iEval; fEvalComputed = TRUE; } // Same shape (and same calibrated per-tier margin) as // normal QSearch's own futility gate below -- see // FUTILITY_BASE_MARGIN_BY_SOURCE's derivation comment. // That margin was calibrated against *ordinary* quiet // positions; resolving a check can swing the eval more // than an ordinary quiet move can (a king escaping to a // genuinely safe square vs. one that only looks escaped), // so this reuses the same margin rather than inventing a // separate, unvalidated one -- better to be at least as // conservative as the calibrated case than to guess looser. // uLastPositionalSource is read off this ply's own // PLY_INFO slot, not a per-thread scalar, so a recursive // QSearch() call for an earlier move in this same loop // (which writes ctx->sPlyInfo[ctx->uPly+1], a different // slot) can't clobber it before a later iteration reads it // back. if (iEval < iAlpha && ((iEval + PIECE_VALUE(mv.pCaptured)) + rgiPositional[pos->uToMove] + FUTILITY_BASE_MARGIN_BY_SOURCE[ ctx->sPlyInfo[ctx->uPly].uLastPositionalSource]) < iAlpha) { continue; } } if (MakeMove(ctx, mv)) { uLegalMoves++; pf->uQsearchNodes++; pf->uQsearchDepth++; ASSERT(uQsearchCheckExtension < 3); pf->uQsearchCheckDepth += uQsearchCheckExtension; ASSERT(pf->uQsearchDepth > 0); iScore = -QSearch(ctx, -iBeta, -iAlpha); pf->uQsearchCheckDepth -= uQsearchCheckExtension; pf->uQsearchDepth--; UnmakeMove(ctx, mv); if (WE_SHOULD_STOP_SEARCHING) { iBestScore = iScore; goto end; } if (iScore > iBestScore) { iBestScore = iScore; ctx->sPlyInfo[ctx->uPly].mvBest = mv; if (iScore > iAlpha) { if (iScore >= iBeta) { KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1); ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); goto end; } else { UpdatePV(ctx, mv); StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly); iAlpha = iScore; } } } } } ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); end: ASSERT((uLegalMoves > 0) || (iBestScore <= -NMATE)); ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING); // No node-type-surprise counting here (unlike Search()/QSearch()'s // own "end:" labels) -- this function has exactly one call site // (QSearch(), which does `goto end` immediately after calling this // at the SAME ply, no MakeMove in between) and QSearch()'s own // "end:" block already counts that identical (iBestScore, ctx->uPly, // eNodeType) outcome; counting here too would double-count every // in-check qsearch node. return(iBestScore); } /** Routine description: The QSearch (Quiescence Search) is a selective search called when there is no remaining depth in Search. Its job is to search only moves that stabilize the position -- once it is quiescence (quiet) we will run a static evaluation on it and return the score. Parameters: SEARCHER_THREAD_CONTEXT *ctx : the searcher context SCORE iAlpha : lowerbound of search window SCORE iBeta : upperbound of search window Return value: SCORE : a score **/ SCORE FASTCALL QSearch(IN SEARCHER_THREAD_CONTEXT *ctx, IN SCORE iAlpha, IN SCORE iBeta) { POSITION *pos = &ctx->sPosition; CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; MOVE mvLast = (pi-1)->mv; MOVE mv; SCORE iBestScore; SCORE iScore; SCORE iEval; SCORE iFutility; SCORE rgiPositional[2]; ULONG x; ULONG uOpponentNonPawnCount; #ifdef PERF_COUNTERS ULONG uLegalMoves; #endif FLAG fIncludeChecks; FLAG fOrigStandPat = ctx->sSearchFlags.fCouldStandPat[pos->uToMove]; static ULONG _WhatToGen[] = { GENERATE_CAPTURES_PROMS, GENERATE_CAPTURES_PROMS_CHECKS }; #ifdef DEBUG ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); ASSERT(ctx->uPly > 0); ASSERT(TRUE == pi->fInQsearch); memcpy(&pi->sPosition, pos, sizeof(POSITION)); #endif INC(ctx->sCounters.tree.u64QNodeCount); pi->iExtensionAmount = 0; if (TRUE == CommonSearchInit(ctx, &iAlpha, &iBeta, &iBestScore)) { goto end; } DTEnterNode(ctx, 0, TRUE, iAlpha, iBeta); // Probe interior node recognizers. Qsearch runs at the deepest, // most performance-sensitive part of the tree, so this used to // unconditionally refuse EGTB probes -- but a qsearch node with few // enough pieces to be in the tablebase at all is exactly the // "trades have happened near a leaf" case the EGTB is most useful // for: only probe when this position's lookup is likely resident // (EGTB_PROBE_IF_RESIDENT -- RecognLookup itself decides, via // EgtbProbeLikelyResident, only on the branch that's actually about // to call ProbeEGTB, so a node an interior recognizer resolves // never pays for the residency check at all) -- see CLAUDE.md. switch(RecognLookup(ctx, &iScore, EGTB_PROBE_IF_RESIDENT)) { case UNRECOGNIZED: break; case RECOGN_EXACT: if ((iAlpha < iScore) && (iScore < iBeta)) { UpdatePV(ctx, RECOGNMOVE); } iBestScore = iScore; goto end; case RECOGN_EGTB: if ((iAlpha < iScore) && (iScore < iBeta)) { UpdatePV(ctx, EGTBMOVE); } iBestScore = iScore; goto end; case RECOGN_LOWER: if (iScore >= iBeta) { iBestScore = iScore; goto end; } break; case RECOGN_UPPER: if (iScore <= iAlpha) { iBestScore = iScore; goto end; } break; #ifdef DEBUG default: ASSERT(FALSE); #endif } // If the side is in check, don't let him stand pat. Search every // reply to check and return a MATE score if applicable. If the // side had a chance to stand pat above then the MATE score will // be disregarded there since it's not forced. if (IS_CHECKING_MOVE(mvLast)) { ASSERT(InCheck(pos, pos->uToMove)); INC(ctx->sCounters.extension.uQExtendChaseNodes); iBestScore = QSearchFromCheckNoStandPat(ctx, iAlpha, iBeta); goto end; } ASSERT(!InCheck(pos, pos->uToMove)); pi->iEval = iEval = iBestScore = Eval(ctx, iAlpha, iBeta, &rgiPositional); // If that Eval (above) was full (i.e. not lazy) it may have set // en prise and trapped piece indicators. Likewise, other nodes // at this depth may have set en prise piece hints. If these are // set and valid, it means this is not a "quiet" position -- don't // let this side stand pat, force them to play a move and recurse. // This is deliberately independent of fCouldStandPat: whether an // ancestor node in this qsearch line had a moment of safety says // nothing about whether *this* node's material danger is real -- // a hanging piece doesn't stop hanging because the position was // quiet three plies ago. fCouldStandPat's job is different (see // its other uses: deciding whether a *whole line* looks forcing // enough to justify extra qsearch depth/breadth), not gating // per-node stand-pat correctness. SCORE iInTrouble = ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove); if (0 != iInTrouble) { iBestScore = iAlpha; } else { ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE; if (iBestScore > iAlpha) { iAlpha = iBestScore; ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0); ASSERT(pi->mvBest.uMove == 0); if (iBestScore >= iBeta) { goto end; } } } // He did not choose to stand pat here or we did not allow it. We // will be generating moves and searching recursively. Compute a // futility score: any move less than this will not be searched // because it will just cause a lazy eval answer; is has no shot // to bring the score close enough to alpha to even consider. // // iEval + move_value + margin < alpha // move_value < alpha - margin - iEval iFutility = 0; if (iAlpha < +NMATE) { #ifdef CALIBRATE_QSEARCH_FUTILITY if (TRUE == ctx->fDiagUnprunedSubtree) { // We're inside a diagnostic "what if this rejected move // had been searched anyway" re-search (see // _QFutDiagnoseReject) -- force every gate in this // function wide open so the diagnostic subtree isn't // contaminated by the same pruning it exists to measure. iFutility = -NMATE; } else #endif #ifdef DIAG_NO_QSEARCH_FUTILITY // Diagnostic-only (never defined in a normal build): forces // _ShouldWeConsiderThisMove's gates wide open so every // capture/checking-move margin question in this file passes // trivially, to measure the node-count/time cost of qsearch // futility pruning as a whole -- not for shipping, just for // sizing how expensive a "fully unpruned diagnostic subtree" // would be for the qsearch-futility calibration harness. iFutility = -NMATE; #else ASSERT(pi->uLastPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT); iFutility = iAlpha - (FUTILITY_BASE_MARGIN_BY_SOURCE[pi->uLastPositionalSource] + rgiPositional[pos->uToMove]) - iEval; iFutility = MAX0(iFutility); #endif } // We know we are not in check. If we are early in the qsearch, // and the other side has not yet been able to stand pat yet, and // we have material OR we have hanging pieces, generate checks // here too. Checks are a "good way" to escape from "trouble". // 2026-10-03: the opponent-stand-pat half of the first clause is // waived at a PV node. // // The suppression exists because of a sound argument: if the // opponent was able to stand pat at an ancestor, then once their // stand-pat score has raised alpha there, no line below worth less // than that score can change what they return -- so resolving // whether this subtree is mate-in-10 or merely loses a queen is // wasted work. That reasoning covers every case in a NULL-WINDOW // search: even where their stand-pat did NOT raise alpha, the node // is heading for a fail-low, and a fail-low here is precisely the // parent's beta cutoff -- any score at or below alpha answers the // question identically, so extra precision buys nothing. // // It does not cover a WIDE-WINDOW node. There the exact score // propagates toward the root, so "mate-in-10" and "drops a queen" // are a different PV and a different reported score -- and finding // forced mates from the early plies of qsearch is the whole reason // this check-generation machinery exists. Neither this gate nor // QSearchFromCheckNoStandPat's escape-futility gate consulted node // type, so that case was suppressed along with the rest. // // Hence: at NODE_PV, drop the fCouldStandPat[opponent] requirement // but KEEP the material requirement (an independent sanity check on // whether checks are worth generating at all, not a suppression). // pi->eNodeType is read, never written -- CommonSearchInit remains // the only assigner, and it has already run for this visit (an // early exit there would have jumped to end: long before here), so // the value cannot be stale. Using eNodeType rather than recomputing // (iBeta != iAlpha + 1) matters: iAlpha may have been RAISED by the // stand-pat above, which would make a recomputed test read narrow // for a node that is still genuinely PV. fIncludeChecks = ( (pf->uQsearchDepth < pf->uQsearchCheckDepth) && ( ( ( (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) || (NODE_PV == pi->eNodeType) ) && (pos->uNonPawnMaterial[pos->uToMove] > (VALUE_KING + VALUE_BISHOP)) ) || (FALSE == ctx->sSearchFlags.fCouldStandPat[pos->uToMove]) ) ); GenerateMoves(ctx, NULLMOVE, _WhatToGen[fIncludeChecks]); // Hoisted out of _ShouldWeConsiderThisMove's per-move loop below: // pos->uToMove is fixed for the whole loop, so the opponent's // TotalNonPawnCount is one POPCNT for the entire node, not one per // candidate move. uOpponentNonPawnCount = TotalNonPawnCount(pos, FLIP(pos->uToMove)); #ifdef PERF_COUNTERS uLegalMoves = 0; #endif for (x = ctx->sMoveStack.uBegin[ctx->uPly]; x < ctx->sMoveStack.uEnd[ctx->uPly]; x++) { SelectBestNoHistory(ctx, x); if (ctx->sMoveStack.mvf[x].iValue <= 0) { // We are only intersted in winning/even captures/promotions // and (if fIncludeChecks is TRUE) some checking moves too. // If we see a move whose value is zero, the rest of the moves // in this ply can be tossed. ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE | VERIFY_AFTER)); goto end; } mv = ctx->sMoveStack.mvf[x].mv; #ifdef DEBUG ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED)); ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED; #endif if (FALSE == _ShouldWeConsiderThisMove(ctx, x, iFutility, fIncludeChecks, uOpponentNonPawnCount #ifdef CALIBRATE_QSEARCH_FUTILITY , iAlpha , iBeta , rgiPositional[pos->uToMove] , pi->uLastPositionalSource #endif )) { continue; } // If fIncludeChecks is FALSE then we still need to see if // this move is going to check the opponent; GenerateMoves // didn't do it for us to save time in the event of a fail // high. Tried swapping this for a post-MakeMove InCheck call // instead (the theory: at most one query, nothing to amortize // WouldGiveCheck's table-build against) -- measured worse on // 2 of 3 curated suites (ringers +7.2%, confident_quick +5.9%, // hard_quick -1.2%, sd 10, node counts identical either way). // The assumption was wrong: this loop tries more than one move // per node whenever an earlier candidate raises alpha without // failing high, and the lazy-built bbUnblocked[uPly] (see // WouldGiveCheck) gets reused cheaply across all of those, // while a fresh InCheck call pays full price every time with // no reuse at all. Reverted -- WouldGiveCheck stays here. if (FALSE == fIncludeChecks) { mv.bvFlags |= WouldGiveCheck(ctx, mv); } if (MakeMove(ctx, mv)) { #ifdef PERF_COUNTERS uLegalMoves++; #endif pf->uQsearchNodes++; pf->uQsearchDepth++; ASSERT(pf->uQsearchDepth > 0); iScore = -QSearch(ctx, -iBeta, -iAlpha); pf->uQsearchDepth--; UnmakeMove(ctx, mv); if (WE_SHOULD_STOP_SEARCHING) goto end; if (iScore > iBestScore) { iBestScore = iScore; pi->mvBest = mv; if (iScore > iAlpha) { if (iScore >= iBeta) { // A fail-high capturing a non-pawn piece is // search-proven evidence that piece was en // prise -- victim belongs to the mover at // ctx->uPly - 1, not here (see the same // reasoning in the main Search() fail-high // branch). Skip near mate. if (mv.pCaptured && !IS_PAWN(mv.pCaptured) && (iBeta < +NMATE)) { ASSERT(ctx->uPly > 0); RecordEnprisePieceAtPly(ctx, ctx->uPly - 1, mv.cTo); } KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1); ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); goto end; } else { UpdatePV(ctx, mv); StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly); iAlpha = iScore; // Readjust futility margin here; it can be wider now. if (iAlpha < +NMATE) { // pi->uLastPositionalSource is this ply's // own PLY_INFO slot -- the recursive // QSearch() call just above (for the move // that raised alpha) wrote its own nested // Eval() results to ctx->uPly+1, a // different slot, so this one is // untouched and still describes the same // Eval() call that produced iEval/ // rgiPositional above. ASSERT(pi->uLastPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT); iFutility = (iAlpha - (FUTILITY_BASE_MARGIN_BY_SOURCE[ pi->uLastPositionalSource] + rgiPositional[pos->uToMove]) - iEval); iFutility = MAX0(iFutility); } } } } } } ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE)); end: ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = fOrigStandPat; ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING); DTLeaveNode(ctx, TRUE, iBestScore, pi->mvBest); // Note: iBestScore can be +INFINITY_SCORE or -INFINITY_SCORE here even in the // absence of a legitimate mate detected if we disallowed stand // pat due to perceived danger early on, when the a..b window had // an extreme bound. This is "legitimate" but weird. return(iBestScore); }