/** 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-2 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) // 2026-10-13: "skip trying null-move at all" on the iEval <= iAlpha // side (alpha-side table, EV-neutral -- the real move loop still runs // and finds the correct score either way; we only forgo the cheap // null-move probe on the rare occasion it would have worked). Units // are thousandths of a percent (same convention as everywhere else // here). 300 is the validated default -- swept against both halves // of ecm.ep_ at sd6/sd10, spot-checked at sd16, and against 1000 // cross_sectional_1.ep_ positions; consistently in the plateau past // the knee with no solve-count cost anywhere tested. Still overridable // for further sweeping; 0 disables entirely. See // NULLMOVE_SKIP_CALIBRATION.md for the original methodology. #ifndef NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS #define NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS (300) #endif // 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 // fMoveIsPruneReduceEligible 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. #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; ULONG uNextDepth; ULONG uNullR; ULONG uLegalMoves = 0; FLAG fIsLeftoverMove = FALSE; FLAG fParentAttackTablesAreFresh; BITBOARD bbMinorAttacksSnapshot[2]; BITBOARD bbRookAttacksSnapshot[2]; FLAG fMoveIsPruneReduceEligible = FALSE; ULONG uRawDepthB; #ifdef MP FLAG fNodeSplitEligible; #endif #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; #endif HASH_ENTRY sHash; FLAG fHashHit; FLAG fThreat; FLAG fSkipNull; FLAG fIsDraw; ULONG uStage = TRY_HASH_MOVE; ULONG u; MOVE_KERNEL_RESULT eMoveKernelResult; #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; // Note: pi->fInCheck set by CommonSearchInit. 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: // Unconditional: a recognizer-proven exact result is a // game-theoretic fact about this position, not a bound -- // unlike an ordinary heuristic score, it can't be "wrong" // for having been reached outside the ambient (alpha, // beta) window, so it deserves to be recorded regardless // (see CLAUDE.md's MATEMOVE/DRAWMOVE/RECOGNMOVE/EGTBMOVE // writeup -- all five sentinel cases shared this same // gate, which is why //<#>/<=> almost never // showed up in a printed PV). UpdatePV(ctx, RECOGNMOVE); iBestScore = iScore; goto end; case RECOGN_EGTB: 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 } // Run Eval() at every node. pi->iEval = iEval = Eval(ctx, iAlpha, iBeta, &(pi->iPositional)); SCORE iImprovement = 0; if (ctx->uPly > 1) { iImprovement = (iEval - ctx->sPlyInfo[ctx->uPly - 2].iEval); } ULONG uRawImproveB = ImproveBucket(iImprovement); SCORE iEnemyImprovement = 0; if (ctx->uPly > 2) { iEnemyImprovement = (ctx->sPlyInfo[ctx->uPly - 1].iEval - ctx->sPlyInfo[ctx->uPly - 3].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 // Pruning on beta. if ((FALSE == fSkipNull) && (FALSE == fThreat) && (FALSE == pi->fInCheck) && (NODE_PV != pi->eNodeType) && (iBeta < +NMATE)) { FLAG fSkipNullForLowFH = FALSE; // Static nullmove pruning / reverse futility pruning? if (iEval > iBeta) { ULONG uStaticNMDepthB = DepthBucket(uDepth / ONE_PLY); ULONG uRawEnemyImproveB = ImproveBucket(iEnemyImprovement); INC(ctx->sCounters.tree.u64QuickNullMoves); ULONG uBetaPredictedFHThousandths = _BetaTablePredictedFHThousandths( uStaticNMDepthB, GapBetaBucket((SCORE)(iEval - iBeta)), uRawImproveB, uRawEnemyImproveB); if ((uBetaPredictedFHThousandths != 0xFFFF) && (uBetaPredictedFHThousandths > 95000)) { INC(ctx->sCounters.tree.u64QuickNullMoveSuccess); // TODO: SF returns a mix of iBeta and iEval here. Test // this. iBestScore = iBeta; goto end; } } #if (NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS > 0) else if (iEval <= iAlpha) { ULONG uNullSkipDepthB = DepthBucket(uDepth / ONE_PLY); ULONG uRawGapAlphaB = GapCpBucket((SCORE)(iAlpha - iEval)); USHORT uAlphaPredictedFH = _JointTablePredictedFHThousandths( uNullSkipDepthB, 0, // hang bucket: assume nothing hung uRawGapAlphaB, 1, // late bucket: "early move" proxy uRawImproveB); if ((uAlphaPredictedFH != 0xFFFF) && (uAlphaPredictedFH < NULLMOVE_SKIP_FH_CEILING_THOUSANDTHS)) { fSkipNullForLowFH = TRUE; INC(ctx->sCounters.tree.u64NullMoveSkippedLowFH); } } #endif if ((FALSE == fSkipNullForLowFH) && WeShouldTryNullmovePruning(ctx, iAlpha, iBeta, iEval, iImprovement, uNextDepth)) { ULONG uNullRBucket = uNullR / ONE_PLY; if (uNullRBucket >= NULL_R_BUCKETS) { uNullRBucket = NULL_R_BUCKETS - 1; } INC(ctx->sCounters.tree.u64NullMoveTriesByR[uNullRBucket]); 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); } pf->fAvoidNullmove = FALSE; // 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... 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)) { 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. ASSERT(iPositionalExtend <= ONE_PLY); // fall through case PREPARE_TO_TRY_MOVES: ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]); ASSERT((uLegalMoves == 0) || ((uLegalMoves == 1) && (mvHash.uMove))); 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; } } uStage++; uRawDepthB = DepthBucket(uDepth / ONE_PLY); #ifdef MP // See fNodeSplitEligible's declaration comment -- same // four conditions the move loop used to re-check on // every iteration (uDepth>=ONE_PLY guards the array // index exactly as before: g_fCanSplit[] is never // indexed when it's false, short-circuit preserved). fNodeSplitEligible = (MOVE_SCORING_IID_RESCORED != pi->eMoveScoringScheme) && (uDepth >= ONE_PLY) && (TRUE == g_fCanSplit[uDepth / ONE_PLY - 1]) && (MOVE_COUNT(ctx, ctx->uPly) > 4); #endif 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]); // Select the best move to try next. if (MOVE_SCORING_IID_RESCORED == pi->eMoveScoringScheme) { SelectBestNoHistory(ctx, x); // mv's score is search-based // Note: 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? fNodeSplitEligible // (hoisted above, PREPARE_TO_TRY_MOVES) folds the uDepth>=ONE_PLY / // g_fCanSplit[] / MOVE_COUNT / eMoveScoringScheme checks -- all // node-constant, see its own declaration comment. Only // uLegalMoves/fIsLeftoverMove (genuinely per-move) and // g_uNumHelpersAvailable (genuinely dynamic, mutated by other // threads) still need a fresh check every iteration. if ((uLegalMoves >= 2) && (TRUE == fIsLeftoverMove) && (0 != g_uNumHelpersAvailable) && fNodeSplitEligible) { 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, fThreat, bbMinorAttacksSnapshot, bbRookAttacksSnapshot); 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 // Per-move kernel, extracted to searchsup.c's SearchOneMove -- // see UNIFY_SEARCH.md. fFullWindow replaces the old // iBestScore==-INFINITY_SCORE sentinel explicitly (the sentinel // was never safe to reuse once a second caller -- HelpSearch(), // once unified -- might call this with a shared-pool first // move that is NOT this node's first move). eMoveKernelResult = SearchOneMove(ctx, mv, x, (uStage == TRY_GENERATED_MOVES), uDepth, iAlpha, iBeta, iEval, iPositionalExtend, fIsLeftoverMove, fThreat, (iBestScore == -INFINITY_SCORE), uRawDepthB, uRawImproveB, bbMinorAttacksSnapshot, bbRookAttacksSnapshot, #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION fThisMoveIsCountermoveMatch, uCMEvidenceBucket, #endif #ifdef TEST_NULL fNullCalibEligible, uNullCalibBucket, &uNullCalibFirstMoveNodeCost, #endif &uLegalMoves, &iScore #ifdef PERF_COUNTERS , &fMoveIsPruneReduceEligible , &uThisMoveHangBucket , &uThisMoveGapBucket , &uThisMoveNumBucket , &uThisMoveDepthBucket #endif ); switch (eMoveKernelResult) { case MOVE_KERNEL_ILLEGAL: case MOVE_KERNEL_PRUNED: continue; case MOVE_KERNEL_ABORTED: iBestScore = iScore; goto end; case MOVE_KERNEL_SEARCHED: default: break; } // Check results of search below this move. 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 fMoveIsPruneReduceEligible 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); // Unconditional -- see the RecognLookup sites above: a // checkmate is an exact, game-theoretic fact about this // position, not a bound, so it can't be "wrong" for // having been reached outside the ambient window. INC(ctx->sCounters.tree.u64LeafCount); UpdatePV(ctx, MATEMOVE); ASSERT(iBestScore <= -NMATE); goto end; } else { iBestScore = g_iDrawScore[pos->uToMove]; // Unconditional -- same reasoning as the MATEMOVE case // just above: stalemate is exact, not a bound. INC(ctx->sCounters.tree.u64LeafCount); UpdatePV(ctx, DRAWMOVE); goto end; } } // Not checkmate/stalemate; store the result of this search in the // hash table. TODO: consider adjusting the hash table store to // a bound if we pruned or reduced aggressively here? 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); } 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: // Unconditional: a recognizer-proven exact result is a // game-theoretic fact about this position, not a bound -- // unlike an ordinary heuristic score, it can't be "wrong" // for having been reached outside the ambient (alpha, // beta) window, so it deserves to be recorded regardless // (see CLAUDE.md's MATEMOVE/DRAWMOVE/RECOGNMOVE/EGTBMOVE // writeup -- all five sentinel cases shared this same // gate, which is why //<#>/<=> almost never // showed up in a printed PV). UpdatePV(ctx, RECOGNMOVE); iBestScore = iScore; goto end; case RECOGN_EGTB: 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); }