path: root/src/testsee.c

/**

Copyright (c) Scott Gasch

Module Name:

    testsee.c

Abstract:

    This code is meant to sanity check the SEE routine.  It works by
    using the generator and MakeMove/UnmakeMove to play out a sequence
    of moves on a single square.  It's somewhat useful code but right
    now I don't really use it because it is too good: it detects
    things like pieces that are pinned against the king whereas the
    SEE itself does not.  Still, I'd want to run it and verify the
    discrepencies if I was doing much work in the SEE code.

Author:

    Scott Gasch ([email protected]) 21 Oct 2004

Revision History:

**/

#include "chess.h"

// This harness's job is to validate _GetAttacksBB against a fixed
// baseline (the real asm/CROUTINES implementation), not to compare
// the engine's own current GetAttacks macro target against itself --
// but chess.h's GETATTACKS_BITBOARD toggle (board_representation/
// MIGRATION.md section 6) can make that macro resolve to
// _GetAttacksBB. Undefine it here so every "GetAttacks(...)" call
// below always reaches the real asm/CROUTINES function (still
// declared under that name in chess.h, just no longer macro-routed),
// regardless of which implementation is live in production.
#ifdef GetAttacks
#undef GetAttacks
#endif

// Same reasoning, for IsAttacked/InCheck (board_representation/
// MOVEGEN_MIGRATION.md section 6b's ISATTACKED_BITBOARD toggle):
// TestIsAttackedBB below must always be able to call the real mailbox
// IsAttacked by name and compare it against IsAttackedBB explicitly,
// regardless of which one chess.h's macro currently routes plain
// "IsAttacked(...)" calls to elsewhere in the engine.
#ifdef IsAttacked
#undef IsAttacked
#endif
#ifdef InCheck
#undef InCheck
#endif

#ifdef TEST_BROKEN
ULONG g_uRootOnMove;

SCORE
DebugSEERecursive(SEARCHER_THREAD_CONTEXT *ctx,
                  MOVE mv)
{
    SCORE i, iMinMax;
    ULONG x;
    MOVE mvReply;
    ULONG uToMove = ctx->sPosition.uToMove;

    //
    // Make the move, this is not optional
    //
    ASSERT(GET_COLOR(mv.pMoved) == uToMove);
    if (FALSE == MakeMove(ctx, mv))
    {
        return(INVALID_SCORE);
    }

    //
    // Initialize MinMax to the stand pat score here so that the reply
    // can be "something else".
    //
    iMinMax = ((ctx->sPosition.uPawnMaterial[g_uRootOnMove] +
                ctx->sPosition.uNonPawnMaterial[g_uRootOnMove]) -
               (ctx->sPosition.uPawnMaterial[FLIP(g_uRootOnMove)] +
                ctx->sPosition.uNonPawnMaterial[FLIP(g_uRootOnMove)]));

    //
    // Generate the reply moves.
    //
    GenerateMoves(ctx, (MOVE){0}, GENERATE_DONT_SCORE);
    for (x = ctx->sMoveStack.uBegin[ctx->uPly];
         x < ctx->sMoveStack.uEnd[ctx->uPly];
         x++)
    {
        //
        // Only consider replies that end up on the same sq as the
        // move.
        //
        mvReply = ctx->sMoveStack.mvf[x].mv;
        ASSERT(SanityCheckMove(&ctx->sPosition, mvReply));
        if (mvReply.cTo != mv.cTo)
        {
            continue;
        }
        
        i = DebugSEERecursive(ctx, mvReply);
        if (INVALID_SCORE != i)
        {
            if ((ctx->uPly % 2) == 0)
            {
                if (i > iMinMax) iMinMax = i;
            }
            else
            {
                if (i < iMinMax) iMinMax = i;
            }
        }
    }

    //
    // Unmake the original move
    //
    UnmakeMove(ctx, mv);
    return(iMinMax);
}

    
SCORE
DebugSEE(POSITION *pos,
         MOVE mv)
{
    SCORE iRootBalance = ((pos->uPawnMaterial[pos->uToMove] +
                           pos->uNonPawnMaterial[pos->uToMove]) -
                          (pos->uPawnMaterial[FLIP(pos->uToMove)] +
                           pos->uNonPawnMaterial[FLIP(pos->uToMove)]));
    SCORE iAfterExchange = iRootBalance;
    SEARCHER_THREAD_CONTEXT *ctx = 
        malloc(sizeof(SEARCHER_THREAD_CONTEXT));

    g_uRootOnMove = pos->uToMove;
    if (NULL != ctx)
    {
        pos->uDangerCount[BLACK] = pos->uDangerCount[WHITE] = 0;
        InitializeSearcherContext(pos, ctx);
        
        GenerateMoves(ctx, (MOVE){0}, GENERATE_DONT_SCORE);
        mv.bvFlags |= WouldGiveCheck(ctx, mv);
        if (InCheck(pos, pos->uToMove))
        {
            mv.bvFlags |= MOVE_FLAG_ESCAPING_CHECK;
        }

        iAfterExchange = DebugSEERecursive(ctx, mv);
        if (iAfterExchange != INVALID_SCORE)
        {
            iAfterExchange -= iRootBalance;
        }
        free(ctx);
    }
    return(iAfterExchange);
}
#endif

#ifdef TEST
static int
_SeeListEntryCompare(const void *pA, const void *pB)
{
    const SEE_THREESOME *a = (const SEE_THREESOME *)pA;
    const SEE_THREESOME *b = (const SEE_THREESOME *)pB;
    if (a->cLoc != b->cLoc) return ((int)a->cLoc - (int)b->cLoc);
    return ((int)a->pPiece - (int)b->pPiece);
}

FLAG
SeeListsAreEqual(SEE_LIST *pA, SEE_LIST *pB)
{
    // Order-independent: GetAttacks's caller (SEE()) sorts/heaps the
    // list immediately after it's populated, so a bitboard-based
    // GetAttacks returning the same *set* of attackers in a different
    // order is a correct match, not a bug (board_representation/
    // MIGRATION.md section 4). Sort a scratch copy of each by
    // (cLoc, pPiece) before comparing field-by-field.
    SEE_LIST sA = *pA;
    SEE_LIST sB = *pB;
    ULONG u;

    if (sA.uCount != sB.uCount) return FALSE;
    qsort(sA.data, sA.uCount, sizeof(sA.data[0]), _SeeListEntryCompare);
    qsort(sB.data, sB.uCount, sizeof(sB.data[0]), _SeeListEntryCompare);
    for (u = 0; u < sA.uCount; u++)
    {
        if ((sA.data[u].pPiece != sB.data[u].pPiece) ||
            (sA.data[u].cLoc != sB.data[u].cLoc) ||
            (sA.data[u].uVal != sB.data[u].uVal))
        {
            return FALSE;
        }
    }
    return TRUE;
}

void
TestGetAttacks(void) 
{
    POSITION pos;
    ULONG u;
    COOR c;
    SEE_LIST rgSlowList;
    SEE_LIST rgAsmList;
    SEE_LIST rgBBList;
    ULONG color;

#if !defined(_X86_) && !defined(_X64_)
    return;
#endif

    Trace("Testing GetAttacks...\n");
    for (u = 0; u < 20000; u++)
    {
        GenerateRandomLegalPosition(&pos);
        FOREACH_SQUARE(c)
        {
            if (!IS_ON_BOARD(c)) continue;
            for (color = BLACK; color <= WHITE; color++)
            {
                SlowGetAttacks(&rgSlowList,
                               &pos,
                               c,
                               color);
                GetAttacks(&rgAsmList,
                           &pos,
                           c,
                           color);
                if (!SeeListsAreEqual(&rgSlowList, &rgAsmList))
                {
                    UtilPanic(TESTCASE_FAILURE,
                              &pos,
                              "SEE_LIST mismatch", &rgSlowList, &rgAsmList,
                              __FILE__, __LINE__);
                }

                // board_representation/MIGRATION.md section 3/4:
                // bbPieces-backed GetAttacks PoC, same correctness
                // gate as the asm/C comparison above.
                _GetAttacksBB(&rgBBList,
                              &pos,
                              c,
                              color);
                if (!SeeListsAreEqual(&rgSlowList, &rgBBList))
                {
                    UtilPanic(TESTCASE_FAILURE,
                              &pos,
                              "SEE_LIST mismatch (_GetAttacksBB)",
                              &rgSlowList, &rgBBList,
                              __FILE__, __LINE__);
                }
            }
        }
    }

    //
    // Speed: board_representation/MIGRATION.md section 5's isolated
    // cycles/call microbenchmark, pulled forward here since it's cheap
    // to add right alongside the correctness gate that just proved the
    // two implementations equivalent. Three positions spanning piece
    // density (opening/middlegame/endgame), SlowGetAttacks vs
    // _GetAttacksBB interleaved call-by-call (not phase-by-phase) to
    // cancel shared-box noise -- a red flag (flat or inverted result)
    // here would mean stopping before wiring this in any further, same
    // as the Eval occupancy-bitboard work that motivated this file.
    {
        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/4R3 w - - 0 1",
        };
        static const char *rgszLabel[3] =
        {
            "opening   ", "middlegame", "endgame   ",
        };
        POSITION posBench;
        SEE_LIST rgList;
        UINT64 u64SlowTotal, u64AsmTotal, u64BBTotal, u64Start;
        ULONG uIter;
        ULONG uSq;
        COOR cBench;
        ULONG uSide;
        const ULONG uCallsPerPosition = 200000;

        // GetAttacks (unqualified) is the real production entry point --
        // the hand-tuned x86/x64 asm routine, not SlowGetAttacks (the C
        // reference used only for correctness comparison above). That's
        // the actual competitor _GetAttacksBB has to beat; SlowGetAttacks
        // is included only as a third data point, not the bar to clear.
        Trace("Benchmarking GetAttacks: asm GetAttacks vs SlowGetAttacks "
              "vs _GetAttacksBB (interleaved, %lu calls/position)...\n",
              uCallsPerPosition);
        for (u = 0; u < 3; u++)
        {
            FenToPosition(&posBench, (char *)rgszFen[u]);
            u64SlowTotal = 0;
            u64AsmTotal = 0;
            u64BBTotal = 0;
            for (uIter = 0; uIter < uCallsPerPosition; uIter++)
            {
                uSq = uIter % 64;
                cBench = BIT_NUMBER_TO_COOR(uSq);
                uSide = uIter & 1;
                if (!IS_ON_BOARD(cBench)) continue;

                u64Start = SystemReadTimeStampCounter();
                GetAttacks(&rgList, &posBench, cBench, uSide);
                u64AsmTotal += (SystemReadTimeStampCounter() - u64Start);

                u64Start = SystemReadTimeStampCounter();
                SlowGetAttacks(&rgList, &posBench, cBench, uSide);
                u64SlowTotal += (SystemReadTimeStampCounter() - u64Start);

                u64Start = SystemReadTimeStampCounter();
                _GetAttacksBB(&rgList, &posBench, cBench, uSide);
                u64BBTotal += (SystemReadTimeStampCounter() - u64Start);
            }
            printf(" %s: asm GetAttacks %" COMPILER_LONGLONG_UNSIGNED_FORMAT
                   " cycles/call, SlowGetAttacks %"
                   COMPILER_LONGLONG_UNSIGNED_FORMAT
                   " cycles/call, _GetAttacksBB %"
                   COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call "
                   "(BB is %.2fx asm)\n",
                   rgszLabel[u],
                   u64AsmTotal / uCallsPerPosition,
                   u64SlowTotal / uCallsPerPosition,
                   u64BBTotal / uCallsPerPosition,
                   (double)u64BBTotal / (double)u64AsmTotal);
        }
    }
}

// board_representation/MOVEGEN_MIGRATION.md section 6b: direct
// comparison harness for IsAttacked/IsAttackedBB, same pattern as
// TestGetAttacks above -- mailbox vs. bitboard, same inputs, must
// match exactly. This is the piece ExposesCheckBB didn't get before
// shipping and had to be debugged the hard way instead (two real bugs
// found via TestSan/perft/DEBUG-assert failures rather than a direct
// comparison); doing it properly here from the start.
void
TestIsAttackedBB(void)
{
    POSITION pos;
    ULONG u;
    COOR c;
    ULONG uSide;
    FLAG fMailbox, fBB;

    Trace("Testing IsAttacked...\n");
    for (u = 0; u < 20000; u++)
    {
        GenerateRandomLegalPosition(&pos);
        FOREACH_SQUARE(c)
        {
            if (!IS_ON_BOARD(c)) continue;
            for (uSide = BLACK; uSide <= WHITE; uSide++)
            {
                fMailbox = IsAttacked(c, &pos, uSide);
                fBB = IsAttackedBB(c, &pos, uSide);
                if (fMailbox != fBB)
                {
                    UtilPanic(TESTCASE_FAILURE,
                              &pos,
                              "IsAttacked/IsAttackedBB mismatch",
                              NULL, NULL,
                              __FILE__, __LINE__);
                }
            }
        }
        for (uSide = BLACK; uSide <= WHITE; uSide++)
        {
            fMailbox = InCheck(&pos, uSide);
            fBB = InCheckBB(&pos, uSide);
            if (fMailbox != fBB)
            {
                UtilPanic(TESTCASE_FAILURE,
                          &pos,
                          "InCheck/InCheckBB mismatch",
                          NULL, NULL,
                          __FILE__, __LINE__);
            }
        }
    }

    //
    // Speed: same isolated cycles/call methodology as TestGetAttacks
    // above, interleaved call-by-call to cancel shared-box noise.
    //
    {
        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/4R3 w - - 0 1",
        };
        static const char *rgszLabel[3] =
        {
            "opening   ", "middlegame", "endgame   ",
        };
        POSITION posBench;
        UINT64 u64MailboxTotal, u64BBTotal, u64Start;
        ULONG uIter;
        ULONG uSq;
        COOR cBench;
        ULONG uSideBench;
        const ULONG uCallsPerPosition = 200000;
        FLAG fSink;

        Trace("Benchmarking IsAttacked: mailbox vs IsAttackedBB "
              "(interleaved, %lu calls/position)...\n",
              uCallsPerPosition);
        for (u = 0; u < 3; u++)
        {
            FenToPosition(&posBench, (char *)rgszFen[u]);
            u64MailboxTotal = 0;
            u64BBTotal = 0;
            for (uIter = 0; uIter < uCallsPerPosition; uIter++)
            {
                uSq = uIter % 64;
                cBench = BIT_NUMBER_TO_COOR(uSq);
                uSideBench = uIter & 1;
                if (!IS_ON_BOARD(cBench)) continue;

                u64Start = SystemReadTimeStampCounter();
                fSink = IsAttacked(cBench, &posBench, uSideBench);
                u64MailboxTotal += (SystemReadTimeStampCounter() - u64Start);

                u64Start = SystemReadTimeStampCounter();
                fSink = IsAttackedBB(cBench, &posBench, uSideBench);
                u64BBTotal += (SystemReadTimeStampCounter() - u64Start);
                (void)fSink;
            }
            printf(" %s: mailbox %" COMPILER_LONGLONG_UNSIGNED_FORMAT
                   " cycles/call, IsAttackedBB %"
                   COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/call "
                   "(BB is %.2fx mailbox)\n",
                   rgszLabel[u],
                   u64MailboxTotal / uCallsPerPosition,
                   u64BBTotal / uCallsPerPosition,
                   (double)u64BBTotal / (double)u64MailboxTotal);
        }
    }
}
#endif // TEST