# Replacing the loopy mobility chain-walks with single-probe magic bitboards ## Motivation `_EvalBishop`/`_EvalRook`/`_EvalQueen` currently compute mobility (and the king-safety x-ray bitboards) via an unbounded `for (;;)` chain walk that repeatedly recomputes `_RookAttacksBB`/`_BishopAttacksBB` with newly- discovered blockers excluded, to handle batteries (friendly R/Q stacked behind each other) and x-ray-through-high-value-enemy-pieces. Crafty does this with one magic-bitboard probe and a popcount. Goal: match that for speed while keeping the signal that actually matters for eval quality. Approximate parity, not exact parity -- see the tradeoffs below, all explicitly agreed rather than accidental. ## What's being thrown away, deliberately 1. **Battery mobility/connectivity through more than one hop.** Today, a rook stacked three deep behind two friendly rooks on an open file gets mobility and connected-rook credit for every square and every blocker in the stack. After this change, each rook only sees its own first blocker. The squares/credit "lost" at the near rook are not actually lost from eval overall -- the rook(s) further out credit those same squares on their own pass. Confirmed via the king-safety-xray analysis: the only case where continuing past a friendly blocker added information nothing else already had was the enemy-GE case below. 2. **Mobility credit for squares beyond an enemy queen/king (or, for bishop, enemy rook) that the piece is directly attacking.** This was never "real mobility" in the legal-move sense anyway -- a rook cannot physically move past a piece it would capture in one ply. Dropping it is a correctness fix that happens to fall out of the simplification, not a loss. (Confirmed, no objection -- see open question 6, closed.) 3. **The general multi-layer x-ray bitboard** (`bbMinorXrayAttacks`/ `bbRookXrayAttacks`/`bbQueenXrayAttacks`), replaced by a narrower, cheaper mechanism (below) that preserves the one case that matters: rook/bishop/queen pointed at the enemy king (or its ring) through exactly one enemy queen/king (or, for bishop, rook) blocker. ## What's being preserved - The existing "real mobility" masks (`bbUnsafeForRook`, `bbUnsafeForMinor`, `bbUnsafeForQueen` -- squares where a cheaper enemy piece would recapture for free) are untouched. These already encode "real mobility" exactly as wanted; nothing new needed here. - The deferred low-mobility re-derivation in `_EvalTrappedPieces` is untouched -- it only consumes a `bbMobility` snapshot and `pos->bbKingAttacks[xColor]`, neither of which cares how the snapshot was computed. - The king-ring x-ray signal for `_EvalKingSafety` (the skewer/pin-adjacent "rook/bishop/queen threatens through the enemy queen/king" case) is preserved, just computed more cheaply (below). - Blocking semantics for the x-ray check exactly match what the chain walk does today: any pawn or minor piece fully blocks (no special-casing of rammed vs. transient pawns -- that would have been *new* behavior, not preserved behavior, and we're explicitly not adding it). Friendly R/Q and the piece's enemy-GE set (queen/king for rook and queen; rook/queen/king for bishop) are the only things that don't block. ## Per-piece-type design ### Bishop / Rook (mobility) ``` bbAttack = _{Bishop,Rook}AttacksBB(c, pos->bbOccupied); bbMobility = (bbAttack & ~bbOccupied & ~bbUnsafe) | (bbAttack & bbEnemySame) | (bbAttack & bbEnemyGE) | (bbAttack & bbEnemyLE & ~bbUnsafe); // bishop's transient-pawn case folds in here uTotalMobility = FastCountBits(bbMobility); pos->bb{Minor,Rook}Attacks[uColor] |= bbAttack; ``` One magic probe, no loop. Same masks as today, just applied to the single first-blocker attack set instead of a chain-extended one. ### Queen (mobility) Two probes (rook-direction + bishop-direction), same mask logic, no per-probe chain: ``` bbAttack = _RookAttacksBB(c, occ) | _BishopAttacksBB(c, occ); bbMobility = (bbAttack & ~occ & ~bbUnsafeForQueen) | (bbAttack & bbEnemyGE) | (bbAttack & bbEnemyLE & ~bbUnsafeForQueen); pos->bbQueenAttacks[uColor] |= bbAttack; ``` ### Connected-rook bonus Direct-attack-only, no chain: ``` bbConnected = bbAttack & pos->bbPieces[uColor][ROOK]; // fire EVAL_TERM per bit, horiz/vert exactly as today (RANK(c)==RANK(cBlocker)) ``` ### King-ring x-ray (replaces bbXXXXrayAttacks' chain-walk population) Computed inside each piece's own eval pass (not moved into `_EvalKingSafety` -- that function's consumer code at eval.c:5216-5248 is unchanged), gated so the common case (no enemy GE piece directly attacked) costs nothing beyond an AND against a bitboard already in hand: ``` bbSeenEnemyGE = bbAttack & bbEnemyGE; // already computed above for mobility -- free bbXray = 0; while (bbSeenEnemyGE) { sq = pop a bit; bbXray |= _{Bishop,Rook}AttacksBB(c, occ & ~BBSQUARE[sq]); } pos->bb{Minor,Rook,Queen}XrayAttacks[uColor] |= bbXray; ``` - Rook: `bbEnemyGE` = enemy queen | enemy king -- at most 2 extra probes, almost always 0. - Bishop: `bbEnemyGE` = enemy rook | queen | king -- at most 3 extra probes, almost always 0. - Queen: same as rook, applied per axis. - One probe per GE piece directly attacked is sufficient -- if removing that single blocker reveals the king/ring, we're done; we never need a second layer, since the only thing consumed downstream is ring-square membership, not an arbitrarily deep battery. - No `g_VectorDelta`/ring-square enumeration needed anywhere -- the gate is "was this enemy GE square already in my direct attack bitboard," which is free, not "check every ring square against every enemy piece," which would have been the expensive shape. ## Order / plumbing No change to eval call order (pawns -> knights/bishops -> rooks -> queens -> king, per `Eval()`'s existing sequence) and no change to where results land on `POSITION` (`bbMinorAttacks`/`bbRookAttacks`/`bbQueenAttacks`/ `bb{Minor,Rook,Queen}XrayAttacks`, all `[2]`-indexed by color, already there). Knight needs no change -- it was never loopy to begin with (single-hop `g_KnightAttacksBB` + mask). ## Validation plan - `gmake TEST=1` + `debug_smoke_test.sh` first (asserts on mobility bounds like `ASSERT(uTotalMobility <= 14)` still need to hold). - Then the three curated suites (`ecm_ringers`/`ecm_confident_quick`/ `ecm_hard_quick`) at fixed `sd`, compared against `head_reference/` -- expect small, explainable deltas (battery/overcount cases), not a cliff. If solve counts move more than noise-level, suspect the x-ray gating logic (an enemy GE piece not being re-detected) before suspecting the mobility masks (those are a straight port). - `eval_tune/`'s DNA re-tune is not required before landing this (mobility *tables* themselves are unchanged, only how the bitboard feeding them is computed), but worth a sanity check with `evaldna dump` before/after on a few batteries/pin positions by hand if anything looks off.