summaryrefslogtreecommitdiff
path: root/src/generate.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/generate.c')
-rwxr-xr-xsrc/generate.c1562
1 files changed, 1556 insertions, 6 deletions
diff --git a/src/generate.c b/src/generate.c
index 09e3e0a..69e431f 100755
--- a/src/generate.c
+++ b/src/generate.c
@@ -728,6 +728,211 @@ GenerateWhiteKnight(IN MOVE_STACK *pStack,
}
//
+// board_representation/MOVEGEN_MIGRATION.md section 3 step 1: bitboard
+// knight generator, the pilot function for the whole migration --
+// lowest risk, most precedented (reuses g_KnightAttacksBB, already
+// built and verified for GetAttacks, no new tables needed). Unlike the
+// mailbox pair above, one function serves both JumpTable slots
+// (BLACK_KNIGHT and WHITE_KNIGHT) -- GenerateWhiteKnight's
+// GET_COLOR(p)==BLACK bit trick was purely a mailbox micro-
+// optimization exploiting how BLACK happens to be encoded; a bitboard
+// lookup needs no such color-specific shortcut, it just ANDs off
+// whichever side's occupancy pos->uToMove identifies.
+//
+// Full-board occupancy, both sides -- same formula as see.c's static
+// _BuildOccupiedBB (a separate copy, not shared, since that one is
+// file-local to see.c and this module's own convention keeps its
+// bitboard helpers together). Needed by the slider magic-bitboard
+// generators (_GenerateRookBB/_GenerateBishopBB) to index into
+// g_RookAttackTable/g_BishopAttackTable -- see MOVE_STACK's
+// bbOccupied field comment in chess.h. Non-static so testgenerate.c's
+// harness can call it directly.
+BITBOARD
+_BuildFullOccupiedBB(IN POSITION *pos)
+/**
+
+Routine description:
+
+ Full-board occupancy bitboard (both colors, every piece including
+ pawns and kings).
+
+Parameters:
+
+ POSITION *pos
+
+Return value:
+
+ BITBOARD
+
+**/
+{
+ return (pos->bbPieces[WHITE][KNIGHT] | pos->bbPieces[WHITE][BISHOP] |
+ pos->bbPieces[WHITE][ROOK] | pos->bbPieces[WHITE][QUEEN] |
+ pos->bbPieces[BLACK][KNIGHT] | pos->bbPieces[BLACK][BISHOP] |
+ pos->bbPieces[BLACK][ROOK] | pos->bbPieces[BLACK][QUEEN] |
+ pos->bbPawns[WHITE] | pos->bbPawns[BLACK] |
+ COOR_TO_BB(pos->cNonPawns[WHITE][0]) |
+ COOR_TO_BB(pos->cNonPawns[BLACK][0]));
+}
+
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: raw
+// magic-table lookups, factored out of _GenerateRookBB/_GenerateBishopBB
+// so _ComputeCheckTargetMaskBB (below) and the Part B SaveMe*BB
+// functions can reuse them without duplicating the index arithmetic a
+// third/fourth time. Non-static (unlike their original file-local
+// status) so movesup.c's section 6b ExposesCheckBB work can call them
+// too -- same convention as _BuildFriendlySideBB/_WhoAttacksSquareBB.
+BITBOARD FORCEINLINE
+_RookAttacksBB(IN COOR c, IN BITBOARD bbOccupied)
+{
+ ULONG uMagicIndex = (ULONG)
+ (((bbOccupied & g_RookOccupancyMask[c]) *
+ g_RookMagic[c]) >> g_RookMagicShift[c]);
+ return g_RookAttackTable[c][uMagicIndex];
+}
+
+BITBOARD FORCEINLINE
+_BishopAttacksBB(IN COOR c, IN BITBOARD bbOccupied)
+{
+ ULONG uMagicIndex = (ULONG)
+ (((bbOccupied & g_BishopOccupancyMask[c]) *
+ g_BishopMagic[c]) >> g_BishopMagicShift[c]);
+ return g_BishopAttackTable[c][uMagicIndex];
+}
+
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2:
+// bbTargetMask = every square a non-king move could land on to resolve
+// a lone check -- the checker's own square (a capture always resolves
+// check) OR, if the checker is a slider, every square strictly between
+// it and the king (a block also resolves check). The "squares between
+// two aligned pieces" trick costs nothing new: each square's magic
+// attack bitboard already reaches exactly to its nearest blocker in
+// every direction, so ANDing both sides' attack sets together gives
+// precisely the empty segment between them, excluding both endpoints
+// (neither piece's own attack set includes its own square). A
+// diagonally-adjacent pawn checker naturally falls out of the same
+// bishop-table branch with zero extra bits, since there is nothing
+// between two adjacent squares -- no separate pawn case needed. A
+// non-aligned (knight) checker is the only case requiring a branch:
+// DIRECTION_BETWEEN_SQUARES returns 0 for a knight offset, and there
+// is no way to block a knight's check regardless.
+static BITBOARD
+_ComputeCheckTargetMaskBB(IN COOR cKing, IN COOR cAttacker,
+ IN BITBOARD bbOccupied)
+{
+ int iDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
+ BITBOARD bbBetween = 0;
+
+ if (0 != iDelta)
+ {
+ if ((16 == iDelta) || (-16 == iDelta) ||
+ (1 == iDelta) || (-1 == iDelta))
+ {
+ bbBetween = _RookAttacksBB(cKing, bbOccupied) &
+ _RookAttacksBB(cAttacker, bbOccupied);
+ }
+ else
+ {
+ bbBetween = _BishopAttacksBB(cKing, bbOccupied) &
+ _BishopAttacksBB(cAttacker, bbOccupied);
+ }
+ }
+ return COOR_TO_BB(cAttacker) | bbBetween;
+}
+
+// Non-static so testgenerate.c's harness can call it directly to set
+// up MOVE_STACK.bbFriendlyOccupied when calling a _Generate*BB
+// function outside of _GenerateAllMoves.
+BITBOARD
+_BuildFriendlySideBB(IN POSITION *pos, IN ULONG uSide)
+/**
+
+Routine description:
+
+ Full occupancy bitboard for one side only (all piece types
+ including pawns and king) -- see.c's _BuildOccupiedBB ORs both
+ sides together for a different purpose (SEE's "is this square
+ occupied at all" query); move generation needs just one side's
+ squares, to AND off as illegal (self-occupied) destinations.
+
+Parameters:
+
+ POSITION *pos
+ ULONG uSide
+
+Return value:
+
+ BITBOARD
+
+**/
+{
+ return (pos->bbPieces[uSide][KNIGHT] | pos->bbPieces[uSide][BISHOP] |
+ pos->bbPieces[uSide][ROOK] | pos->bbPieces[uSide][QUEEN] |
+ pos->bbPawns[uSide] |
+ COOR_TO_BB(pos->cNonPawns[uSide][0]));
+}
+
+// Non-static (unlike a purely-internal helper would be) so
+// testgenerate.c's speed/correctness harness can call it directly,
+// same convention _GetAttacksBB (see.c) already uses.
+void
+_GenerateKnightBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cKnight)
+/**
+
+Routine description:
+
+ Bitboard equivalent of GenerateKnight/GenerateWhiteKnight -- called
+ by GenerateMoves' JumpTable in place of both when
+ GENERATE_KNIGHT_BITBOARD is defined. Produces the exact same
+ pseudo-legal move set (same over-generation behavior, no
+ legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's
+ explicit non-goal.
+
+ Relies on pStack->bbFriendlyOccupied already being set by the
+ caller (_GenerateAllMoves computes it once per node, before
+ dispatching to any piece type, precisely so every bitboard-backed
+ generator for that node shares one build instead of each paying
+ for its own -- see MOVE_STACK's field comment in chess.h). A
+ direct caller outside of _GenerateAllMoves (e.g. testgenerate.c's
+ harness) must set it first; the DEBUG-build ASSERT below catches
+ a stale/unset value, but only in a DEBUG build.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must
+ already be set for pos->uToMove)
+ POSITION *pos : the board position
+ COOR cKnight : the knight's location
+
+Return value:
+
+ static void
+
+**/
+{
+ BITBOARD bbDest = g_KnightAttacksBB[cKnight] & ~pStack->bbFriendlyOccupied;
+ ULONG uBitIndex;
+ COOR c;
+ PIECE p;
+
+ ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove);
+ ASSERT(pStack->bbFriendlyOccupied ==
+ _BuildFriendlySideBB(pos, pos->uToMove));
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cKnight, c, p);
+ }
+}
+
+//
// These logical AND/ORs replaced with bitwise AND/OR; the effect is
// the same the the bitwise is marginally faster.
//
@@ -803,6 +1008,68 @@ Return value:
while(0 != g_iNDeltas[u]);
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2:
+// bitboard equivalent of SaveMeKnight -- one AND against a
+// precomputed bbTargetMask replaces the per-square (c == cAttacker) ||
+// BLOCKS_THE_CHECK(c) test entirely. ExposesCheck (pin detection)
+// stays exactly as-is, unchanged, called per surviving candidate --
+// not in scope to alter, see section 6a's "what does not change."
+//
+void
+_SaveMeKnightBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cKnight,
+ IN COOR cKing,
+ IN BITBOARD bbTargetMask)
+/**
+
+Routine description:
+
+ Bitboard equivalent of SaveMeKnight -- called in place of it (via
+ a direct, statically-known call, not JumpTable) when
+ GENERATE_ESCAPES_BLOCK_BITBOARD is defined.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must
+ already be set for pos->uToMove)
+ POSITION *pos : the board position
+ COOR cKnight : the knight's location
+ COOR cKing : the friendly king's location
+ BITBOARD bbTargetMask : squares that resolve the lone check --
+ see _ComputeCheckTargetMaskBB
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbDest = g_KnightAttacksBB[cKnight] &
+ ~pStack->bbFriendlyOccupied & bbTargetMask;
+ ULONG uBitIndex;
+ COOR c, cExposed;
+ PIECE p;
+
+ ASSERT(InCheck(pos, pos->uToMove));
+ ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove);
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ cExposed = ExposesCheck(pos, cKnight, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == c))
+ {
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cKnight, c, p);
+ }
+ }
+}
+
const INT g_iBDeltas[] = {
-17, -15, +15, +17, 0 };
@@ -916,6 +1183,78 @@ Return value:
}
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 3 step 3:
+// magic-bitboard bishop generator -- mechanically identical to
+// _GenerateRookBB, swapping in the bishop's magic tables. Measured
+// speed result for rook was parity (not a win) against mailbox at
+// these small destination counts -- see that finding written up in
+// MOVEGEN_MIGRATION.md's section 3 entry; expect the same here rather
+// than a different outcome, since the underlying reason (a mailbox ray
+// walk's cost is already ~O(destination count), so magic's O(1)
+// lookup pipeline doesn't out-race it at these distances) applies
+// identically to diagonals.
+//
+void
+_GenerateBishopBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cBishop)
+/**
+
+Routine description:
+
+ Bitboard equivalent of GenerateBishop -- called by GenerateMoves'
+ JumpTable in place of it when GENERATE_BISHOP_BITBOARD is defined.
+ Produces the exact same pseudo-legal move set (same over-generation
+ behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md
+ section 1's explicit non-goal.
+
+ Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already
+ being set by the caller, same as _GenerateRookBB -- see that
+ function's header comment and MOVE_STACK's field comments in
+ chess.h.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and
+ bbOccupied must already be set)
+ POSITION *pos : the board position
+ COOR cBishop : the bishop's location
+
+Return value:
+
+ void
+
+**/
+{
+ ULONG uMagicIndex;
+ BITBOARD bbDest;
+ ULONG uBitIndex;
+ COOR c;
+ PIECE p;
+
+ ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove);
+ ASSERT(pStack->bbFriendlyOccupied ==
+ _BuildFriendlySideBB(pos, pos->uToMove));
+ ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos));
+
+ uMagicIndex = (ULONG)
+ (((pStack->bbOccupied & g_BishopOccupancyMask[cBishop]) *
+ g_BishopMagic[cBishop]) >> g_BishopMagicShift[cBishop]);
+ bbDest = g_BishopAttackTable[cBishop][uMagicIndex] &
+ ~pStack->bbFriendlyOccupied;
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cBishop, c, p);
+ }
+}
+
void
SaveMeBishop(IN MOVE_STACK *pStack,
@@ -990,6 +1329,65 @@ Return value:
while(0 != g_iBDeltas[u]);
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2:
+// bitboard equivalent of SaveMeBishop -- same pattern as
+// _SaveMeKnightBB, using the magic lookup instead of a ray walk.
+//
+void
+_SaveMeBishopBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cBishop,
+ IN COOR cKing,
+ IN BITBOARD bbTargetMask)
+/**
+
+Routine description:
+
+ Bitboard equivalent of SaveMeBishop -- called in place of it (via
+ a direct, statically-known call, not JumpTable) when
+ GENERATE_ESCAPES_BLOCK_BITBOARD is defined.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and
+ bbOccupied must already be set)
+ POSITION *pos : the board position
+ COOR cBishop : the bishop's location
+ COOR cKing : the friendly king's location
+ BITBOARD bbTargetMask : squares that resolve the lone check --
+ see _ComputeCheckTargetMaskBB
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbDest = _BishopAttacksBB(cBishop, pStack->bbOccupied) &
+ ~pStack->bbFriendlyOccupied & bbTargetMask;
+ ULONG uBitIndex;
+ COOR c, cExposed;
+ PIECE p;
+
+ ASSERT(InCheck(pos, pos->uToMove));
+ ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove);
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ cExposed = ExposesCheck(pos, cBishop, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == c))
+ {
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cBishop, c, p);
+ }
+ }
+}
+
const INT g_iRDeltas[] = {
-1, +1, +16, -16, 0 };
@@ -1104,6 +1502,77 @@ Return value:
}
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 3 step 3: magic-
+// bitboard rook generator -- the first consumer of the InitMagic()
+// infrastructure (data.c) built ahead of time for exactly this. Unlike
+// knight/king, this piece type is expected to actually win on speed:
+// the magic lookup replaces a 4-direction ray walk (up to 7 squares
+// per direction) with one multiply+shift+table lookup, independent of
+// how far the rook can see.
+//
+void
+_GenerateRookBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cRook)
+/**
+
+Routine description:
+
+ Bitboard equivalent of GenerateRook -- called by GenerateMoves'
+ JumpTable in place of it when GENERATE_ROOK_BITBOARD is defined.
+ Produces the exact same pseudo-legal move set (same over-generation
+ behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md
+ section 1's explicit non-goal.
+
+ Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already
+ being set by the caller (_GenerateAllMoves computes both once per
+ node, before dispatching to any piece type) -- see MOVE_STACK's
+ field comments in chess.h. A direct caller outside of
+ _GenerateAllMoves (e.g. testgenerate.c's harness) must set both
+ first.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and
+ bbOccupied must already be set)
+ POSITION *pos : the board position
+ COOR cRook : the rook's location
+
+Return value:
+
+ void
+
+**/
+{
+ ULONG uMagicIndex;
+ BITBOARD bbDest;
+ ULONG uBitIndex;
+ COOR c;
+ PIECE p;
+
+ ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove);
+ ASSERT(pStack->bbFriendlyOccupied ==
+ _BuildFriendlySideBB(pos, pos->uToMove));
+ ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos));
+
+ uMagicIndex = (ULONG)
+ (((pStack->bbOccupied & g_RookOccupancyMask[cRook]) *
+ g_RookMagic[cRook]) >> g_RookMagicShift[cRook]);
+ bbDest = g_RookAttackTable[cRook][uMagicIndex] &
+ ~pStack->bbFriendlyOccupied;
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cRook, c, p);
+ }
+}
+
void
SaveMeRook(IN MOVE_STACK *pStack,
IN POSITION *pos,
@@ -1177,6 +1646,65 @@ Return value:
while(0 != g_iRDeltas[u]);
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2:
+// bitboard equivalent of SaveMeRook -- same pattern as
+// _SaveMeBishopBB, using the rook magic lookup instead of a ray walk.
+//
+void
+_SaveMeRookBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cRook,
+ IN COOR cKing,
+ IN BITBOARD bbTargetMask)
+/**
+
+Routine description:
+
+ Bitboard equivalent of SaveMeRook -- called in place of it (via a
+ direct, statically-known call, not JumpTable) when
+ GENERATE_ESCAPES_BLOCK_BITBOARD is defined.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and
+ bbOccupied must already be set)
+ POSITION *pos : the board position
+ COOR cRook : the rook's location
+ COOR cKing : the friendly king's location
+ BITBOARD bbTargetMask : squares that resolve the lone check --
+ see _ComputeCheckTargetMaskBB
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbDest = _RookAttacksBB(cRook, pStack->bbOccupied) &
+ ~pStack->bbFriendlyOccupied & bbTargetMask;
+ ULONG uBitIndex;
+ COOR c, cExposed;
+ PIECE p;
+
+ ASSERT(InCheck(pos, pos->uToMove));
+ ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove);
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ cExposed = ExposesCheck(pos, cRook, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == c))
+ {
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cRook, c, p);
+ }
+ }
+}
+
void
GenerateQueen(IN MOVE_STACK *pStack,
@@ -1234,6 +1762,82 @@ Return value:
while(0 != g_iQKDeltas[u]);
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 3 step 4: queen is
+// just rook-directions OR bishop-directions combined, once step 3 is
+// solved -- no new design or new tables needed. Two magic lookups (one
+// rook-table, one bishop-table) ORed together, same
+// `_EvalQueenOccupancyBB`-flagged caution as the rest of this plan:
+// a combined single 8-ray table was tried elsewhere (the PoC in data.c
+// this migration's tables were built alongside) and measured *slower*
+// than reusing the two-pass rook/bishop structure -- don't rediscover
+// that, this deliberately does not attempt to unify the two lookups
+// into one table.
+//
+void
+_GenerateQueenBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cQueen)
+/**
+
+Routine description:
+
+ Bitboard equivalent of GenerateQueen -- called by GenerateMoves'
+ JumpTable in place of it when GENERATE_QUEEN_BITBOARD is defined.
+ Produces the exact same pseudo-legal move set (same over-generation
+ behavior, no legal-awareness added) -- see MOVEGEN_MIGRATION.md
+ section 1's explicit non-goal.
+
+ Relies on pStack->bbFriendlyOccupied and pStack->bbOccupied already
+ being set by the caller, same as _GenerateRookBB/_GenerateBishopBB
+ -- see those functions' header comments and MOVE_STACK's field
+ comments in chess.h.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and
+ bbOccupied must already be set)
+ POSITION *pos : the board position
+ COOR cQueen : the queen's location
+
+Return value:
+
+ void
+
+**/
+{
+ ULONG uRookMagicIndex, uBishopMagicIndex;
+ BITBOARD bbDest;
+ ULONG uBitIndex;
+ COOR c;
+ PIECE p;
+
+ ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove);
+ ASSERT(pStack->bbFriendlyOccupied ==
+ _BuildFriendlySideBB(pos, pos->uToMove));
+ ASSERT(pStack->bbOccupied == _BuildFullOccupiedBB(pos));
+
+ uRookMagicIndex = (ULONG)
+ (((pStack->bbOccupied & g_RookOccupancyMask[cQueen]) *
+ g_RookMagic[cQueen]) >> g_RookMagicShift[cQueen]);
+ uBishopMagicIndex = (ULONG)
+ (((pStack->bbOccupied & g_BishopOccupancyMask[cQueen]) *
+ g_BishopMagic[cQueen]) >> g_BishopMagicShift[cQueen]);
+ bbDest = (g_RookAttackTable[cQueen][uRookMagicIndex] |
+ g_BishopAttackTable[cQueen][uBishopMagicIndex]) &
+ ~pStack->bbFriendlyOccupied;
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cQueen, c, p);
+ }
+}
+
void
SaveMeQueen(IN MOVE_STACK *pStack,
@@ -1309,6 +1913,66 @@ Return value:
while(0 != g_iQKDeltas[u]);
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2:
+// bitboard equivalent of SaveMeQueen -- two magic lookups ORed
+// together, same as _GenerateQueenBB, ANDed with bbTargetMask.
+//
+void
+_SaveMeQueenBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cQueen,
+ IN COOR cKing,
+ IN BITBOARD bbTargetMask)
+/**
+
+Routine description:
+
+ Bitboard equivalent of SaveMeQueen -- called in place of it (via a
+ direct, statically-known call, not JumpTable) when
+ GENERATE_ESCAPES_BLOCK_BITBOARD is defined.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied and
+ bbOccupied must already be set)
+ POSITION *pos : the board position
+ COOR cQueen : the queen's location
+ COOR cKing : the friendly king's location
+ BITBOARD bbTargetMask : squares that resolve the lone check --
+ see _ComputeCheckTargetMaskBB
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbDest = (_RookAttacksBB(cQueen, pStack->bbOccupied) |
+ _BishopAttacksBB(cQueen, pStack->bbOccupied)) &
+ ~pStack->bbFriendlyOccupied & bbTargetMask;
+ ULONG uBitIndex;
+ COOR c, cExposed;
+ PIECE p;
+
+ ASSERT(InCheck(pos, pos->uToMove));
+ ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove);
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ cExposed = ExposesCheck(pos, cQueen, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == c))
+ {
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cQueen, c, p);
+ }
+ }
+}
+
void
GenerateBlackKing(IN MOVE_STACK *pStack,
IN POSITION *pos,
@@ -1482,6 +2146,123 @@ Return value:
}
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 3 step 2: bitboard
+// king generator, normal (non-castling) moves only -- castling stays
+// mailbox per section 1's explicit non-goal (at most 2 candidate
+// moves, checked via simple square-emptiness tests, not
+// ray-walk-shaped, nothing for a bitboard to speed up). Serves both
+// JumpTable slots the same way _GenerateKnightBB does, for the same
+// reason (GenerateWhiteKing's GET_COLOR(p)==BLACK bit trick was a
+// mailbox-only micro-optimization); the castling tail below still
+// branches on color since CASTLE_BLACK_*/CASTLE_WHITE_* and their
+// associated squares genuinely differ per side.
+//
+void
+_GenerateKingBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN COOR cKing)
+/**
+
+Routine description:
+
+ Bitboard equivalent of GenerateBlackKing/GenerateWhiteKing's normal
+ (non-castling) move enumeration -- called by GenerateMoves'
+ JumpTable in place of both when GENERATE_KING_BITBOARD is defined.
+ Produces the exact same pseudo-legal move set as the mailbox pair,
+ castling included (via the same mailbox logic those functions use,
+ verbatim) -- see MOVEGEN_MIGRATION.md section 1's explicit non-goal
+ against changing over-generation behavior.
+
+ Relies on pStack->bbFriendlyOccupied already being set by the
+ caller, same as _GenerateKnightBB -- see that function's header
+ comment and MOVE_STACK's field comment in chess.h.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack (bbFriendlyOccupied must
+ already be set for pos->uToMove)
+ POSITION *pos : the board position
+ COOR cKing : the king's location
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbDest = g_KingAttacksBB[cKing] & ~pStack->bbFriendlyOccupied;
+ ULONG uBitIndex;
+ COOR c;
+ PIECE p;
+
+ ASSERT(IS_KING(pos->rgSquare[cKing].pPiece));
+ ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove);
+ ASSERT(pStack->bbFriendlyOccupied ==
+ _BuildFriendlySideBB(pos, pos->uToMove));
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ p = pos->rgSquare[c].pPiece;
+ _AddNormalMove(pStack, pos, cKing, c, p);
+ }
+
+ //
+ // Castling: unchanged mailbox logic, copied verbatim from
+ // GenerateBlackKing/GenerateWhiteKing -- see those functions'
+ // comments. Not in scope for a bitboard rewrite (section 1).
+ //
+ if (pos->uToMove == BLACK)
+ {
+ if ((pos->bvCastleInfo & BLACK_CAN_CASTLE) == 0) return;
+#ifdef DEBUG
+ ASSERT(IS_KING(pos->rgSquare[E8].pPiece));
+ ASSERT(cKing == E8);
+#endif
+ if ((pos->bvCastleInfo & CASTLE_BLACK_SHORT) &&
+ (IS_EMPTY(pos->rgSquare[G8].pPiece)) &&
+ (IS_EMPTY(pos->rgSquare[F8].pPiece)))
+ {
+ ASSERT(pos->rgSquare[H8].pPiece == BLACK_ROOK);
+ _AddCastle(pStack, pos, E8, G8);
+ }
+ if ((pos->bvCastleInfo & CASTLE_BLACK_LONG) &&
+ (IS_EMPTY(pos->rgSquare[C8].pPiece)) &&
+ (IS_EMPTY(pos->rgSquare[D8].pPiece)) &&
+ (IS_EMPTY(pos->rgSquare[B8].pPiece)))
+ {
+ ASSERT(pos->rgSquare[A8].pPiece == BLACK_ROOK);
+ _AddCastle(pStack, pos, E8, C8);
+ }
+ }
+ else
+ {
+ if ((pos->bvCastleInfo & WHITE_CAN_CASTLE) == 0) return;
+#ifdef DEBUG
+ ASSERT(IS_KING(pos->rgSquare[E1].pPiece));
+ ASSERT(cKing == E1);
+#endif
+ if ((pos->bvCastleInfo & CASTLE_WHITE_SHORT) &&
+ (IS_EMPTY(pos->rgSquare[G1].pPiece)) &&
+ (IS_EMPTY(pos->rgSquare[F1].pPiece)))
+ {
+ ASSERT(pos->rgSquare[H1].pPiece == WHITE_ROOK);
+ _AddCastle(pStack, pos, E1, G1);
+ }
+ if ((pos->bvCastleInfo & CASTLE_WHITE_LONG) &&
+ (IS_EMPTY(pos->rgSquare[C1].pPiece)) &&
+ (IS_EMPTY(pos->rgSquare[B1].pPiece)) &&
+ (IS_EMPTY(pos->rgSquare[D1].pPiece)))
+ {
+ ASSERT(pos->rgSquare[A1].pPiece == WHITE_ROOK);
+ _AddCastle(pStack, pos, E1, C1);
+ }
+ }
+}
+
void
GenerateWhitePawn(IN MOVE_STACK *pStack,
@@ -1882,6 +2663,213 @@ Return value:
}
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 3 step 5: bulk,
+// whole-side pawn generator using the classic shift-and-mask technique
+// (confirmed via ~/crafty/movgen.c to be the standard approach, not a
+// per-starting-square precomputed mask) rather than a per-square
+// lookup like the other five migrated piece types. Structurally
+// different for a real reason: pos->bbPawns[uSide]'s bits already
+// live in dense rank*8+file space (COOR_TO_BIT_NUMBER), so shifting
+// the *entire* bitboard by 8 moves every pawn of that side forward one
+// rank simultaneously -- no per-pawn loop needed to find destinations,
+// only to emit the resulting moves.
+//
+// This engine's square numbering has A8 = bit 0 (COOR_TO_BIT_NUMBER of
+// 0x88's A8 == 0x00), so rank number increases as the *row* (bits/8)
+// *decreases* -- opposite of Crafty's convention (confirmed via
+// GenerateWhitePawn's existing 0x88 deltas: -16 forward, -15/-17
+// captures). Concretely, in bit-number space:
+// WHITE forward = row decreases = bb >> 8
+// BLACK forward = row increases = bb << 8
+// and the two diagonals per side are +-7/+-9 (one rank plus one file),
+// each requiring the *opposite* file's edge excluded first so a
+// same-row wraparound (e.g. an h-file pawn's ">>7" would otherwise
+// silently land back on the same row's a-file -- a real, silent-wrong-
+// answer trap, not just an out-of-range index) never happens -- see
+// each shift's comment below for which file it excludes and why.
+//
+// Double-push eligibility (rank 2 for White, rank 7 for Black) is
+// checked by masking the *already-computed single-push destination*
+// bitboard against BBRANK[3]/BBRANK[6] (did this pawn's single push
+// land on rank 3/6, which is only possible starting from rank 2/7)
+// rather than a per-square starting-rank table -- same technique
+// Crafty uses (movgen.c's padvances2, masking padvances1_all against
+// its own rank-3/rank-6 constant before the second shift).
+//
+// En passant is deliberately NOT folded into the bulk capture
+// bitboards -- it is exactly one specific square (pos->cEpSquare) at
+// most once per node, cheaper and less error-prone to check directly
+// (does either of the two diagonal-behind squares hold one of this
+// side's pawns) than to derive and mask a whole extra bitboard for an
+// event this rare.
+//
+void
+_GenerateAllPawnMovesBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN ULONG uSide)
+/**
+
+Routine description:
+
+ Bitboard equivalent of the GenerateWhitePawn/GenerateBlackPawn pair
+ -- called in place of the per-pawn mailbox loop when
+ GENERATE_PAWN_BITBOARD is defined, for the entire side's pawns in
+ one call rather than once per pawn. Produces the exact same
+ pseudo-legal move set (same over-generation behavior, no
+ legal-awareness added) -- see MOVEGEN_MIGRATION.md section 1's
+ explicit non-goal.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack
+ POSITION *pos : the board position
+ ULONG uSide : which side's pawns to generate for (pos->uToMove)
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbPawns = pos->bbPawns[uSide];
+ BITBOARD bbOccupied = _BuildFullOccupiedBB(pos);
+ BITBOARD bbEmpty = ~bbOccupied;
+ BITBOARD bbEnemy = bbOccupied & ~_BuildFriendlySideBB(pos, uSide);
+ BITBOARD bbSinglePush, bbDoublePush, bbCapLeft, bbCapRight, bb;
+ ULONG uBitIndex;
+ COOR cTo, cFrom, cEp;
+ PIECE p;
+
+ if (uSide == WHITE)
+ {
+ bbSinglePush = (bbPawns >> 8) & bbEmpty;
+ bbDoublePush = ((bbSinglePush & BBRANK[3]) >> 8) & bbEmpty;
+ // "Left" diagonal (file-1, i.e. 0x88's -17): exclude file A
+ // (file-1 invalid/wraps for an a-file pawn).
+ bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy;
+ // "Right" diagonal (file+1, i.e. 0x88's -15): exclude file H.
+ bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy;
+ }
+ else
+ {
+ ASSERT(uSide == BLACK);
+ bbSinglePush = (bbPawns << 8) & bbEmpty;
+ bbDoublePush = ((bbSinglePush & BBRANK[6]) << 8) & bbEmpty;
+ // "Left" diagonal (file-1, 0x88's +15): exclude file A.
+ bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy;
+ // "Right" diagonal (file+1, 0x88's +17): exclude file H.
+ bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy;
+ }
+
+ // Single push (+ promotion if landing on the far rank).
+ bb = bbSinglePush;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 8) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 8);
+ ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
+ if (RANK8(cTo) || RANK1(cTo))
+ {
+ _AddPromote(pStack, pos, cFrom, cTo);
+ }
+ else
+ {
+ _AddNormalMove(pStack, pos, cFrom, cTo, 0);
+ }
+ }
+
+ // Double push -- never a promotion (rank 4/5 destination only).
+ bb = bbDoublePush;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 16) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 16);
+ ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
+ _AddDoubleJump(pStack, pos, cFrom, cTo);
+ }
+
+ // Capture left (+ promotion if landing on the far rank).
+ bb = bbCapLeft;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 9) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 7);
+ ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
+ p = pos->rgSquare[cTo].pPiece;
+ ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cFrom].pPiece));
+ if (RANK8(cTo) || RANK1(cTo))
+ {
+ _AddPromote(pStack, pos, cFrom, cTo);
+ }
+ else
+ {
+ _AddNormalMove(pStack, pos, cFrom, cTo, p);
+ }
+ }
+
+ // Capture right (+ promotion if landing on the far rank).
+ bb = bbCapRight;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 7) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 9);
+ ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
+ p = pos->rgSquare[cTo].pPiece;
+ ASSERT(!IS_EMPTY(p) && OPPOSITE_COLORS(p, pos->rgSquare[cFrom].pPiece));
+ if (RANK8(cTo) || RANK1(cTo))
+ {
+ _AddPromote(pStack, pos, cFrom, cTo);
+ }
+ else
+ {
+ _AddNormalMove(pStack, pos, cFrom, cTo, p);
+ }
+ }
+
+ // En passant -- deliberately not bulk (see block comment above):
+ // check the (at most 2) squares diagonally behind pos->cEpSquare
+ // for one of this side's pawns, exactly like the mailbox
+ // functions' cTo == pos->cEpSquare check, just run once per side
+ // per node instead of once per pawn.
+ cEp = pos->cEpSquare;
+ if (IS_ON_BOARD(cEp))
+ {
+ int iBehindDelta = (uSide == WHITE) ? 16 : -16;
+
+ cFrom = cEp + iBehindDelta - 1;
+ if (IS_ON_BOARD(cFrom) &&
+ IS_PAWN(pos->rgSquare[cFrom].pPiece) &&
+ (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide))
+ {
+ _AddEnPassant(pStack, pos, cFrom, cEp);
+ }
+ cFrom = cEp + iBehindDelta + 1;
+ if (IS_ON_BOARD(cFrom) &&
+ IS_PAWN(pos->rgSquare[cFrom].pPiece) &&
+ (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide))
+ {
+ _AddEnPassant(pStack, pos, cFrom, cEp);
+ }
+ }
+}
+
void
SaveMeBlackPawn(IN MOVE_STACK *pStack,
@@ -2038,6 +3026,209 @@ Return value:
}
}
+//
+// board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2: bulk
+// whole-side pawn escape generator, same shift-and-mask technique as
+// _GenerateAllPawnMovesBB, with each move-category bitboard ANDed
+// against bbTargetMask before extraction and an ExposesCheck filter
+// added per surviving candidate (the mailbox SaveMeWhitePawn/
+// SaveMeBlackPawn pair calls ExposesCheck per move too -- see section
+// 6a's "what does not change"). En passant is NOT covered by
+// bbTargetMask (a between-squares/capture-square mask has no way to
+// express "the checking pawn happens to be capturable en passant") --
+// kept as the same narrow direct special case the mailbox functions
+// use: only relevant when the double-jumping pawn *is* the checker.
+//
+void
+_SaveMeAllPawnMovesBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos,
+ IN ULONG uSide,
+ IN COOR cKing,
+ IN COOR cAttacker,
+ IN BITBOARD bbTargetMask)
+/**
+
+Routine description:
+
+ Bitboard equivalent of the SaveMeWhitePawn/SaveMeBlackPawn pair --
+ called in place of the per-pawn mailbox loop when
+ GENERATE_ESCAPES_BLOCK_BITBOARD is defined, for the entire side's
+ pawns in one call.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack
+ POSITION *pos : the board position
+ ULONG uSide : which side's pawns to generate for (pos->uToMove)
+ COOR cKing : the friendly king's location
+ COOR cAttacker : the lone checker's location
+ BITBOARD bbTargetMask : squares that resolve the lone check --
+ see _ComputeCheckTargetMaskBB
+
+Return value:
+
+ void
+
+**/
+{
+ BITBOARD bbPawns = pos->bbPawns[uSide];
+ BITBOARD bbOccupied = _BuildFullOccupiedBB(pos);
+ BITBOARD bbEmpty = ~bbOccupied;
+ BITBOARD bbEnemy = bbOccupied & ~_BuildFriendlySideBB(pos, uSide);
+ BITBOARD bbSinglePush, bbDoublePush, bbCapLeft, bbCapRight, bb;
+ ULONG uBitIndex;
+ COOR cTo, cFrom, cExposed;
+ PIECE p;
+
+ if (uSide == WHITE)
+ {
+ bbSinglePush = (bbPawns >> 8) & bbEmpty;
+ bbDoublePush = ((bbSinglePush & BBRANK[3]) >> 8) & bbEmpty;
+ bbCapLeft = ((bbPawns & ~BBFILE[0]) >> 9) & bbEnemy;
+ bbCapRight = ((bbPawns & ~BBFILE[7]) >> 7) & bbEnemy;
+ }
+ else
+ {
+ ASSERT(uSide == BLACK);
+ bbSinglePush = (bbPawns << 8) & bbEmpty;
+ bbDoublePush = ((bbSinglePush & BBRANK[6]) << 8) & bbEmpty;
+ bbCapLeft = ((bbPawns & ~BBFILE[0]) << 7) & bbEnemy;
+ bbCapRight = ((bbPawns & ~BBFILE[7]) << 9) & bbEnemy;
+ }
+
+ // Every move category is ANDed against bbTargetMask -- see this
+ // function's header comment for why that's sufficient (a push
+ // destination is only ever in bbTargetMask if it's a genuine block
+ // square, since bbTargetMask's non-capture bits are, by
+ // construction, empty squares; a capture destination is only ever
+ // in bbTargetMask if it's the checker's own square, since
+ // between-squares are empty and captures already require bbEnemy).
+ bbSinglePush &= bbTargetMask;
+ bbDoublePush &= bbTargetMask;
+ bbCapLeft &= bbTargetMask;
+ bbCapRight &= bbTargetMask;
+
+ bb = bbSinglePush;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 8) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 8);
+ cExposed = ExposesCheck(pos, cFrom, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == cTo))
+ {
+ if (RANK8(cTo) || RANK1(cTo))
+ {
+ _AddPromote(pStack, pos, cFrom, cTo);
+ }
+ else
+ {
+ _AddNormalMove(pStack, pos, cFrom, cTo, 0);
+ }
+ }
+ }
+
+ bb = bbDoublePush;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 16) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 16);
+ cExposed = ExposesCheck(pos, cFrom, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == cTo))
+ {
+ _AddDoubleJump(pStack, pos, cFrom, cTo);
+ }
+ }
+
+ bb = bbCapLeft;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 9) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 7);
+ cExposed = ExposesCheck(pos, cFrom, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
+ {
+ p = pos->rgSquare[cTo].pPiece;
+ if (RANK8(cTo) || RANK1(cTo))
+ {
+ _AddPromote(pStack, pos, cFrom, cTo);
+ }
+ else
+ {
+ _AddNormalMove(pStack, pos, cFrom, cTo, p);
+ }
+ }
+ }
+
+ bb = bbCapRight;
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cTo = BIT_NUMBER_TO_COOR(uBitIndex);
+ cFrom = (uSide == WHITE) ?
+ BIT_NUMBER_TO_COOR(uBitIndex + 7) :
+ BIT_NUMBER_TO_COOR(uBitIndex - 9);
+ cExposed = ExposesCheck(pos, cFrom, cKing);
+ if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
+ {
+ p = pos->rgSquare[cTo].pPiece;
+ if (RANK8(cTo) || RANK1(cTo))
+ {
+ _AddPromote(pStack, pos, cFrom, cTo);
+ }
+ else
+ {
+ _AddNormalMove(pStack, pos, cFrom, cTo, p);
+ }
+ }
+ }
+
+ //
+ // En passant: only relevant when the double-jumping enemy pawn
+ // *is* the checker -- there is no way to block check with an en
+ // passant capture (see SaveMeWhitePawn/SaveMeBlackPawn's identical
+ // comment). White defender: cAttacker == cEpSquare + 16. Black
+ // defender: cAttacker == cEpSquare - 16.
+ //
+ if (IS_ON_BOARD(pos->cEpSquare))
+ {
+ COOR cEp = pos->cEpSquare;
+ int iBehindDelta = (uSide == WHITE) ? 16 : -16;
+ FLAG fEpResolvesCheck = (uSide == WHITE) ?
+ (cAttacker == cEp + 16) : (cAttacker == cEp - 16);
+
+ if (fEpResolvesCheck)
+ {
+ cFrom = cEp + iBehindDelta - 1;
+ if (IS_ON_BOARD(cFrom) &&
+ IS_PAWN(pos->rgSquare[cFrom].pPiece) &&
+ (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide))
+ {
+ _AddEnPassant(pStack, pos, cFrom, cEp);
+ }
+ cFrom = cEp + iBehindDelta + 1;
+ if (IS_ON_BOARD(cFrom) &&
+ IS_PAWN(pos->rgSquare[cFrom].pPiece) &&
+ (GET_COLOR(pos->rgSquare[cFrom].pPiece) == uSide))
+ {
+ _AddEnPassant(pStack, pos, cFrom, cEp);
+ }
+ }
+ }
+}
+
void
InvalidGenerator(IN UNUSED MOVE_STACK *pStack,
@@ -2100,7 +3291,12 @@ Return value:
}
-static void
+// Non-static (unlike its historical internal-only status) so
+// testgenerate.c's whole-node dispatch benchmark can call it directly
+// by name -- see _GenerateAllMovesBB's block comment for why that
+// comparison needs both functions callable under their real names in
+// a toggle-free build.
+void
_GenerateAllMoves(IN MOVE_STACK *pStack,
IN POSITION *pos)
/**
@@ -2128,22 +3324,67 @@ Return value:
InvalidGenerator, // EMPTY | WHITE
InvalidGenerator, // 2 (BLACK_PAWN)
InvalidGenerator, // 3 (WHITE_PAWN)
+ // MOVEGEN_MIGRATION.md section 6 toggle -- one #define per
+ // piece type, independent of the others. _GenerateKnightBB
+ // serves both slots; see its header comment for why the
+ // mailbox pair's color split doesn't carry over to bitboards.
+#if defined(GENERATE_KNIGHT_BITBOARD)
+ _GenerateKnightBB, // 4 (BLACK_KNIGHT)
+ _GenerateKnightBB, // 5 (WHITE_KNIGHT)
+#else
GenerateKnight, // 4 (BLACK_KNIGHT)
GenerateWhiteKnight, // 5 (WHITE_KNIGHT)
+#endif
+#if defined(GENERATE_BISHOP_BITBOARD)
+ _GenerateBishopBB, // 6 (BLACK_BISHOP)
+ _GenerateBishopBB, // 7 (WHITE_BISHOP)
+#else
GenerateBishop, // 6 (BLACK_BISHOP)
GenerateBishop, // 7 (WHITE_BISHOP)
+#endif
+#if defined(GENERATE_ROOK_BITBOARD)
+ _GenerateRookBB, // 8 (BLACK_ROOK)
+ _GenerateRookBB, // 9 (WHITE_ROOK)
+#else
GenerateRook, // 8 (BLACK_ROOK)
GenerateRook, // 9 (WHITE_ROOK)
+#endif
+#if defined(GENERATE_QUEEN_BITBOARD)
+ _GenerateQueenBB, // 10 (BLACK_QUEEN)
+ _GenerateQueenBB, // 11 (WHITE_QUEEN)
+#else
GenerateQueen, // 10 (BLACK_QUEEN)
- GenerateQueen, // 11 (WHITE_QUEEN)
+ GenerateQueen, // 11 (WHITE_QUEEN)
+#endif
+#if defined(GENERATE_KING_BITBOARD)
+ _GenerateKingBB, // 12 (BLACK_KING)
+ _GenerateKingBB // 13 (WHITE_KING)
+#else
GenerateBlackKing, // 12 (BLACK_KING)
GenerateWhiteKing // 13 (WHITE_KING)
+#endif
};
ULONG u;
#ifdef DEBUG
PIECE p;
#endif
+ // See MOVE_STACK's bbFriendlyOccupied field comment (chess.h) and
+ // _GenerateKnightBB's header comment: computed once per node here,
+ // before any piece-type dispatch, so every bitboard-backed
+ // generator invoked below shares this build instead of each
+ // recomputing it -- extend this #if with each new
+ // GENERATE_*_BITBOARD toggle as piece types migrate.
+#if defined(GENERATE_KNIGHT_BITBOARD) || defined(GENERATE_KING_BITBOARD) || \
+ defined(GENERATE_ROOK_BITBOARD) || defined(GENERATE_BISHOP_BITBOARD) || \
+ defined(GENERATE_QUEEN_BITBOARD)
+ pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove);
+#endif
+#if defined(GENERATE_ROOK_BITBOARD) || defined(GENERATE_BISHOP_BITBOARD) || \
+ defined(GENERATE_QUEEN_BITBOARD)
+ pStack->bbOccupied = _BuildFullOccupiedBB(pos);
+#endif
+
for(u = pos->uNonPawnCount[pos->uToMove][0] - 1;
u != (ULONG)-1;
u--)
@@ -2159,7 +3400,10 @@ Return value:
(JumpTable[pos->rgSquare[c].pPiece])(pStack, pos, c);
}
- if (pos->uToMove == BLACK)
+#if defined(GENERATE_PAWN_BITBOARD)
+ _GenerateAllPawnMovesBB(pStack, pos, pos->uToMove);
+#else
+ if (pos->uToMove == BLACK)
{
for(u = 0; u < pos->uPawnCount[BLACK]; u++)
{
@@ -2175,7 +3419,7 @@ Return value:
}
} else {
ASSERT(pos->uToMove == WHITE);
- for(u = 0; u < pos->uPawnCount[WHITE]; u++)
+ for(u = 0; u < pos->uPawnCount[WHITE]; u++)
{
c = pos->cPawns[WHITE][u];
#ifdef DEBUG
@@ -2188,8 +3432,188 @@ Return value:
GenerateWhitePawn(pStack, pos, c);
}
}
+#endif
+}
+
+//
+// board_representation/MOVEGEN_MIGRATION.md section 3: fully
+// bitboard-driven alternative to _GenerateAllMoves, forked at this
+// level (not folded into _GenerateAllMoves's own JumpTable-based body
+// via an #if) specifically to eliminate _GenerateAllMoves's own
+// indirect-call dispatch, not just to swap which per-piece-type
+// function gets called.
+//
+// _GenerateAllMoves's cNonPawns[side][] loop is a flat list mixing all
+// non-pawn piece types together (pieces are added/removed via
+// swap-with-last, so there is no contiguous per-type range to slice)
+// -- that mixed ordering is *why* it needs
+// JumpTable[pos->rgSquare[c].pPiece], an indirect call whose target
+// changes almost every iteration as the loop walks across different
+// piece types, close to the worst case for a CPU's indirect-branch
+// predictor. Every per-piece-type speed benchmark in this migration
+// (testgenerate.c's TestGenerateKnightSpeed and friends) called its
+// _Generate*BB function directly, bypassing JumpTable entirely -- so
+// none of those numbers ever measured, or could benefit from
+// removing, this dispatch cost. This function is the piece that
+// actually exercises that question: pos->bbPieces[side][KNIGHT/
+// BISHOP/ROOK/QUEEN] already partitions squares by type (unlike
+// cNonPawns), so each piece type gets its own bit-extraction loop
+// calling its specific _Generate*BB function BY NAME -- a
+// statically-known, likely-inlinable direct call, no function pointer
+// anywhere in this function.
+//
+// Only exists (and is only substituted in for _GenerateAllMoves, see
+// the #define below) when every non-pawn, non-castling piece type's
+// bitboard toggle is defined -- a partial-rollout mix (e.g. knight and
+// king migrated, rook/bishop/queen not yet) still needs
+// _GenerateAllMoves's cNonPawns/JumpTable path, since that path is the
+// only one that knows how to fall back to a still-mailbox piece type
+// while also correctly finding already-migrated ones by iterating the
+// same mixed list. This function does not attempt to support that
+// mixed case -- see MOVEGEN_MIGRATION.md for why an all-or-nothing
+// fork was chosen over threading partial-rollout support through this
+// function too.
+//
+void
+_GenerateAllMovesBB(IN MOVE_STACK *pStack,
+ IN POSITION *pos)
+/**
+
+Routine description:
+
+ Fully bitboard-driven equivalent of _GenerateAllMoves -- see the
+ block comment above. Produces the exact same pseudo-legal move set
+ (same over-generation behavior, no legal-awareness added, and no
+ change to which moves are generated, only how the dispatch to each
+ piece type's generator happens) -- see MOVEGEN_MIGRATION.md
+ section 1's explicit non-goal.
+
+Parameters:
+
+ MOVE_STACK *pStack : the move stack
+ POSITION *pos : the board position
+
+Return value:
+
+ static void
+
+**/
+{
+ ULONG uSide = pos->uToMove;
+ BITBOARD bb;
+ ULONG uBitIndex;
+ COOR c;
+#if !defined(GENERATE_PAWN_BITBOARD)
+ ULONG u;
+#endif
+#if defined(DEBUG) && !defined(GENERATE_PAWN_BITBOARD)
+ PIECE p;
+#endif
+
+ pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, uSide);
+ pStack->bbOccupied = _BuildFullOccupiedBB(pos);
+
+ bb = pos->bbPieces[uSide][KNIGHT];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ ASSERT(IS_KNIGHT(pos->rgSquare[c].pPiece));
+ _GenerateKnightBB(pStack, pos, c);
+ }
+
+ bb = pos->bbPieces[uSide][BISHOP];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ ASSERT(IS_BISHOP(pos->rgSquare[c].pPiece));
+ _GenerateBishopBB(pStack, pos, c);
+ }
+
+ bb = pos->bbPieces[uSide][ROOK];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ ASSERT(IS_ROOK(pos->rgSquare[c].pPiece));
+ _GenerateRookBB(pStack, pos, c);
+ }
+
+ bb = pos->bbPieces[uSide][QUEEN];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ ASSERT(IS_QUEEN(pos->rgSquare[c].pPiece));
+ _GenerateQueenBB(pStack, pos, c);
+ }
+
+ // King has no bitboard of its own (a single square, cNonPawns[
+ // side][0] -- see POSITION's bbPieces field comment in chess.h for
+ // why a bitboard would add nothing here); still a direct,
+ // statically-known call, same as the four loops above.
+ c = pos->cNonPawns[uSide][0];
+ ASSERT(IS_KING(pos->rgSquare[c].pPiece));
+ _GenerateKingBB(pStack, pos, c);
+
+ // Pawns: unchanged from _GenerateAllMoves -- not in scope for this
+ // migration (section 3 step 5's pawn note) unless
+ // GENERATE_PAWN_BITBOARD is also defined, in which case pawns get
+ // the same bulk treatment via _GenerateAllPawnMovesBB -- pawns'
+ // own toggle is independent of the five above (section 6).
+#if defined(GENERATE_PAWN_BITBOARD)
+ _GenerateAllPawnMovesBB(pStack, pos, uSide);
+#else
+ if (uSide == BLACK)
+ {
+ for(u = 0; u < pos->uPawnCount[BLACK]; u++)
+ {
+ c = pos->cPawns[BLACK][u];
+#ifdef DEBUG
+ ASSERT(IS_ON_BOARD(c));
+ p = pos->rgSquare[c].pPiece;
+ ASSERT(!IS_EMPTY(p));
+ ASSERT(IS_PAWN(p));
+ ASSERT(GET_COLOR(p) == uSide);
+#endif
+ GenerateBlackPawn(pStack, pos, c);
+ }
+ }
+ else
+ {
+ ASSERT(uSide == WHITE);
+ for(u = 0; u < pos->uPawnCount[WHITE]; u++)
+ {
+ c = pos->cPawns[WHITE][u];
+#ifdef DEBUG
+ ASSERT(IS_ON_BOARD(c));
+ p = pos->rgSquare[c].pPiece;
+ ASSERT(!IS_EMPTY(p));
+ ASSERT(IS_PAWN(p));
+ ASSERT(GET_COLOR(p) == uSide);
+#endif
+ GenerateWhitePawn(pStack, pos, c);
+ }
+ }
+#endif
}
+// Whole-dispatch fork -- see _GenerateAllMovesBB's block comment for
+// why this is a #define swap of the entire function (matching
+// chess.h's GetAttacks precedent) rather than a branch nested inside
+// _GenerateAllMoves. Only fires when every non-pawn, non-castling
+// piece type is bitboard-backed; any partial mix still uses
+// _GenerateAllMoves's cNonPawns/JumpTable path unchanged.
+#if defined(GENERATE_KNIGHT_BITBOARD) && defined(GENERATE_KING_BITBOARD) && \
+ defined(GENERATE_ROOK_BITBOARD) && defined(GENERATE_BISHOP_BITBOARD) && \
+ defined(GENERATE_QUEEN_BITBOARD)
+#define _GenerateAllMoves _GenerateAllMovesBB
+#endif
static ULONG
@@ -2219,17 +3643,28 @@ Return value:
**/
{
+#if !defined(GENERATE_ESCAPES_KING_BITBOARD) || !defined(GENERATE_ESCAPES_BLOCK_BITBOARD)
ULONG u;
+#endif
+#if !defined(GENERATE_ESCAPES_KING_BITBOARD)
ULONG v;
+#endif
COOR c;
+#if !defined(GENERATE_ESCAPES_BLOCK_BITBOARD)
COOR cDefender;
+#endif
PIECE p;
PIECE pKing;
COOR cKing = pos->cNonPawns[pos->uToMove][0];
+#if !defined(GENERATE_ESCAPES_KING_BITBOARD)
int iIndex;
+#endif
SEE_LIST rgCheckers;
+#if !defined(GENERATE_ESCAPES_KING_BITBOARD)
int iDelta;
+#endif
ULONG uReturn = 0;
+#if !defined(GENERATE_ESCAPES_BLOCK_BITBOARD)
static void (*JumpTable[])
(MOVE_STACK *, POSITION *, COOR, COOR, COOR) =
{
@@ -2248,6 +3683,7 @@ Return value:
InvalidSaveMe, // kings already considered
InvalidSaveMe // kings already considered
};
+#endif
ASSERT(IS_KING(pos->rgSquare[cKing].pPiece));
ASSERT(TRUE == InCheck(pos, pos->uToMove));
@@ -2271,6 +3707,50 @@ Return value:
ASSERT(GET_COLOR(pKing) == pos->uToMove);
ASSERT(IS_KING(pKing));
ASSERT(OPPOSITE_COLORS(pKing, rgCheckers.data[0].pPiece));
+#if defined(GENERATE_ESCAPES_KING_BITBOARD)
+ //
+ // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 1:
+ // g_KingAttacksBB gives every candidate flight square in one
+ // lookup (already excludes friendly-occupied squares); the
+ // mailbox version's manual per-checker x-ray loop below is
+ // replaced entirely by testing _WhoAttacksSquareBB against
+ // occupancy with the king itself removed -- a slider whose ray
+ // was only blocked by the king's own (pre-move) body now correctly
+ // shows up as attacking a candidate square still on that ray,
+ // exactly the case the manual loop existed to catch by hand.
+ // Pawns are checked separately since _WhoAttacksSquareBB
+ // deliberately excludes them (see its header comment).
+ {
+ ULONG uEnemy = FLIP(pos->uToMove);
+ // pKing is only used inside ASSERTs below, which vanish in a
+ // non-DEBUG build -- silence the resulting "set but not used"
+ // warning explicitly rather than leave it looking accidental.
+ (void)pKing;
+ BITBOARD bbFriendly = _BuildFriendlySideBB(pos, pos->uToMove);
+ BITBOARD bbOccupiedWithoutKing =
+ _BuildFullOccupiedBB(pos) & ~COOR_TO_BB(cKing);
+ BITBOARD bbDest = g_KingAttacksBB[cKing] & ~bbFriendly;
+ ULONG uBitIndex;
+
+ while (bbDest)
+ {
+ uBitIndex = FastFirstBit(bbDest) - 1;
+ bbDest &= (bbDest - 1);
+ c = BIT_NUMBER_TO_COOR(uBitIndex);
+ p = pos->rgSquare[c].pPiece;
+ ASSERT(IS_EMPTY(p) || OPPOSITE_COLORS(p, pKing));
+
+ if ((0 == _WhoAttacksSquareBB(pos, c, uEnemy,
+ bbOccupiedWithoutKing)) &&
+ (0 == (g_PawnAttackOriginBB[uEnemy][c] &
+ pos->bbPawns[uEnemy])))
+ {
+ _AddNormalMove(pStack, pos, cKing, c, p);
+ uReturn += 0x00010000;
+ }
+ }
+ }
+#else
u = 0;
while(0 != g_iQKDeltas[u])
{
@@ -2332,6 +3812,7 @@ Return value:
loop:
;
}
+#endif
//
// N.B. If there is more than one piece checking the king then
@@ -2370,6 +3851,74 @@ Return value:
// checking piece.
//
c = rgCheckers.data[0].cLoc;
+#if defined(GENERATE_ESCAPES_BLOCK_BITBOARD)
+ //
+ // board_representation/MOVEGEN_MIGRATION.md section 6a Phase 2:
+ // pos->cNonPawns[side][] mixes every non-pawn piece type together
+ // (same reason as _GenerateAllMoves's own loop -- no contiguous
+ // per-type range to slice), which is why the mailbox path above
+ // needs JumpTable[p], an indirect call whose target changes almost
+ // every iteration -- close to the worst case for a CPU's
+ // indirect-branch predictor. pos->bbPieces[side][KNIGHT/BISHOP/
+ // ROOK/QUEEN] sidesteps this exactly like _GenerateAllMovesBB did:
+ // each piece type gets its own bit-extraction loop calling its
+ // specific _SaveMe*BB function BY NAME, no function pointer
+ // anywhere in this block.
+ {
+ BITBOARD bbTargetMask;
+ BITBOARD bb;
+ ULONG uBitIndex;
+ COOR cDef;
+
+ // Unlike _GenerateAllMoves, GENERATE_ESCAPES's call site never
+ // precomputes these -- set them here, once, for every
+ // _SaveMe*BB call below to share (same amortization reasoning
+ // as _GenerateAllMoves's own precompute block).
+ pStack->bbFriendlyOccupied = _BuildFriendlySideBB(pos, pos->uToMove);
+ pStack->bbOccupied = _BuildFullOccupiedBB(pos);
+ bbTargetMask =
+ _ComputeCheckTargetMaskBB(cKing, c, pStack->bbOccupied);
+
+ bb = pos->bbPieces[pos->uToMove][KNIGHT];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cDef = BIT_NUMBER_TO_COOR(uBitIndex);
+ _SaveMeKnightBB(pStack, pos, cDef, cKing, bbTargetMask);
+ }
+
+ bb = pos->bbPieces[pos->uToMove][BISHOP];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cDef = BIT_NUMBER_TO_COOR(uBitIndex);
+ _SaveMeBishopBB(pStack, pos, cDef, cKing, bbTargetMask);
+ }
+
+ bb = pos->bbPieces[pos->uToMove][ROOK];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cDef = BIT_NUMBER_TO_COOR(uBitIndex);
+ _SaveMeRookBB(pStack, pos, cDef, cKing, bbTargetMask);
+ }
+
+ bb = pos->bbPieces[pos->uToMove][QUEEN];
+ while (bb)
+ {
+ uBitIndex = FastFirstBit(bb) - 1;
+ bb &= (bb - 1);
+ cDef = BIT_NUMBER_TO_COOR(uBitIndex);
+ _SaveMeQueenBB(pStack, pos, cDef, cKing, bbTargetMask);
+ }
+
+ _SaveMeAllPawnMovesBB(pStack, pos, pos->uToMove, cKing, c,
+ bbTargetMask);
+ }
+#else
for (u = 1; // don't consider the king
u < pos->uNonPawnCount[pos->uToMove][0];
u++)
@@ -2384,7 +3933,7 @@ Return value:
}
// Consider all pawns too
- if (pos->uToMove == BLACK)
+ if (pos->uToMove == BLACK)
{
for (u = 0; u < pos->uPawnCount[BLACK]; u++)
{
@@ -2399,7 +3948,7 @@ Return value:
}
} else {
ASSERT(pos->uToMove == WHITE);
- for (u = 0; u < pos->uPawnCount[WHITE]; u++)
+ for (u = 0; u < pos->uPawnCount[WHITE]; u++)
{
cDefender = pos->cPawns[WHITE][u];
#ifdef DEBUG
@@ -2411,6 +3960,7 @@ Return value:
SaveMeWhitePawn(pStack, pos, cDefender, cKing, c);
}
}
+#endif
return(uReturn);
}
generated by cgit v1.3 (git 2.53.0) at 2026-09-09 11:46:56 +0000