path: root/src/board_representation/MIGRATION.md

# Migration plan: bitboard-backed `GetAttacks` and `CountKingSafetyDefects`

**Status: section 1 (and its correctness gate, section 2) implemented,
verified, uncommitted on disk. Sections 3-8 not started.** See the
per-section status notes below for specifics.

Context: a prior pass of this session added occupancy-bitboard-driven
mobility/attack-presence bitboards (`bbPawnAttacks`, `bbMinorAttacks`,
`bbRookAttacks`, `bbQueenAttacks`, `bbKingAttacks`, plus xray variants) to
`POSITION`, rebuilt from scratch inside every `Eval()` call, additive
alongside the pre-existing per-square `rgSquare[c|8].bvAttacks` mailbox
struct. Measured via a dedicated `evalcycles` command (rdtsc-based,
compared against a `git worktree` build of pre-migration HEAD, since none
of this work was committed): the new code is **17-41% slower per `Eval()`
call**, consistently, across 5 representative positions. Root cause: pure
duplication -- every mobility function still does the original mailbox
ray-walk *and* now also writes the bitboards, so every position pays for
both representations and nothing was ever removed to pay for it.

That result reframed the question: the win isn't "add more bitboards to
Eval," it's picking the *right* bitboards in the *right* place. This
document is the plan for that -- two functions sharing one new bitboard
primitive:

1. **`GetAttacks`** (the SEE support routine in `see.c` / `x86.asm` /
   `x64.asm`), called far more often per node than `Eval()` -- every
   capture move considered in move ordering, at every node, via
   `generate.c`'s 5 call sites and `searchsup.c:365`.
2. **`CountKingSafetyDefects`** (`eval.c:2408`), which turns out to be an
   even more pervasive case of the same problem: it's called not just
   from `Eval()` (`eval.c:7386-7387`, `eval.c:2549-2550`) but directly
   from search-tree pruning/extension decisions -- `search.c:1252`,
   `searchsup.c:484`, `searchsup.c:902,905` -- meaning it runs at search
   nodes regardless of whether `Eval()` is even reached at that node.

Both do the exact same thing algorithmically: walk every one of a side's
non-pawn pieces with a geometry-table lookup (`CHECK_VECTOR`) and, for
sliders, a manual mailbox ray-walk, to answer "does this piece attack (or
point at) this particular square" -- `GetAttacks`'s target is the move's
destination square, `CountKingSafetyDefects`'s target is the king's
square. O(pieces) candidates x O(ray length), every call, regardless of
how close any given piece actually is to the target square. Both are
strong candidates for the same fix, because both reduce to the same
underlying query: "which of this side's pieces attack square X."

## -1. Current repo state: what's committed, what's stashed

As of this writing, `HEAD` (`5c8d794`) has the keep-worthy pieces from
the abandoned attack-presence-bitboard work already committed on their
own: the `bitboard.c` passed-pawn bit-clear fix, the `search.c`/
`searchsup.c` LMR-gate-to-caller refactor plus its matching `split.c`
fix, and *only* the `CountBits`/`CoorFromBitBoardRank8ToRank1`/
`CoorFromBitBoardRank1ToRank8` inlining block in `eval.c` (the
`_FastFirstBit`/`_FastLastBit` pair from the same block was PoC-only --
no production call sites -- and was left out, since keeping it would
leave an unused-function warning once the PoC code it served is gone).

Everything else from that work -- the `bbPawnAttacks`/etc. `POSITION`
fields, all the `eval.c` reader-migration and mobility-function
production code built on them, the `RunEval{Rook,Bishop,Queen,Knight}AB`
PoC harnesses and their `command.c` entries -- is **not on disk**. It's
sitting in `git stash@{0}` ("eval bitboard reader-migration work
(measured 17-41% slower) + PoC harnesses + reusable data.c ray tables +
command.c evalcycles"), deliberately left there rather than popped back,
since most of it isn't wanted.

Two things were wanted out of that stash for this plan, and **have now
been pulled** (done, not just planned):

- **`data.c`** (clean, additions-only diff): `g_RookRayToEdge`/
  `g_BishopRayToEdge`/`g_KnightAttacksBB` + their `Initialize*` functions
  -- pulled whole-file via `git checkout stash@{0} -- data.c`, builds
  clean.
- **`main.c`**'s 3-line addition calling those three `Initialize*`
  functions from the startup sequence -- pulled the same way, alongside
  `data.c`.
- **`chess.h`**'s `extern` declarations for the above (7 lines: the two
  ray-to-edge tables + their delta/direction arrays, `g_KnightAttacksBB`,
  and the three `Initialize*` prototypes) -- hand-copied rather than
  checked out, since `chess.h`'s stashed diff also carries the unwanted
  `bbPawnAttacks`/etc. `POSITION` fields and PoC function prototypes. Only
  the 7 wanted lines were added, next to the existing `BBADJACENT_RANKS`
  externs.
- `command.c`'s `evalcycles` command was **not** pulled yet -- still
  sitting in the stash, still wanted eventually (section 5 needs the same
  shape for `getattacksbench`/`kingdefectsbench`), just not needed until
  that section starts. Extraction instructions unchanged from before:
  `git diff stash@{0}^ stash@{0} -- command.c`, take only
  `EvalCyclesCommand` and its command-table entry, leave
  `evalrookab`/etc. behind.

`eval.c` was correctly left alone -- its stashed diff includes the
inlining block already committed, so pulling it would conflict. Nothing
from section 3 onward has touched `eval.c`/`see.c` yet; when it does,
use the stashed `eval.c` only as *reference* for the ray-walk pattern
(already proven correct there -- `RunEvalRookAB` et al. verified 0
mismatches), not as something to check out.

Also present in the stash, independent of all of the above and not
needed for this plan: a small `uNumSplits`/`uNumSplitsTerminated`
split-statistics counter/reporting addition spanning `chess.h`,
`root.c`, and `script.c`. Harmless and separable, but tangential --
leave it in the stash unless it's wanted on its own merits later.

## 0. Scope and non-goals

In scope: add incrementally-maintained per-color, per-piece-type location
bitboards to `POSITION`, and a bitboard-driven "who attacks square X"
primitive that both `GetAttacks` and `CountKingSafetyDefects` consume.

Explicitly not in scope: changing `MOVE`'s `cFrom:8`/`cTo:8` encoding or
`COOR`'s `0x88` numbering. That would shrink `g_HistoryCounters`,
`g_iPSQT`, `g_ContinuationHistory`, and the countermove table
(`COUNTER_MOVE_TABLE_SIZE`) since they're all keyed directly off raw
`COOR`/`MOVE` bits sized to `0x88`'s wasted range -- a real win if it ever
happens, but a much bigger, separate project (touches `san.c`/`ics.c`
notation, `hash.c`'s packed move encoding, `book.c`'s format, `root.c`'s
PV printing). Ruled out for this pass; noted here only so it isn't
rediscovered and reconsidered mid-migration.

Also out of scope for this pass: touching `Eval()`'s existing
(measured-slower) attack-presence bitboards -- that's a separate
decision, addressed in section 8, not bundled with this one. Keeping
these independent means a bad result here doesn't force a revert of the
Eval work and vice versa.

## 1. New state: `bbPieces[2][8]` -- DONE

Implemented as planned, with one correction found while implementing:
there's no existing `NUM_PIECE_TYPES` constant, so it's sized `[2][8]`
to exactly match `uNonPawnCount[2][8]`'s existing convention (indices
0/1 unused for this field, 2..6 are `PIECE_TYPE`-indexed
KNIGHT/BISHOP/ROOK/QUEEN/KING, KING's slot always zero by construction).
Added to `POSITION` (`chess.h`) right after `uNonPawnCount`.

Pawns excluded (`pHash->bbPawnLocations[2]` already covers them). King
excluded (`cNonPawns[color][0]`, single square, a bitboard adds nothing)
-- enforced by only ever writing indices `KNIGHT..QUEEN` (i.e. `< KING`),
never `KING` itself.

**Maintained incrementally in `move.c`**, at all 6 non-pawn
piece-movement functions (more than the original plan's 2 sites --
`SlidePiece`/`LiftPiece`/`PlacePiece` each turned out to have a second,
`WithoutSigs` sibling used by `UnmakeMove`, not found until reading the
actual call graph):

- `SlidePiece` / `SlidePieceWithoutSigs` (simple non-capture move, and
  its unmake counterpart -- also what castling uses, twice per call, for
  king and rook) -- clear from-bit, set to-bit.
- `LiftPiece` / `LiftPieceWithoutSigs` (piece leaves the board: capture,
  or the pawn side of a promotion, or unmake-removing a
  promoted/just-placed piece) -- clear the bit. Both already branch on
  `IS_PAWN`/`!IS_KING` for other bookkeeping, so the new line drops
  straight into the existing non-pawn branch, no new conditional needed.
- `PlacePiece` / `PlacePieceWithoutSigs` (piece appears on the board:
  promotion result, or unmake-restoring a captured piece) -- set the bit.
  Same existing-branch placement as above.

Confirmed via the actual call sites (`move.c:811-828`, `:960-993`,
`:1249-1339`) that every move type -- normal, capture, both-side
castling, promotion (with or without capture), en passant, and every
undo -- routes through one of these 6 functions; nothing bypasses them
with a direct `rgSquare[].pPiece` write.

O(1) extra work per move, next to array bookkeeping already happening
there. No rebuild-from-scratch anywhere.

**From-scratch population**: `fen.c`'s piece-placement loop (the
non-king branch that already sets `cNonPawns[uColor][uIndex]`), one line
added. Zeroing is free -- `fen.c`'s `memset(p, 0, sizeof(POSITION))`
covers the new field automatically, no separate zeroing code needed.

## 2. Correctness gate on the *maintenance* side -- DONE, verified clean

Implemented in `board.c`'s existing `VerifyPositionConsistency`
(`board.c:129`), not new bespoke code, as planned: a local `bbPieces[2][8]`
accumulated in the same non-pawn piece-list walk that already builds
`uNonPawnCount[2][7]` (`|= COOR_TO_BB(c)` guarded by `!IS_KING(p)`,
right next to the existing `uNonPawnCount[u][PIECE_TYPE(p)]++`),
compared against `pos->bbPieces` in a loop next to the existing count
comparison (`KNIGHT` to `< KING`, matching `move.c`'s own range
convention), and one new `szExplainations[]` entry ("bbPieces bitboard
doesn't match piece list", reason index 21).

**Verified clean**, not just added: `gmake DEBUG=1` build has zero
warnings, and `precommit_check.sh` (`gmake TEST=1` self-test +
`debug_smoke_test.sh`) passed with the assert live. Specifically checked
that `TEST=1`'s `TestMakeUnmakeMove` (`testmove.c:454`) exercises the
edge cases that would most likely expose a missed `move.c` update site --
en passant, promotion-with-capture, and both-side castling, each
round-tripped through make+unmake with `VerifyPositionConsistency`
firing on every `Slide`/`Lift`/`Place` call in `DEBUG` builds -- and the
`bbPieces` check stayed silent throughout. Also confirmed the release
build (`GENETIC=1 PERF_COUNTERS=1 MP=1 SIXTYFOUR=1`) compiles clean and
runs a normal search correctly (the maintenance code has no `#ifdef
DEBUG` guard, matching section 6's "always on" toggle strategy).

Nothing reads `bbPieces` yet (confirmed: it's write-only outside the
`DEBUG` consistency check), so this remains pure addition with zero
behavioral risk, exactly as planned. **Not yet committed** -- sitting on
disk, verified, ready to commit whenever section 1 is considered a good
checkpoint.

## 3. New `_WhoAttacksSquareBB` primitive, consumed by two PoCs -- NOT STARTED

Everything below this point is still just the plan -- no code written yet.

Build one shared bitboard primitive rather than two independent
implementations, since `GetAttacks` and `CountKingSafetyDefects` are the
same query against different target squares:

- Pawns: existing 2-square delta check, unchanged (already O(1), nothing
  to improve).
- Knights/king: `g_KnightAttacksBB[cSquare] & bbPieces[side][KNIGHT]`
  (and the equivalent king delta check) -- O(1), reusing
  `g_KnightAttacksBB` already built and verified this session.
- Sliders (bishop/rook/queen): reuse `g_RookRayToEdge`/`g_BishopRayToEdge`
  + `_FastFirstBit`/`_FastLastBit`, walking outward from the target
  square along each ray to the nearest blocker, testing it against
  `bbPieces[side][ROOK]`/`[BISHOP]`/`[QUEEN]` (queens checked on both ray
  sets). Needs `bbOccupied` (both colors, all pieces) to find the
  blocker -- construct as `bbPieces[WHITE][*] | bbPieces[BLACK][*] |
  pHash->bbPawnLocations[*] | king bits`, now cheap (all pre-maintained)
  rather than a `cNonPawns` walk.

Two call-site wrappers, each a PoC alongside the real thing (same pattern
as this session's earlier `_EvalRookOccupancyBB` PoC work), gated so old
and new are both callable side by side:

- **`_GetAttacksBB`** (`see.c`): calls the primitive against the move's
  destination square, populates a `SEE_LIST` exactly like `GetAttacks`
  does today. No pin-detection, no en-passant handling -- matching
  `GetAttacks`'s exact (deliberately approximate) semantics. Not
  introducing new behavior, just recomputing the same answer differently.
- **`_CountKingSafetyDefectsBB`** (`eval.c`): calls the primitive against
  the king's square, feeding the same `CHECK_VECTOR`-derived defect-count
  logic `CountKingSafetyDefects` already has (`uPiecesPointingAtKing`
  bookkeeping included) -- only the "which enemy pieces bear on this
  square" step changes, the counting/scoring logic downstream of it
  doesn't.

`CountKingSafetyDefects` doesn't build a `SEE_LIST` at all (it just
counts and classifies), so it isn't a second consumer of `_GetAttacksBB`
directly -- it's a second consumer of the lower-level per-piece-type
bitboard scan the two share. Structure the primitive so it can return
either "the raw attacker bitboard per piece type" (what
`CountKingSafetyDefects` wants, to test `CHECK_VECTOR`-equivalent
conditions itself) or "a populated `SEE_LIST`" (what `GetAttacks` wants),
rather than forcing one call shape on both.

## 4. Correctness verification

Confirmed before writing this plan: `SEE()` sorts/heaps the attacker list
immediately after `GetAttacks` returns (`see.c:872-878`,
`_BuildHeap`/`_SortList`), so a bitboard-based `GetAttacks` returning
attackers in a different order than the mailbox version is fine --
correctness only requires the *set* of attackers to match, not the
sequence.

1. **Fix `SeeListsAreEqual` to be order-independent first**
   (`testsee.c:139`) -- sort both lists by `(cLoc, pPiece)` before the
   field-by-field compare, or compare as multisets. Do this as its own
   tiny commit; verify it still passes against the existing
   Slow-vs-asm comparison (order shouldn't change there, so this change
   should be provably a no-op in isolation before it's relied on for
   anything new).
2. **Extend `TestGetAttacks`** (`testsee.c:154`) to add `_GetAttacksBB`
   as a third comparison against the same 20,000 random-position x
   every-square x both-colors sweep already in place
   (`GenerateRandomLegalPosition`). This is the primary correctness
   gate -- cheap to run (`gmake TEST=1`), already wired into the batch
   self-test startup path.
3. **Add an equivalent random-position test for
   `_CountKingSafetyDefectsBB`**, same 20,000-position generator, both
   colors, comparing its returned defect count *and* the
   `uPiecesPointingAtKing` side-effect against `CountKingSafetyDefects`.
   No existing harness to extend here (unlike `GetAttacks`), so this is
   new test code in the `TEST=1` build, following `TestGetAttacks`'s
   shape.
4. **`precommit_check.sh`** as always, for the crash/assert layer.
5. **SEE-value diffing at the position level**: since `SEE()` returns a
   single integer per move (not a board eval), the equivalent of the
   Eval work's "150-position score-identity diff" is a diagnostic
   command (`seescores`, analogous to the batch `eval` dumps used
   earlier) that computes `SEE()` for every legal capture in a batch of
   ECM/random positions, run once per `GetAttacksBB` toggle state,
   diffed. Catches any behavioral drift `TestGetAttacks`'s raw-list
   comparison might miss once results feed into `_MinLegalPiece`'s
   exchange simulation. Do the same for `CountKingSafetyDefects`: a
   `kingdefects` diagnostic command dumping the defect count for both
   kings across the same position batch, diffed the same way -- this one
   matters more than it sounds, since the count feeds directly into
   `Eval()`'s king-safety score term (`eval.c:2549-2550`), not just
   pruning gates.
6. **Full-suite behavioral check is mandatory here, not optional** --
   this is the one place this migration is *riskier* than the Eval
   constant work: `GetAttacks` feeds move ordering and pruning decisions
   (`generate.c`'s 5 call sites, `searchsup.c:365`), and
   `CountKingSafetyDefects` feeds pruning/extension decisions directly
   (`search.c:1252`, `searchsup.c:484,902,905`) *in addition to* an
   Eval() score term -- so even value-for-value-identical results can
   shift which move gets tried first or which lines get pruned/extended,
   changing node counts and occasionally search results at the margins.
   Run all three curated suites (`ecm_ringers`, `ecm_confident_quick`,
   `ecm_hard_quick`) at `sd10` against `head_reference/`, and don't treat
   a clean `TestGetAttacks`/`_CountKingSafetyDefectsBB` unit-level pass
   as sufficient sign-off by itself -- `CountKingSafetyDefects`'s direct
   search-code call sites make this the higher-risk of the two changes,
   despite being the simpler one to implement.
7. **`match_play.py` gate** (`LOWER95 >= 0.5`) before calling this done
   -- same reasoning: this is closer to a search-behavior change than a
   pure eval-magnitude change, so the existing eval-tuning gate criteria
   apply. Run once with both migrations landed together (they share the
   same underlying primitive, so testing them jointly is representative
   of how they'll actually ship) plus, if the combined match shows a
   problem, one more isolating each toggle independently to attribute it.

## 5. Microbenchmarking

The Eval cycle measurement earlier this session is the cautionary tale:
an isolated PoC can look plausible and still lose once integrated,
because integration costs (dual maintenance, extra indirection) aren't
visible in isolation. Two tiers, both required before wiring in:

1. **Isolated cycles/call**, same `SystemReadTimeStampCounter` pattern
   as `evalcycles`/`RunEvalRookAB`: a `getattacksbench [iterations]`
   command looping old vs. new `GetAttacks` on the *current*
   position/square, and a `kingdefectsbench [iterations]` command doing
   the same for `CountKingSafetyDefects`, interleaved (old/new/old/new)
   to cancel shared-box noise, run across a battery of positions spanning
   piece density -- opening (~30 pieces), middlegame (~20), endgame
   (~8) -- since the algorithmic win should scale *with* piece count, and
   a flat or inverted result across that spectrum is a red flag before
   proceeding further, exactly like the rook/bishop Eval win that didn't
   hold up once integrated.
2. **Whole-engine cycles-per-node / NPS**, not just the isolated call:
   `sd`-fixed-depth comparison against `head_reference` on the three
   curated suites, using the engine's own self-reported `Searched for N
   seconds, M nodes` (not `ps` sampling -- noisy on this shared box per
   earlier sessions). This is the check that would have caught the Eval
   regression earlier if it had been run before the reader-migration
   work proceeded -- don't skip straight from isolated-cycles-looks-good
   to production wiring again. Given `CountKingSafetyDefects`'s search-code
   call sites, this whole-engine number is where its win (or lack of one)
   will actually show up -- its isolated per-call cycle count matters
   less than `GetAttacks`'s does, precisely because it's called from more
   places than just move ordering.

## 6. Dual-support / toggle strategy

Same `#define` pattern already established for the Eval occupancy work
(`ROOK_OCCUPANCY_EVAL` et al.): `GETATTACKS_BITBOARD`, flipping which
implementation `chess.h`'s `GetAttacks` macro/prototype resolves to
(alongside the existing `CROUTINES` old/new(asm) switch -- this becomes a
three-way choice: `SlowGetAttacks` (C mailbox), asm `GetAttacks` (x86/x64
mailbox), `_GetAttacksBB` (new)). A second, independent toggle,
`KINGSAFETY_BITBOARD`, does the same for `CountKingSafetyDefects` vs.
`_CountKingSafetyDefectsBB` -- independent so each can be measured,
gated, and (if needed) rolled back on its own, even though they share the
underlying `_WhoAttacksSquareBB` primitive.

`bbPieces` maintenance itself is **always on** regardless of either
toggle -- it's cheap enough that gating it adds complexity for no
benefit, and other future work (see section 8) can build on it once
trusted.

## 7. Retirement criteria for the old mailbox implementations

Only delete `SlowGetAttacks`/asm `GetAttacks` after **all** of:

- Extended `TestGetAttacks` clean across the 20,000-position sweep.
- Isolated cycles/call shows a consistent win across the piece-density
  spectrum (not just one favorable position).
- Whole-engine `sd10` on all three curated suites shows no solve-count
  regression vs. `head_reference`.
- `match_play.py` gate clears `LOWER95 >= 0.5`.
- `head_reference/` rebuilt as the new baseline once landed.

Only delete the old `CountKingSafetyDefects` mailbox body after the same
five criteria, evaluated against *its* test/bench additions -- do not
retire it just because `GetAttacks`'s migration cleared its own bar; they
share a primitive but are independently gated per section 6, and
`CountKingSafetyDefects`'s wider call-site footprint (search-code pruning
gates, not just move ordering) makes it the one more likely to surface a
problem only visible in full search behavior, not in the unit-level
correctness test.

One easy win to check first, independent of all this: confirm whether
`x86.asm`'s `GetAttacks` is even compiled into the `SIXTYFOUR=1` release
profile at all (`GNUmakefile`) -- if it's already dead on this 64-bit-only
box, that's a zero-risk deletion to do up front, separate from the
migration.

## 8. What this means for the existing (measured-slower) Eval bitboards

Not bundling a decision here, but flagging it: once `bbPieces` exists and
is trusted, it's a cheaper substrate than what the current
`bbPawnAttacks`/`bbMinorAttacks`/`bbRookAttacks`/`bbQueenAttacks`/
`bbKingAttacks` work does today (rebuild-from-scratch per `Eval()` call).
Worth revisiting *after* this migration lands -- either reimplementing
the attack-presence bitboards on top of `bbPieces` + ray tables cheaply,
or reverting them if `bbPieces` alone doesn't end up mattering for Eval.
Separate decision, separate correctness/benchmark cycle, not this one.