Speed up eval/move-gen/SEE; remove EvalLookForDanger, overhaul _EvalKing

SPRT-confirmed improvement (1814 games, st 4.0): candidate nps=1498118
vs head=1378448, avg depth 14.30 vs 13.87, ELO=+24.2+/-16.0,
LOWER95=0.5118, LLR=+3.126 crossing the H1 bound.

Most of the diff is non-semantic speed work across eval.c, generate.c,
movesup.c, see.c, probe.c and friends. Two real semantic changes:
removed EvalLookForDanger and overhauled _EvalKing's king-safety scoring.

Co-Authored-By: Claude Sonnet 5 <[email protected]>

1 files changed, 322 insertions, 0 deletions

diff --git a/src/testgenerate.c b/src/testgenerate.c
index c6947d2..95c5000 100644
--- a/src/testgenerate.c
+++ b/src/testgenerate.c
@@ -697,4 +697,326 @@ TestGenerateAllMovesSpeed(void)
     }
     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