/**

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);
}

//
// 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);
}

//
// board_representation/MOVEGEN_MIGRATION.md's never-started
// _FindUnblockedSquares/WouldGiveCheck candidate. Unlike every other
// benchmark in this file, this does NOT measure the generator call in
// isolation: _FindUnblockedSquares 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 _FindUnblockedSquares(BB) 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. WouldGiveCheck's own body is selected at
// compile time by UNBLOCKED_BITBOARD (SQUARE_IS_UNBLOCKED/
// DIR_FROM_SQ_TO_KING), so unlike TestGenerateAllMovesSpeed this can't
// compare both implementations by name in one binary -- run this test
// in two builds (with and without -DUNBLOCKED_BITBOARD) and compare
// the printed cycles/pair across them.
//
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 _FindUnblockedSquares%s + WouldGiveCheck over "
          "a generated move list (%lu calls/position) -- compare this "
          "build's numbers against a build with the opposite "
          "-DUNBLOCKED_BITBOARD setting...\n",
#ifdef UNBLOCKED_BITBOARD
          "BB",
#else
          " (mailbox)",
#endif
          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;
#ifdef UNBLOCKED_BITBOARD
        _FindUnblockedSquaresBB(pStack, &posBench);
#else
        _FindUnblockedSquares(pStack, &posBench);
#endif
        _GenerateAllMoves(pStack, &posBench);
        uNumMoves = MOVE_COUNT(ctx, uPly);
        ASSERT(uNumMoves > 0);

        u64Total = 0;
        for (uIter = 0; uIter < uCallsPerPosition; uIter++)
        {
            u64Start = SystemReadTimeStampCounter();
#ifdef UNBLOCKED_BITBOARD
            _FindUnblockedSquaresBB(pStack, &posBench);
#else
            _FindUnblockedSquares(pStack, &posBench);
#endif
            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",
        "rnbqkbnr/pp1ppppp/8/2pP4/8/8/PPP1PPPP/RNBQKBNR b KQkq c6 0 2",
        "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