/** Copyright (c) Scott Gasch Module Name: testgenerate.c Abstract: Test the move generator. Author: Scott Gasch (scott.gasch@gmail.com) 12 May 2004 Revision History: $Id: testgenerate.c 345 2007-12-02 22:56:42Z scott $ **/ #ifdef TEST #include "chess.h" UINT64 g_uPlyTestLeafNodeCount = 0; UINT64 g_uPlyTestTotalNodeCount = 0; extern CHAR *GenerateRandomLegalFenString(); void PlyTest(SEARCHER_THREAD_CONTEXT *ctx, ULONG uDepth, FLAG fInCheck) { ULONG u; MOVE mv; ULONG uPly = ctx->uPly; FLAG fGivesCheck; #if DEBUG POSITION board; memcpy(&board, &(ctx->sPosition), sizeof(POSITION)); #endif if (uDepth > MAX_PLY_PER_SEARCH) { return; } else if (uDepth == 0) { g_uPlyTestTotalNodeCount++; g_uPlyTestLeafNodeCount++; return; } g_uPlyTestTotalNodeCount++; mv.uMove = 0; GenerateMoves(ctx, mv, (fInCheck ? GENERATE_ESCAPES : GENERATE_ALL_MOVES)); for (u = ctx->sMoveStack.uBegin[uPly]; u < ctx->sMoveStack.uEnd[uPly]; u++) { mv = ctx->sMoveStack.mvf[u].mv; mv.bvFlags |= WouldGiveCheck(ctx, mv); if (MakeMove(ctx, mv)) { ASSERT(!InCheck(&ctx->sPosition, GET_COLOR(mv.pMoved))); fGivesCheck = IS_CHECKING_MOVE(mv); #ifdef DEBUG if (fGivesCheck) { ASSERT(InCheck(&ctx->sPosition, FLIP(GET_COLOR(mv.pMoved)))); } else { ASSERT(!InCheck(&ctx->sPosition, FLIP(GET_COLOR(mv.pMoved)))); } #endif PlyTest(ctx, uDepth - 1, fGivesCheck); UnmakeMove(ctx, mv); ASSERT(PositionsAreEquivalent(&board, &ctx->sPosition)); } } } void TestMoveGenerator(void) { typedef struct _TEST_MOVEGEN { char *szFen; UINT64 uLeaves[7]; } TEST_MOVEGEN; TEST_MOVEGEN x[] = { { "3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1", { 218, 0, 0, 0, 0, 0, 0 } }, { "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - - 0 0", { 48, 2039, 97862, 4085603, 193690690ULL, 8031647685ULL } }, { "8/PPP4k/8/8/8/8/4Kppp/8 w - - 0 0", { 18, 290, 5044, 89363, 1745545, 34336777ULL, 749660761ULL } }, { "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 0", { 14, 191, 2812, 43238, 674624, 11030083ULL, 78633661ULL } }, { "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 0", { 20, 400, 8902, 197281, 4865609, 119060324ULL, 3195901860ULL } }, }; ULONG u, v; SEARCHER_THREAD_CONTEXT *ctx; POSITION pos; Trace("Testing move generator...\n"); ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); ASSERT(ctx); for (u = 0; u < ARRAY_LENGTH(x); u++) { if (FALSE == FenToPosition(&pos, x[u].szFen)) { UtilPanic(INCONSISTENT_STATE, NULL, NULL, NULL, NULL, __FILE__, __LINE__); } InitializeSearcherContext(&pos, ctx); for (v = 1; v <= 4; v++) { g_uPlyTestLeafNodeCount = 0; g_uPlyTestTotalNodeCount = 0; PlyTest(ctx, v, FALSE); if ((x[u].uLeaves[v-1]) && (g_uPlyTestLeafNodeCount != x[u].uLeaves[v-1])) { UtilPanic(TESTCASE_FAILURE, NULL, "Perft", NULL, NULL, __FILE__, __LINE__); } } } SystemFreeMemory(ctx); } void TestLegalMoveGenerator(void) { ULONG u, v; CHAR *p; POSITION pos; SEARCHER_THREAD_CONTEXT *ctx; MOVE mv; #ifdef DEBUG ULONG uLegalKingMoves; #endif ULONG uTotalLegalMoves; Trace("Testing legal move generator...\n"); ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); ASSERT(ctx); u = 0; do { switch(rand() % 10) { case 0: p = "8/2K1p2k/1Q2B1p1/2N5/q4q2/3p2Pp/7P/8 w - - 2 0"; break; default: p = GenerateRandomLegalFenString(); break; } if (FALSE == FenToPosition(&pos, p)) { UtilPanic(TESTCASE_FAILURE, NULL, "FenToPosition", NULL, NULL, __FILE__, __LINE__); } if (FALSE == IsBoardLegal(&pos)) { continue; } if (TRUE == InCheck(&pos, pos.uToMove)) { #ifdef DEBUG uLegalKingMoves = 0; #endif uTotalLegalMoves = 0; InitializeSearcherContext(&pos, ctx); mv.uMove = 0; GenerateMoves(ctx, mv, GENERATE_ESCAPES); for (v = ctx->sMoveStack.uBegin[0]; v < ctx->sMoveStack.uEnd[0]; v++) { mv = ctx->sMoveStack.mvf[v].mv; ASSERT(mv.bvFlags & MOVE_FLAG_ESCAPING_CHECK); if (TRUE == MakeMove(ctx, mv)) { uTotalLegalMoves++; #ifdef DEBUG if (IS_KING(mv.pMoved)) { uLegalKingMoves++; } #endif UnmakeMove(ctx, mv); } else { ctx->sMoveStack.mvf[v].mv.uMove = 0; } } ASSERT(NUM_KING_MOVES(ctx, ctx->uPly) == uLegalKingMoves); if (uTotalLegalMoves > 1) { ASSERT(!ONE_LEGAL_MOVE(ctx, ctx->uPly)); } else if (uTotalLegalMoves == 1) { ASSERT(ONE_LEGAL_MOVE(ctx, ctx->uPly)); } u++; } } while(u < 1000); 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); } // // board_representation/MOVEGEN_MIGRATION.md's never-started // _FindUnblockedSquaresBB/WouldGiveCheck candidate. Unlike every other // benchmark in this file, this does NOT measure the generator call in // isolation: _FindUnblockedSquaresBB writes ~20 square entries that may // never be read, and WouldGiveCheck reads only 1-3 of them per move, // so a bitboard version that looks like a big win building the table // can give some of it back at query time. The real per-node cost is // the pair -- one _FindUnblockedSquaresBB call followed by // WouldGiveCheck over every move actually generated at that node -- // so that's what gets timed here, same interleaved-call methodology // as the rest of this file. // void TestFindUnblockedSquaresSpeed(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 u64Total, u64Start; ULONG uIter, u, uMove, uNumMoves; ULONG uPly; MOVE_STACK *pStack; const ULONG uCallsPerPosition = 50000; Trace("Benchmarking _FindUnblockedSquaresBB + WouldGiveCheck over " "a generated move list (%lu calls/position)...\n", uCallsPerPosition); ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); ASSERT(ctx); pStack = &(ctx->sMoveStack); uPly = ctx->uPly; for (u = 0; u < 3; u++) { FenToPosition(&posBench, (char *)rgszFen[u]); InitializeSearcherContext(&posBench, ctx); // Generate once, outside the timed loop, to get a realistic // move list for this position -- WouldGiveCheck's cost is // what's under test here, not generation itself. pStack->uEnd[uPly] = pStack->uBegin[uPly]; pStack->sGenFlags[uPly].uAllGenFlags = 0; _FindUnblockedSquaresBB(pStack, &posBench); _GenerateAllMoves(pStack, &posBench); uNumMoves = MOVE_COUNT(ctx, uPly); ASSERT(uNumMoves > 0); #ifdef DEBUG // Calling _GenerateAllMoves directly (above), not the // GenerateMoves wrapper, skips the DEBUG-only // pStack->board[uPly] snapshot GenerateMoves normally takes // (generate.c, right before it dispatches to a generator) -- // WouldGiveCheck's own ASSERT(PositionsAreEquivalent(...)) // checks the move it's given against exactly that snapshot, // so without this, WouldGiveCheck below trips on whatever // stale snapshot happened to be sitting in pStack->board[uPly] // from some earlier, unrelated call. posBench never changes // for the rest of this position's timed loop (no MakeMove // happens here), so one copy here is sufficient, not one per // iteration. 2026-10-15: found via the first DEBUG+TEST // combined build this self-test suite had ever been run // under. memcpy(&(pStack->board[uPly]), &posBench, sizeof(POSITION)); #endif u64Total = 0; for (uIter = 0; uIter < uCallsPerPosition; uIter++) { u64Start = SystemReadTimeStampCounter(); _FindUnblockedSquaresBB(pStack, &posBench); for (uMove = pStack->uBegin[uPly]; uMove < pStack->uEnd[uPly]; uMove++) { WouldGiveCheck(ctx, pStack->mvf[uMove].mv); } u64Total += (SystemReadTimeStampCounter() - u64Start); } printf(" %s: %" COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/pair (%lu moves checked per call)\n", rgszLabel[u], u64Total / uCallsPerPosition, uNumMoves); } SystemFreeMemory(ctx); } #if defined(CAPTURES_PROMS_BITBOARD_PATH) static int _CompareU32(const void *pA, const void *pB) { const ULONG *a = (const ULONG *)pA; const ULONG *b = (const ULONG *)pB; if (*a < *b) return -1; if (*a > *b) return 1; return 0; } // // Correctness gate for _GenerateCapturesAndPromotions // (generate.c, the GENERATE_CAPTURES_PROMS bitboard path): its output // must equal _GenerateAllMoves' output filtered down to // IS_CAPTURE_OR_PROMOTION(mv), as a SET (mv.uMove already encodes // cFrom/cTo/pMoved/pCaptured/pPromoted/flags, so set membership is a // direct ULONG compare -- no need to decode fields individually). Both // generators read the identical board, so a true mismatch here means // one of them is wrong, not a representational difference. Covers // ordinary captures, capture-promotions, quiet push-promotions, en // passant, and (implicitly, by their absence from both outputs) that // castling and ordinary quiet pushes never show up in either side of // the comparison. // void TestCapturesAndPromotionsGenerator(void) { static const char *rgszFen[] = { "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR b KQkq - 0 1", "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R b KQkq - 0 1", "8/PPP4k/8/8/8/8/4Kppp/8 w - - 0 1", "8/PPP4k/8/8/8/8/4Kppp/8 b - - 0 1", "3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1", "rnbqkbnr/ppp1p1pp/8/3pPp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3", "rnbqkbnr/pp1p1ppp/8/2pPp3/8/8/PPP1PPPP/RNBQKBNR w KQkq c6 0 3", // 2026-10-15: this used to read "...b KQkq c6 0 2" -- an ep // square on rank 6 is only reachable with WHITE to move (it // records a BLACK pawn's just-played double push), so pairing // it with "b" (Black to move) was self-contradictory and // unreachable through real play. FenToPosition never rejected // it (it isn't routed through SetRootPosition's IsBoardLegal // gate), so the move generator ran en passant generation // against a position whose ep square didn't correspond to // the side to move at all -- see board.c's IsBoardLegal for // the check that would now catch this same mistake if it // arrived via `setboard`. Replaced with a genuine Black-to- // move en passant position (White just played c2-c4, passing // over c3; Black's pawn already on d4 can capture there). "rnbqkbnr/ppp1pppp/8/8/2Pp4/8/PP1PPPPP/RNBQKBNR b KQkq c3 0 3", "8/1P6/8/8/8/8/7p/1k4K1 w - - 0 1", "8/1P6/8/8/8/8/7p/1k4K1 b - - 0 1", "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 b - - 0 1", }; POSITION pos; SEARCHER_THREAD_CONTEXT *ctx; MOVE_STACK *pStack; ULONG uPly; ULONG u, v; ULONG uRefCount, uNewCount; static ULONG rgRef[MAX_MOVES_PER_PLY]; static ULONG rgNew[MAX_MOVES_PER_PLY]; MOVE mv; Trace("Testing captures/promotions-only generator against " "_GenerateAllMoves filtered to IS_CAPTURE_OR_PROMOTION...\n"); ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT)); ASSERT(ctx); pStack = &(ctx->sMoveStack); uPly = ctx->uPly; for (u = 0; u < ARRAY_LENGTH(rgszFen); u++) { if (FALSE == FenToPosition(&pos, (char *)rgszFen[u])) { UtilPanic(TESTCASE_FAILURE, NULL, "FenToPosition", NULL, NULL, __FILE__, __LINE__); } InitializeSearcherContext(&pos, ctx); // GENERATE_CAPTURES_PROMS' own precondition (see GenerateMoves' // ASSERT) -- none of the fixtures above should trip this, but // don't assume it of a future addition. if (TRUE == InCheck(&pos, pos.uToMove)) { continue; } // Reference: full generation, filtered to captures/promotions. pStack->uEnd[uPly] = pStack->uBegin[uPly]; pStack->sGenFlags[uPly].uAllGenFlags = 0; _GenerateAllMoves(pStack, &pos); uRefCount = 0; for (v = pStack->uBegin[uPly]; v < pStack->uEnd[uPly]; v++) { mv = pStack->mvf[v].mv; if (IS_CAPTURE_OR_PROMOTION(mv)) { ASSERT(uRefCount < MAX_MOVES_PER_PLY); rgRef[uRefCount++] = mv.uMove; } } // Candidate: the new generator, directly. pStack->uEnd[uPly] = pStack->uBegin[uPly]; pStack->sGenFlags[uPly].uAllGenFlags = 0; _GenerateCapturesAndPromotions(pStack, &pos); uNewCount = 0; for (v = pStack->uBegin[uPly]; v < pStack->uEnd[uPly]; v++) { mv = pStack->mvf[v].mv; ASSERT(IS_CAPTURE_OR_PROMOTION(mv)); ASSERT(uNewCount < MAX_MOVES_PER_PLY); rgNew[uNewCount++] = mv.uMove; } if (uRefCount != uNewCount) { Trace("TestCapturesAndPromotionsGenerator: FEN %s: " "reference produced %lu move(s), new produced %lu\n", rgszFen[u], uRefCount, uNewCount); UtilPanic(TESTCASE_FAILURE, NULL, "TestCapturesAndPromotionsGenerator", NULL, NULL, __FILE__, __LINE__); } // Set equality -- the two generators walk pieces in different // orders, so sort both before the element-by-element compare. qsort(rgRef, uRefCount, sizeof(rgRef[0]), _CompareU32); qsort(rgNew, uNewCount, sizeof(rgNew[0]), _CompareU32); for (v = 0; v < uRefCount; v++) { if (rgRef[v] != rgNew[v]) { Trace("TestCapturesAndPromotionsGenerator: FEN %s: " "move set mismatch at sorted index %lu " "(ref 0x%08lx, new 0x%08lx)\n", rgszFen[u], v, (unsigned long)rgRef[v], (unsigned long)rgNew[v]); UtilPanic(TESTCASE_FAILURE, NULL, "TestCapturesAndPromotionsGenerator", NULL, NULL, __FILE__, __LINE__); } } } SystemFreeMemory(ctx); } // // Speed gate: _GenerateCapturesAndPromotions must be faster than // _GenerateAllMoves for the same position, interleaved-call // methodology matching every other *Speed test in this file. Unlike // the per-piece-type speed tests above, this isn't comparing two // implementations of the same move set -- the new generator produces // fewer moves by design -- so this is purely "does skipping the quiet // moves up front actually cost less than generating and discarding // them," the actual claim behind building this generator at all. // void TestGenerateCapturesAndPromotionsSpeed(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", "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", }; static const char *rgszLabel[3] = { "opening ", "middlegame", "tactical ", }; POSITION posBench; SEARCHER_THREAD_CONTEXT *ctx; UINT64 u64AllTotal, u64CapsTotal, u64Start; ULONG uIter, u; ULONG uPly; const ULONG uCallsPerPosition = 200000; Trace("Benchmarking whole-node move generation: _GenerateAllMoves " "vs _GenerateCapturesAndPromotions (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(!InCheck(&posBench, posBench.uToMove)); u64AllTotal = 0; u64CapsTotal = 0; for (uIter = 0; uIter < uCallsPerPosition; uIter++) { ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; u64Start = SystemReadTimeStampCounter(); _GenerateAllMoves(&ctx->sMoveStack, &posBench); u64AllTotal += (SystemReadTimeStampCounter() - u64Start); ctx->sMoveStack.uEnd[uPly] = ctx->sMoveStack.uBegin[uPly]; u64Start = SystemReadTimeStampCounter(); _GenerateCapturesAndPromotions(&ctx->sMoveStack, &posBench); u64CapsTotal += (SystemReadTimeStampCounter() - u64Start); } printf(" %s: _GenerateAllMoves %" COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call, _GenerateCapturesAndPromotions %" COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call " "(captures-only is %.2fx all-moves)\n", rgszLabel[u], u64AllTotal / uCallsPerPosition, u64CapsTotal / uCallsPerPosition, (double)u64CapsTotal / (double)u64AllTotal); if (u64CapsTotal >= u64AllTotal) { UtilPanic(TESTCASE_FAILURE, NULL, "TestGenerateCapturesAndPromotionsSpeed: not faster", NULL, NULL, __FILE__, __LINE__); } } SystemFreeMemory(ctx); } #endif // captures/promotions bitboard path #endif