diff options
| author | Scott Gasch <[email protected]> | 2026-10-14 12:36:24 -0700 |
|---|---|---|
| committer | Scott Gasch <[email protected]> | 2026-10-14 12:36:24 -0700 |
| commit | bb2d7a9cce6275fcfb038c8a3ab248ba3cf2c827 (patch) | |
| tree | fd340778cf077ec53df1b144bf191ee8ae8188ea /src/searchsup.c | |
| parent | 2d7d182d4ab518d9f48c5b8cef0c5f664ed9ba3f (diff) | |
Extract Search()'s per-move kernel into SearchOneMove (searchsup.c)
UNIFY_SEARCH.md step 2: pull the per-move body out of Search()'s move
loop (search.c) -- SEE, MakeMove, extension, LMP/LMR eligibility and
decision, PVS search with re-search-on-fail-high, UnmakeMove -- into
a standalone function, SearchOneMove (searchsup.c), called from
Search() in place of the inline block. HelpSearch() (split.c) is
deliberately untouched for now; unifying it onto this same kernel is
UNIFY_SEARCH.md's later step.
Not extracted (stays in Search(), per UNIFY_SEARCH.md's "what should
NOT be extracted"): move acquisition/selection, result publication
(iAlpha/mvBest bookkeeping, UpdatePV, hash storage), and the
split-launch decision. The split-launch check (StartParallelSearch)
runs BEFORE this kernel would be called for that move, unaffected.
MOVE_KERNEL_RESULT (chess.h) replaces the old goto/continue control
flow a called function can't use: SEARCHED (made, searched, unmade;
*piScore valid), PRUNED (LMP fired, never made), ILLEGAL (MakeMove
refused mv -- previously silent fall-through with no uLegalMoves
bump), ABORTED (WE_SHOULD_STOP_SEARCHING fired after the move was
already made/searched/unmade -- *piScore is a real partial result).
fFullWindow is an explicit parameter, not inferred from the
iBestScore==-INFINITY_SCORE sentinel the inline code used -- that
sentinel is only safe because HelpSearch() currently never calls
this code at all. Once HelpSearch() also calls SearchOneMove (a
later step), its own first move off the shared pool would never be
this sentinel's "node's actual first move" in the first place, so
making the caller state it explicitly removes a trap that wouldn't
assert if violated.
FORCEINLINE across the search.c/searchsup.c boundary, no new shared
header -- matches this project's own existing convention (WouldGiveCheck,
generate.c, non-static FORCEINLINE, called from half a dozen .c files,
"one of the most called codepaths... speed of the essence") rather than
needing search_inline.h as UNIFY_SEARCH.md originally sketched. Verified
actual inlining, not just assumed it: `nm`/objdump on the final linked
typhoon binary show no SearchOneMove symbol and no call instruction
anywhere -- same as WouldGiveCheck/ComputeMoveExtension/
CanWeReduceOrPruneMove, all of which inline away entirely under this
build's -flto, while non-inlined functions (Search, HelpSearch) still
show up as expected. Confirms the long parameter list costs nothing at
runtime (no call/ret/stack-marshaling survives once genuinely inlined).
Diagnostic locals crossing the old inline-block boundary resolved per
their actual #ifdef gating (checked, not assumed): fIsLeftoverMove/
fMoveIsPruneReduceEligible and the four uThisMove*Bucket values are
read only under #ifdef PERF_COUNTERS post-kernel, so they're OUT
params gated the same way; fThisMoveIsCountermoveMatch/uCMEvidenceBucket
are caller-computed before the kernel and never mutated by it, so
plain IN params under MOVE_ORDERING_EVIDENCE_COLLECTION;
fThisMoveJointExtraEligible/uThisMoveJointExtraTier never cross the
boundary at all (every consumer is inside the kernel), so they became
pure kernel-locals, dropped from Search()'s own declarations entirely.
Verification: precommit_check.sh passes. Bit-identical node counts
(per UNIFY_SEARCH.md's step-2 gate) confirmed at sd10/--cpus 1 against
the pre-extraction baseline (head_reference/pre_unification_sd10_cpus1/)
across all 191 positions in the three curated suites, zero differences
-- a pure refactor, exactly as required at this stage.
Co-Authored-By: Claude Sonnet 5 <[email protected]>
Diffstat (limited to 'src/searchsup.c')
| -rw-r--r-- | src/searchsup.c | 522 |
1 files changed, 522 insertions, 0 deletions
diff --git a/src/searchsup.c b/src/searchsup.c index d94dbb4..64dc991 100644 --- a/src/searchsup.c +++ b/src/searchsup.c @@ -1662,6 +1662,528 @@ Return value: } +MOVE_KERNEL_RESULT FORCEINLINE +SearchOneMove(IN SEARCHER_THREAD_CONTEXT *ctx, + IN MOVE mv, + IN ULONG x, + IN FLAG fIsGeneratedMoveStage, + IN ULONG uDepth, + IN SCORE iAlpha, + IN SCORE iBeta, + IN SCORE iEval, + IN INT iPositionalExtend, + IN FLAG fIsLeftoverMove, + IN FLAG fThreat, + IN FLAG fFullWindow, + IN ULONG uRawDepthB, + IN ULONG uRawImproveB, + IN BITBOARD bbMinorAttacksSnapshot[2], + IN BITBOARD bbRookAttacksSnapshot[2], +#ifdef MOVE_ORDERING_EVIDENCE_COLLECTION + IN FLAG fThisMoveIsCountermoveMatch, + IN ULONG uCMEvidenceBucket, +#endif +#ifdef TEST_NULL + IN FLAG fNullCalibEligible, + IN ULONG uNullCalibBucket, + OUT UINT64 *puNullCalibFirstMoveNodeCost, +#endif + IN OUT ULONG *puLegalMoves, + OUT SCORE *piScore +#ifdef PERF_COUNTERS + , OUT FLAG *pfMoveIsPruneReduceEligible + , OUT ULONG *puThisMoveHangBucket + , OUT ULONG *puThisMoveGapBucket + , OUT ULONG *puThisMoveNumBucket + , OUT ULONG *puThisMoveDepthBucket +#endif + ) +/** + +Routine description: + + The per-move kernel hoisted out of Search()'s move loop + (search.c): make the move, compute its extension, decide whether + to prune or reduce it, search it with a PVS window, re-search if + a reduced move fails high, unmake it. See UNIFY_SEARCH.md for the + full extraction rationale and a parameter-by-parameter accounting + of why each non-obvious one is here. + + Deliberately NOT included (stays in each caller instead): move + acquisition (how mv was selected), result publication (iAlpha/ + mvBest bookkeeping, UpdatePV, hash storage), and the split-launch + decision itself. See UNIFY_SEARCH.md's "What should NOT be + extracted" section. + +Parameters: + + See the prototype's own inline comments (chess.h) for the + non-obvious ones (x, uStage, fFullWindow, the node-level hoists). + +Return value: + + MOVE_KERNEL_RESULT -- see chess.h's enum comment. + +**/ +{ + PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; + CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags; + SCORE iMoveSee = 0; + INT iExtend; + ULONG uNextDepth; + FLAG fThisMoveLMPPruned; + FLAG fMoveIsPruneReduceEligible = FALSE; + SCORE iScore; +#ifdef PERF_COUNTERS + ULONG uThisMoveJointExtraTier = 0; + FLAG fThisMoveJointExtraEligible = FALSE; + ULONG uThisMoveHangBucket = 0; + ULONG uThisMoveGapBucket = 0; + ULONG uThisMoveNumBucket = 0; + ULONG uThisMoveDepthBucket = 0; +#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. + if (IS_CHECKING_MOVE(mv) || + (mv.pCaptured && !IS_PAWN(mv.pCaptured) && (uDepth <= THREE_PLY))) + { + iMoveSee = GetMoveSee(ctx, + mv, + (TRUE == fIsGeneratedMoveStage) ? + (x - 1) : (ULONG)-1); + } + + if (FALSE == MakeMove(ctx, mv)) + { + return(MOVE_KERNEL_ILLEGAL); + } + + (*puLegalMoves)++; + ASSERT((IS_CHECKING_MOVE(mv) && InCheck(&ctx->sPosition, ctx->sPosition.uToMove)) || + (!IS_CHECKING_MOVE(mv) && !InCheck(&ctx->sPosition, ctx->sPosition.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((*puLegalMoves > 1) ? (x != 0) : TRUE); + + // Pruning on alpha... late move pruning / late move reduction. + fMoveIsPruneReduceEligible = CanWeReduceOrPruneMove(ctx, + mv, + x, + *puLegalMoves, + iExtend, + iAlpha, + fThreat, + fIsLeftoverMove); + fThisMoveLMPPruned = FALSE; + if (TRUE == fMoveIsPruneReduceEligible) + { + // In here we consider: + // - LMP (late move 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 5D prediction table, given: + // - the gap from iEval to iAlpha here, + // - move lateness (number), + // - board material apparently hung by mv, + // - remaining depth to search, and + // - improvement... + // + // ...it will give us a predicted FH% for the move. + + ULONG uRawGapB = GapCpBucket((SCORE)(iAlpha - iEval)); + ULONG uRawLateB = MoveNumBucket(*puLegalMoves); + SCORE iHangCp = EstimateHangingMaterialCp(ctx, mv, (x - 1), + bbMinorAttacksSnapshot, + bbRookAttacksSnapshot); + ULONG uRawDumbB = HangCpBucket(iHangCp); + + // Note: 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. + ULONG uPredictedFH = _JointTablePredictedFHThousandths(uRawDepthB, + uRawDumbB, + uRawGapB, + uRawLateB, + uRawImproveB); + + // Late move pruning; skip searching under this move? + fThisMoveLMPPruned = ShouldLatePrune( + ctx, + uDepth, + *puLegalMoves, + uFHAttempts, + uFHPctThousandths, + uPredictedFH); + + // If LMP didn't fire, 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) && + (uDepth > TWO_PLY)) + { + ULONG uExtraTier = 0; + INT iLMR = GetLMRReduction(ctx, + uDepth, + *puLegalMoves, + 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, LMR -- move pruning and reduction + + if (TRUE == fThisMoveLMPPruned) + { +#ifdef PERF_COUNTERS + INC(ctx->sCounters.tree.u64LMPPruned); +#endif + UnmakeMove(ctx, mv); + ASSERT(PositionsAreEquivalent(&ctx->sPosition, &pi->sPosition)); +#ifdef PERF_COUNTERS + *pfMoveIsPruneReduceEligible = fMoveIsPruneReduceEligible; +#endif + return(MOVE_KERNEL_PRUNED); + } + +#ifdef PERF_COUNTERS + if (TRUE == fIsLeftoverMove) + { + INC(ctx->sCounters.tree.u64LeftoverTries); + +#ifdef FH_TABLE_COLLECTION + if (TRUE == fMoveIsPruneReduceEligible) + { + 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(*puLegalMoves); + 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; + pf->iCumulativeExtend += iExtend; + + // Compute the next search depth for this move/subtree. + uNextDepth = uDepth - ONE_PLY + iExtend; + if (uNextDepth >= MAX_DEPTH_PER_SEARCH) { + uNextDepth = 0; + } + + ASSERT(pf->fAvoidNullmove == FALSE); + if (TRUE == fFullWindow) + { + // First move, full a..b window. + ASSERT(*puLegalMoves == 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); + *puNullCalibFirstMoveNodeCost = + 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); + } + } + + // Deeper verification search late move reduction FH. + 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 + // Undo the full reduction, whatever its magnitude... + uNextDepth -= iExtend; + 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 + // 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. + CHAR szShadowPV[SMALL_STRING_LEN_CHAR] = ""; + { + MOVE mvChain[8]; + ULONG uChainLen = 0; + MOVE mvNext; + + while ((uChainLen < 8) && + (0 != (mvNext = GetPonderMove(&ctx->sPosition)).uMove)) + { + strncat(szShadowPV, MoveToSan(mvNext, &ctx->sPosition), + 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 + 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(&ctx->sPosition), + szShadowPV); +#endif + } + } +#endif + UnmakeMove(ctx, mv); + pf->iCumulativeExtend -= iExtend; + ASSERT(PositionsAreEquivalent(&ctx->sPosition, &pi->sPosition)); + +#ifdef PERF_COUNTERS + *pfMoveIsPruneReduceEligible = fMoveIsPruneReduceEligible; + *puThisMoveHangBucket = uThisMoveHangBucket; + *puThisMoveGapBucket = uThisMoveGapBucket; + *puThisMoveNumBucket = uThisMoveNumBucket; + *puThisMoveDepthBucket = uThisMoveDepthBucket; +#endif + *piScore = iScore; + + if (WE_SHOULD_STOP_SEARCHING) + { + return(MOVE_KERNEL_ABORTED); + } + return(MOVE_KERNEL_SEARCHED); +} #ifdef DO_IID |
