From 92fc41226f784b251f41eab7e75c13075e980a54 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Fri, 4 Sep 2026 16:46:27 -0700 Subject: Land bitboard move generation (Part A+B) and movesup.c bitboard queries; default on Implements the full board_representation/MOVEGEN_MIGRATION.md scope: bitboard-backed generators for all six not-in-check piece types plus the JumpTable-avoiding whole-node dispatch fork (_GenerateAllMovesBB), the in-check escape path (king flight + block/capture), and movesup.c's ExposesCheck/FasterExposesCheck/ExposesCheckEp/IsAttacked/ InCheck bitboard equivalents. Nine toggles total (GENERATE_{KNIGHT,KING,ROOK,BISHOP,QUEEN,PAWN}_BITBOARD, GENERATE_ESCAPES_{KING,BLOCK}_BITBOARD, EXPOSESCHECK_BITBOARD, ISATTACKED_BITBOARD), all now on by default in GNUmakefile -- DISABLE_BITBOARD_MOVEGEN=1 opts back into the mailbox path, which remains fully present and compiled either way. Correctness verified via perft (Kiwipete, Position 4), the move-set comparison harness across 20,000 random positions, all nine toggles combined cleanly (15/15 runs, after fixing a GenerateRandomLegalPosition en-passant-sentinel bug in the test harness), and sd10 on all three curated suites showing zero solve-count regression vs head_reference (the ecm_hard_quick delta traced to unrelated intervening commits). Speed: most individual generators land near parity by design (mailbox's per-square walk was already close to O(destination count)); the real, consistent wins are the dispatch-layer fork (up to 23% in dense positions) and IsAttackedBB (0.73x-0.93x of mailbox). Co-Authored-By: Claude Sonnet 5 Claude-Session: https://claude.ai/code/session_01AbHkVrm5KUyzLwWd3GHmo6 --- src/testgenerate.c | 453 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 453 insertions(+) (limited to 'src/testgenerate.c') diff --git a/src/testgenerate.c b/src/testgenerate.c index 5fdf30f..c6947d2 100755 --- a/src/testgenerate.c +++ b/src/testgenerate.c @@ -244,4 +244,457 @@ TestLegalMoveGenerator(void) while(u < 1000); SystemFreeMemory(ctx); } + +// +// board_representation/MOVEGEN_MIGRATION.md section 5's isolated +// cycles/call microbenchmark for the knight generator -- modeled +// directly on testsee.c's TestGetAttacks speed block (interleaved +// call-by-call across opening/middlegame/endgame positions, to cancel +// shared-box noise). Correctness for this piece type is already +// covered by TestMoveGenerator's perft counts (with +// GENERATE_KNIGHT_BITBOARD defined) -- this only answers "is it +// faster," the section 5 gate before a piece type's toggle is +// considered for default-on. +// +void +TestGenerateKnightSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3KN3/8/8/8/8 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcKnight[3] = { B1, C3, E5 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking knight move generation: mailbox vs " + "_GenerateKnightBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_KNIGHT(posBench.rgSquare[rgcKnight[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcKnight[u]].pPiece) == + posBench.uToMove); + + // _GenerateKnightBB relies on this being set by its caller + // (normally _GenerateAllMoves, once per node) -- see + // MOVE_STACK's bbFriendlyOccupied field comment in chess.h. + // Computed once per benchmark position, not per call, matching + // how the real call site amortizes it. + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateWhiteKnight(&ctx->sMoveStack, &posBench, rgcKnight[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateKnightBB(&ctx->sMoveStack, &posBench, rgcKnight[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateKnightBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateKnightSpeed, for the king. Opening position +// has castling rights but blocked by intervening pieces (exercises the +// emptiness-check branch's cost without ever actually reaching +// _AddCastle); middlegame is already castled (no rights, cheapest +// castling-tail exit); endgame is a bare king on an open board (no +// rights either, but the most normal-move destinations to enumerate). +// +void +TestGenerateKingSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/4K3/8/8/8/8 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcKing[3] = { E1, G1, E5 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking king move generation: mailbox vs " + "_GenerateKingBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_KING(posBench.rgSquare[rgcKing[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcKing[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateWhiteKing(&ctx->sMoveStack, &posBench, rgcKing[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateKingBB(&ctx->sMoveStack, &posBench, rgcKing[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateKingBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateKnightSpeed/TestGenerateKingSpeed, for the +// rook -- but unlike those two, this piece type is expected to +// actually win: rook a1 is fully blocked in the opening (0 +// destinations, cheapest case either way), partially open in the +// middlegame, and nearly fully open in the endgame (up to 13 +// destinations along an empty file/rank) -- exactly the case a +// 4-direction ray walk pays for and a magic lookup doesn't. +// +void +TestGenerateRookSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3K4/8/8/8/R7 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcRook[3] = { A1, A1, A1 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking rook move generation: mailbox vs " + "_GenerateRookBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_ROOK(posBench.rgSquare[rgcRook[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcRook[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + ctx->sMoveStack.bbOccupied = _BuildFullOccupiedBB(&posBench); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateRook(&ctx->sMoveStack, &posBench, rgcRook[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateRookBB(&ctx->sMoveStack, &posBench, rgcRook[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateRookBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateRookSpeed, for the bishop -- expect the +// same parity result (see MOVEGEN_MIGRATION.md section 3's rook +// entry for why), not a different outcome, since the underlying +// reason applies identically to diagonals. +// +void +TestGenerateBishopSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "8/5k2/8/3K4/8/8/8/B7 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcBishop[3] = { C1, D3, A1 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking bishop move generation: mailbox vs " + "_GenerateBishopBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_BISHOP(posBench.rgSquare[rgcBishop[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcBishop[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + ctx->sMoveStack.bbOccupied = _BuildFullOccupiedBB(&posBench); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateBishop(&ctx->sMoveStack, &posBench, rgcBishop[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateBishopBB(&ctx->sMoveStack, &posBench, rgcBishop[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateBishopBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Same shape as TestGenerateRookSpeed/TestGenerateBishopSpeed, for the +// queen -- expect the same parity-or-slightly-worse result, plus an +// extra fixed cost this time (two magic lookups instead of one) -- +// see MOVEGEN_MIGRATION.md section 3's rook entry for why a win was +// never really on the table for this piece type either. +// +void +TestGenerateQueenSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1b2rk1/pp2bppp/2n1pn2/2pp4/3P4/1QNBPN2/PP3PPP/R3KB1R w - - 0 1", + "8/5k2/8/3K4/8/8/8/Q7 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + static const COOR rgcQueen[3] = { D1, B3, A1 }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking queen move generation: mailbox vs " + "_GenerateQueenBB (interleaved, %lu calls/position)...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + ASSERT(IS_QUEEN(posBench.rgSquare[rgcQueen[u]].pPiece)); + ASSERT(GET_COLOR(posBench.rgSquare[rgcQueen[u]].pPiece) == + posBench.uToMove); + + ctx->sMoveStack.bbFriendlyOccupied = + _BuildFriendlySideBB(&posBench, posBench.uToMove); + ctx->sMoveStack.bbOccupied = _BuildFullOccupiedBB(&posBench); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + GenerateQueen(&ctx->sMoveStack, &posBench, rgcQueen[u]); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateQueenBB(&ctx->sMoveStack, &posBench, rgcQueen[u]); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, _GenerateQueenBB %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} + +// +// Whole-node dispatch benchmark: _GenerateAllMoves (mailbox +// cNonPawns/JumpTable dispatch) vs _GenerateAllMovesBB (direct calls +// off pos->bbPieces, no indirect branch) -- see _GenerateAllMovesBB's +// block comment in generate.c. Unlike every other benchmark in this +// file, this measures the dispatch layer itself, not an individual +// piece-type generator in isolation -- the level this migration's +// indirect-call-misprediction hypothesis actually predicts a win at. +// Must be run in a build with none of the GENERATE_*_BITBOARD toggles +// defined, so _GenerateAllMoves keeps its real name (not +// macro-substituted to _GenerateAllMovesBB) and both are directly +// comparable under their own names in one binary. +// +void +TestGenerateAllMovesSpeed(void) +{ + static const char *rgszFen[3] = + { + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", + "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1", + "6k1/8/8/3K4/8/2NBRQ2/8/8 w - - 0 1", + }; + static const char *rgszLabel[3] = + { + "opening ", "middlegame", "endgame ", + }; + POSITION posBench; + SEARCHER_THREAD_CONTEXT *ctx; + UINT64 u64MailboxTotal, u64BBTotal, u64Start; + ULONG uIter, u; + ULONG uPly; + const ULONG uCallsPerPosition = 200000; + + Trace("Benchmarking whole-node move generation dispatch: " + "_GenerateAllMoves (mailbox JumpTable) vs _GenerateAllMovesBB " + "(direct bbPieces dispatch), interleaved, %lu calls/position " + "-- only meaningful in a toggle-free build...\n", + uCallsPerPosition); + + ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); + ASSERT(ctx); + uPly = ctx->uPly; + + for (u = 0; u < 3; u++) + { + FenToPosition(&posBench, (char *)rgszFen[u]); + InitializeSearcherContext(&posBench, ctx); + + u64MailboxTotal = 0; + u64BBTotal = 0; + for (uIter = 0; uIter < uCallsPerPosition; uIter++) + { + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateAllMoves(&ctx->sMoveStack, &posBench); + u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start); + + ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; + u64Start = SystemReadTimeStampCounter(); + _GenerateAllMovesBB(&ctx->sMoveStack, &posBench); + u64BBTotal += (SystemReadTimeStampCounter() - u64Start); + } + printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT + " cycles/call, BB dispatch %" + COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " + "(BB is %.2fx mailbox)\n", + rgszLabel[u], + u64MailboxTotal / uCallsPerPosition, + u64BBTotal / uCallsPerPosition, + (double)u64BBTotal / (double)u64MailboxTotal); + } + SystemFreeMemory(ctx); +} #endif -- cgit v1.3