path: root/src/docs/UNIFY_SEARCH.md

# Unifying the per-move search kernel in `search.c` and `split.c`

Status: **plan only, not started.** Do as the only change in a commit;
test with `precommit_check.sh` plus the `head_reference` node-count gate
below at each step. Line numbers below are current as of this revision
(EFP's explicit per-move pruning block has been removed from `Search()`;
only stale names remain — see "EFP is gone" below).

## Motivation

`Search()`'s main move loop (`search.c:909..1780`) and `HelpSearch()`
(`split.c:1058..1283`) independently implement what is supposed to be the
same per-move logic: 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. They have drifted apart because every
improvement to this logic has been written once, in `search.c`, and not
reliably ported to `split.c`. Concretely, today:

- `Search()` has LMP (late move pruning, via `ShouldLatePrune`/the joint
  FH% table). `HelpSearch()` does not.
- `Search()` gates reduction/pruning eligibility through the single
  `CanWeReduceOrPruneMove()` (searchsup.c:783), which the routine's own
  comment documents as 9 base checks plus 2 move-identity exemptions
  (killer-adjacency, countermove match). `HelpSearch()` (split.c:1187-1193)
  has a hand-rolled 7-condition gate that is missing: the SEE-negative-
  capture carve-out, the mate-magnitude-alpha check, the `fThreat` check,
  and both exemptions. **This is a bigger behavioral gap than "HelpSearch
  lacks LMP"** — `HelpSearch()` is currently reducing/pruning-eligible on
  moves `Search()` would exempt outright.
- `Search()` passes real `bbMinorAttacksSnapshot`/`bbRookAttacksSnapshot`
  attack-bitboard snapshots into `EstimateHangingMaterialCp`. `HelpSearch()`
  passes zeroed snapshots (`split.c:1215-1216`), degrading its hang
  estimate (and, by extension, `ShouldLatePrune`'s joint-table lookup once
  step 4 below gives it one).
- `split.c:1245` and `split.c:1268` write `ctx->sPlyInfo[ctx->uPly]
  .iExtensionAmount` — but both writes happen **after** `MakeMove`, i.e.
  after `ctx->uPly` has already advanced (confirmed: `search.c:465` binds
  `pi = &ctx->sPlyInfo[ctx->uPly]` *before* the move loop's `MakeMove`
  calls; `move.c:928` is where `MakeMove` increments `ctx->uPly`).
  `split.c:1156`'s own `ComputeMoveExtension` call already compensates
  with `uBegin[ctx->uPly - 1]` one line away, so the "-1 after MakeMove"
  pattern is known and applied inconsistently, not unknown. **This is two
  separate bugs, not one:**
  1. Wrong slot: writes the child's `iExtensionAmount`, not the mover's —
     invisible to the null-move history-reduced-bailout check one ply
     down (searchsup.c).
  2. Stale-on-skip: `search.c:1386`'s own comment documents that it used
     to only write `pi->iExtensionAmount` when `iExtend < 0`, and that was
     itself a bug (a later sibling move could read a stale reduction left
     by an earlier one) — fixed in `Search()` by writing it
     unconditionally every iteration. `split.c:1245`/`1268` still only
     write inside `if (iLMR < 0)` / the re-search branch, i.e. still have
     the stale-on-skip bug `Search()` already fixed once.
  Both must be fixed together: unconditional write, to
  `ctx->sPlyInfo[ctx->uPly - 1].iExtensionAmount`.

## EFP is gone — update, don't carry forward

A prior session removed EFP's explicit per-move futility-pruning block
from `Search()`'s move loop entirely. Confirmed by search: `ShouldFutilityPrune`/
`FutilityPrun*`/`StaticNullMove`/`ShouldStaticNull` have zero hits anywhere
in `search.c`/`searchsup.c`/`split.c`. Only inert names remain:
`EFP_FH_MIN_SAMPLES` (search.c:84, unused #define), `_PostReduceDepthBucketEfpAligned`
(a depth-bucketing helper, name is now just vestigial), and
`fAnyMoveEFPPruned` (search.c:1851, read in an `else` branch comment on
the store-upper-bound path — confirm whether this flag can still ever be
set anywhere before relying on it in the extraction; if nothing sets it
any more it's dead and should be dropped in step 0 below, not carried into
the shared kernel).

This also **resolves the doc's previous closing question** ("unify EFP and
LMP before this project") — there's no EFP left to unify; `ShouldLatePrune`'s
joint FH% table is the sole pruning mechanism now. Drop that requirement.

It also means the previously-planned "related gap" about `pi->uPVDistance`
never written in `HelpSearch()` is **moot**: `uPVDistance` has zero hits
anywhere in the codebase now (it was EFP-era instrumentation, removed
along with EFP). Nothing to port.

## What should NOT be extracted

The two loops differ along three axes that are not just stylistic — they
reflect genuinely different control/data flow, and trying to force them
into one shape will make the result worse, not better.

1. **Move acquisition.** `Search()` pulls from a staged iterator (hash
   move, killers, generated moves, ..., tracked via index `x`).
   `HelpSearch()` pulls from a shared move pool via `_GetNextParallelMove`,
   which also hands back the *current* shared `iAlpha`/`iBestScore`
   (another helper thread may have raised them since this thread's last
   iteration). This is loop-header logic. **Stays in each caller.**
2. **Result publication.** `Search()` keeps `iAlpha`/`mvBest` as plain
   thread-local variables, calls `UpdatePV()`, and uses `goto end`/`goto
   no_more_moves`. `HelpSearch()` publishes through the locked
   `_UpdateSplitInfo(ctx, mv, iScore, u)` and checks `g_SplitInfo[u]
   .fTerminate` after every move. Different synchronization models.
   **Stays in each caller.**
3. **The split-launch decision itself** (`search.c:1082-1173`,
   `StartParallelSearch` and the `g_fCanSplit`/`g_uNumHelpersAvailable`
   gating). Must stay outside the extracted kernel, or a helper thread
   executing the kernel could attempt to launch a nested split, which the
   current design does not expect. **Stays in `search.c` only.**

## What SHOULD be extracted

The inner per-move kernel, called once per move after it's been pulled off
whichever move source the caller uses — current location
`search.c:1175-1681` (SEE computation through `UnmakeMove` and the
`iCumulativeExtend` restore), immediately before the publication tail that
starts at `search.c:1684`:

```
SEE (pre-move, on pos)
  -> MakeMove
  -> ComputeMoveExtension
  -> CanWeReduceOrPruneMove gate
       -> ShouldLatePrune (LMP)
       -> GetLMRReduction (LMR)
  -> PVS search (null-window, then full-window re-search if it raises alpha)
  -> re-search to full depth if a reduced move fails high
  -> UnmakeMove
```

## The instrumentation problem (the design question the old draft missed)

The span to extract is NOT a clean make/decide/search/unmake block with no
side channels. The publication tail at `search.c:1684-1777` reads several
locals the kernel's interior sets, and `JOINT_EXTRA_VERIFY`'s shadow-search
block sits *between* the PVS re-search and `PRUNE_VERIFY`'s fail-high
check, inside the make/unmake span — the instrumentation can't be
boundary-excluded without duplicating the real move-handling logic around
it. Locals that cross the proposed kernel/caller boundary in both
directions:

- Caller → kernel (already loop-invariant, computed once outside the
  per-move loop; pass as params, don't recompute): `uRawDepthB`
  (`search.c:993`), `uRawImproveB`, `fNodeSplitEligible`.
- Kernel → caller (read by the publication tail at 1684+, must survive the
  call): `fIsLeftoverMove`, `fMoveIsPruneReduceEligible`,
  `uThisMoveHangBucket`/`GapBucket`/`NumBucket`/`DepthBucket` (all
  `PERF_COUNTERS`/`FH_TABLE_COLLECTION`-gated), `fThisMoveIsCountermoveMatch`/
  `uCMEvidenceBucket` (`MOVE_ORDERING_EVIDENCE_COLLECTION`-gated),
  `fThisMoveJointExtraEligible`/`uThisMoveJointExtraTier`
  (`PERF_COUNTERS`-gated), `fVerifyFlagged`/`uVerifyBand`/`uVerifyDepthB`/
  `uVerifyAttB`/`uVerifyRateB` (`PRUNE_VERIFY`-gated), and the `TEST_NULL`
  node-cost pair.

**Decision needed before writing code, not discovered mid-extraction**:
bundle all of this into one `OUT` struct (e.g. `MOVE_KERNEL_DIAGNOSTICS`,
`#ifdef`-sectioned to match each field's existing gate) that the kernel
fills in and the caller's publication tail reads — rather than a long
flat parameter list. The user's note below ("put what you can in
`PLY_INFO`") is the other half of this: some of these (the bucket/tier
values) are genuinely per-move-at-this-ply state and belong as fields on
`ctx->sPlyInfo[ctx->uPly - 1]` (indexed the same way `iExtensionAmount`
already is) rather than threaded through call/return at all — this
removes most of the diagnostics-struct bulk and gives `HelpSearch()`'s
own ply slot the same fields for free. Resolve this split (struct vs.
`PLY_INFO` fields vs. a mix) as part of scoping the extraction, before
step 3.

## Two sequencing traps that will break the "bit-identical node counts" gate

- `pf->iCumulativeExtend += iExtend` (search.c:1387) happens *after* the
  LMP-prune `continue` (search.c:1313-1315) — the prune path `UnmakeMove`s
  but never increments/decrements `iCumulativeExtend` for that move at
  all. A `MOVE_KERNEL_PRUNED` return must preserve that asymmetry exactly;
  don't "clean up" by making prune and search paths symmetric around
  `iCumulativeExtend`.
- `WE_SHOULD_STOP_SEARCHING` (search.c:1684) is checked *after*
  `UnmakeMove` and *after* the `iCumulativeExtend -=` restore. A
  `MOVE_KERNEL_ABORTED` return must not skip either of those — the kernel
  itself must still fully unwind (unmake + restore) before reporting
  abort, not bail out of the middle of its own cleanup.

## Proposed signature

```c
typedef enum _MOVE_KERNEL_RESULT
{
    MOVE_KERNEL_SEARCHED,   // move was made, searched, and unmade; iScore valid
    MOVE_KERNEL_PRUNED,     // move was late-move-pruned; not made; iScore invalid
    MOVE_KERNEL_ABORTED     // search was stopped mid-move; iScore is a partial result
} MOVE_KERNEL_RESULT;

FORCEINLINE MOVE_KERNEL_RESULT
SearchOneMove(SEARCHER_THREAD_CONTEXT *ctx,
              MOVE mv,
              ULONG uDepth,
              SCORE iAlpha,
              SCORE iBeta,
              SCORE iEval,
              ULONG uLegalMoves,
              FLAG fIsLeftoverMove,
              FLAG fFullWindow,
              FLAG fThreat,
              ULONG uRawDepthB,
              ULONG uRawImproveB,
              BITBOARD bbMinorAttacksSnapshot[2],
              BITBOARD bbRookAttacksSnapshot[2],
              OUT SCORE *piScore,
              OUT INT *piExtend);
    // Diagnostics (hang/gap/num/depth buckets, countermove-evidence
    // bucket, joint-extra tier, prune-verify band) are NOT parameters --
    // see "the instrumentation problem" above. They land in
    // ctx->sPlyInfo[ctx->uPly - 1] (written by the kernel before it
    // unmakes) wherever that's a clean fit, or an OUT diagnostics struct
    // otherwise. Finalize the split while scoping step 3, not here.
```

Notes on why each non-obvious parameter is there:

- **`fFullWindow` is explicit, not inferred.** `Search()`'s current code
  infers "is this the first move at this node" from the sentinel
  `iBestScore == -INFINITY_SCORE` (search.c:1396). That sentinel is only
  true for `Search()`'s actual first move. `HelpSearch()` must never take
  that branch — a helper thread's first move off the shared pool is *not*
  the node's first move — and today this is only safe because
  `_GetNextParallelMove` happens to never hand back `-INFINITY_SCORE`.
  Once this logic is shared, that implicit contract becomes load-bearing
  in a way that won't assert if violated. Making it an explicit
  caller-supplied flag removes the trap.
- **`uLegalMoves` is a parameter, not computed inside.** It feeds
  `MoveNumBucket`/`ShouldLatePrune`'s floor and `CanWeReduceOrPruneMove`'s
  own `uLegalMoves > 1` check. `search.c` has it as a running counter;
  `split.c` must pass `g_SplitInfo[u].uAlreadyDone + uMoveNum + 1`
  (matching what it already computes locally as `uSplitLegalMoves` at
  split.c:1217 — confirm this matches the `> 5` floor `split.c:1189`
  hardcodes today, which should become a call into the shared
  `CanWeReduceOrPruneMove` instead of staying hand-rolled). Getting this
  wrong silently changes LMP/LMR aggressiveness with no assert to catch
  it.
- **`fThreat` must be plumbed through `g_SplitInfo`.** `CanWeReduceOrPruneMove`
  takes `fThreat` as a real gating input (searchsup.c:783) but
  `chess.h:1612-1662`'s `SPLIT_INFO` struct has no such field today — add
  one, populated by the originating thread at split-launch time (same
  pattern as `iEval`/`iImprovement`), or `HelpSearch()` can't call the
  real gate at all.
- **Attack snapshots are real parameters, not internally zeroed.** This is
  the fix for the degraded-hang-estimate gap above: `HelpSearch()` must
  start passing real snapshots instead of the zeroed
  `bbNoMinorAttacksSnapshot`/`bbNoRookAttacksSnapshot` it uses today
  (split.c:1215-1216). Requires extending `g_SplitInfo[]` to carry
  `bbMinorAttacksSnapshot`/`bbRookAttacksSnapshot` from the originating
  thread (already computed in `Search()` before `StartParallelSearch`).
  **Open risk, worth raising with the user explicitly (not just noting):**
  once the kernel is shared, `FH_TABLE_COLLECTION`'s sampling
  (search.c:1323-1365) fires from helper threads too. If step 4 (unify)
  lands before step 5 (real snapshots), those samples get logged with
  zeroed snapshots — training the joint FH% table on degraded inputs, not
  just giving `HelpSearch()` a degraded *decision*. **Recommendation: land
  step 5 together with step 4, not as a follow-up**, or gate
  `FH_TABLE_COLLECTION`'s increments to the originating thread only
  (`ctx->uPly` vs. some "is this a split helper" check) until step 5 lands.
  Ask the user which they'd rather do before step 4.
- **Return value is an enum, not control flow via `goto`.** The kernel
  can't `goto end`/`goto no_more_moves`/`continue` — those targets don't
  exist in the extracted function. Each caller's own loop dispatches on
  the enum: `Search()` on `PRUNED` does `continue` (and must NOT touch
  `iCumulativeExtend`, see the sequencing trap above); on `ABORTED` it
  does its `goto end` with `iBestScore = iScore`; `HelpSearch()` on
  `ABORTED` does `break`. The abort *condition* itself also differs
  (`WE_SHOULD_STOP_SEARCHING` vs. `g_SplitInfo[u].fTerminate`) — stays a
  caller-side check made around the kernel call, not a predicate pushed
  into it.

## Suggested sequencing

0. **Housekeeping**: confirm whether `fAnyMoveEFPPruned` (search.c:1851)
   can still be set anywhere post-EFP-removal; if dead, delete it rather
   than carry it into the shared kernel's scope. Small, standalone.
1. **Standalone fix**: `iExtensionAmount`'s two bugs in `split.c` (wrong
   slot + stale-on-skip, see Motivation above) — write
   `ctx->sPlyInfo[ctx->uPly - 1].iExtensionAmount = iExtend` unconditionally,
   every iteration, matching `search.c:1386`'s already-fixed convention.
   Commit on its own, verified via `precommit_check.sh`.
2. **Extraction**: pull the kernel out of `search.c` into a new shared
   header (`search_inline.h`, `FORCEINLINE` across translation units
   requires a header), make `Search()` call it, with `HelpSearch()`
   untouched (still running its own inline copy, including its own
   gap-riddled gate). This isolates "did the extraction change
   `Search()`'s behavior" from "did unifying the two callers change
   `HelpSearch()`'s behavior." Resolve the instrumentation-placement
   question (PLY_INFO fields vs. diagnostics struct) as part of this
   step, before writing the header.
3. **`g_SplitInfo` plumbing**: add `fThreat` and the two attack-snapshot
   bitboards to `SPLIT_INFO` (chess.h), populated at split-launch time.
   Do this *before* step 4, not after — see the `FH_TABLE_COLLECTION`
   risk above.
4. **Unification**: make `HelpSearch()` call the same kernel via the real
   `CanWeReduceOrPruneMove()` gate (replacing its hand-rolled 7-condition
   version) and `ShouldLatePrune`, removing its inline copy entirely. This
   is the commit that actually changes `HelpSearch()`'s behavior — it
   gains LMP, the full 9-check+2-exemption gate, and real attack
   snapshots, all at once, since step 3 already landed the plumbing they
   need.

## Verification plan

Standard gates at every step (`precommit_check.sh` — `TEST=1` self-test
suite + `debug_smoke_test.sh`), plus:

1. **Isolate the single-threaded path first (after step 2).** Force
   `g_uNumHelpersAvailable = 0` (no split ever fires) and confirm **node
   counts are bit-identical to HEAD** on the three curated suites
   (`ecm_ringers`, `ecm_confident_quick`, `ecm_hard_quick`) at a fixed `sd`
   depth, per the `head_reference` protocol in CLAUDE.md. This should be a
   pure refactor at this stage — "no change whatsoever," not "no
   significant change." Any node-count delta here is a real extraction
   bug, not noise. Watch specifically for the two sequencing traps above
   (`iCumulativeExtend` on the prune path, `WE_SHOULD_STOP_SEARCHING`
   ordering) — those are exactly the kind of thing that produces a subtle
   node-count drift instead of a crash.
2. **After step 4, re-enable helpers and compare separately**, expecting a
   real difference this time (`HelpSearch()` now has LMP, the full gate,
   and real snapshots it didn't have before). Compare solve counts and
   fail-high rates across the three curated suites per CLAUDE.md's
   existing methodology (measure the pick, not just the game). Rebuild
   `head_reference/` as the new baseline once this change is committed.
3. Run the full `precommit_check.sh` gate before every commit in the
   sequence above, not just at the end — this is a search/move-generation
   change throughout.

## Performance: `Search()` is the current profiler hotspot

Confirmed with the user: `Search()` is the single hottest function in the
program right now. That changes the risk profile of this refactor from
"pure correctness/maintainability" to "must not cost NPS" — a few concrete
implications for how to do each step:

- **`FORCEINLINE` is load-bearing, not decorative, here.** The whole
  point of extracting into a header function instead of a normal
  `.c`-file one is that the compiler can fully inline `SearchOneMove` at
  both call sites and optimize it in the context of each caller's
  surrounding code (register allocation across the call, dead-branch
  elimination of whichever `#ifdef` blocks aren't compiled in) exactly as
  if the code were still written inline. If it isn't actually inlined in
  the shipping `GENETIC=1 PERF_COUNTERS=1 MP=1 SIXTYFOUR=1` build, this
  refactor becomes a real regression (a non-inlined call in the hottest
  function in the program), not a neutral one. Don't just assert
  `FORCEINLINE` and move on — check post-step-2 that `clang` actually
  inlines it (`-Rpass=inline`/`-Rpass-missed=inline`, or inspect
  `nm`/disassembly for a surviving `SearchOneMove` symbol) before trusting
  the bit-identical-node-count gate alone; a node-count match doesn't
  prove NPS didn't drop.
- **Don't let the diagnostics-boundary decision regress the hot path.**
  The "instrumentation problem" section above already flags that several
  locals need to cross the kernel/caller boundary. For the fields that
  move into `ctx->sPlyInfo[ctx->uPly - 1]`: writing them is already in
  the hot path today (`iExtensionAmount` already lives there), so this is
  likely free. For anything kept as an `OUT` diagnostics struct instead:
  every field in that struct gets written on every move in the
  `PERF_COUNTERS`/`FH_TABLE_COLLECTION`-eligible path even when the
  calling code only reads a couple of them, and the struct itself is a
  stack object passed by pointer — prefer the `PLY_INFO`-field approach
  wherever a field is genuinely per-ply state (most of them), and reserve
  an `OUT` struct only for values with no natural per-ply home. This is
  exactly the tradeoff the "instrumentation problem" section says to
  resolve before writing code — performance is now part of *why* that
  decision matters, not just design cleanliness.
- **Don't widen the non-`PERF_COUNTERS` build's hot path.** The
  `SearchOneMove` signature above is sized for the worst case (every
  diagnostic input). In a release build with none of those macros
  defined, make sure the corresponding parameters either compile away
  entirely (same `#ifdef`-sectioning convention the rest of this file
  already uses) or are proven by the compiler to be dead weight — don't
  let `uRawDepthB`/`uRawImproveB`/the snapshots turn into always-live
  arguments on every call when the only consumers are instrumentation
  that's compiled out. Verify by comparing generated code size/a quick
  NPS run of a `PERF_COUNTERS`-undefined build before and after step 2,
  not just the instrumented build used for the suite gates.
- **Opportunistic, in-scope wins to look for while the code is open**
  (don't go hunting outside this refactor's diff, but don't ignore an
  obvious one either, since the whole per-move span is being rewritten
  once regardless): any snapshot/bucket value currently recomputed
  per-move that's actually loop-invariant per node (the doc's
  `uRawDepthB`/`uRawImproveB` hoist is already one example carried over
  from the current code — check for others while rewriting this block,
  e.g. whether `GetMoveFailHighPctThousandths(mv, &uFHAttempts)` or the
  joint-table lookup have any sub-computation that's the same across
  moves at a node and is currently being redone); and whether the
  diagnostics-struct-vs-PLY_INFO choice above can also drop a redundant
  write (e.g. if a value is written to both a local and `pi->` today,
  keeping only the `pi->` copy and reading it back removes a stack
  write). Treat these as reviewed, measured changes (node-count +
  NPS-on-`head_reference`-suite comparison), not assumed-safe
  micro-optimizations — a performance claim needs the same before/after
  evidence a correctness claim does here.
- **Verification gate, added to the existing plan**: alongside the
  bit-identical node-count check in step 2's isolation gate, also record
  wall-clock NPS for the same `sd`-depth suite runs, before and after
  each step, on this box (which the project's own CLAUDE.md already
  warns is noisy under shared load — do a back-to-back A/B, not a single
  run, per the Environment notes). A refactor that's node-count-identical
  but measurably slower per node is a regression this plan must not ship
  silently.

## Open question for the user

Whether to gate `FH_TABLE_COLLECTION`'s sampling to the originating
thread only until step 3's snapshot plumbing lands, or accept a short
window (within the same commit sequence, steps 3+4 landing together) where
no helper-thread sample is ever collected with zeroed snapshots because
the plumbing and the unification land atomically. Recommendation above is
the latter (land 3 and 4 together) — flagging here so it's a decision, not
an assumption.