path: root/src/testsearch.c

/**

Copyright (c) Scott Gasch

Module Name:

    testsearch.c

Abstract:

    This is a test module to sanity check the search code.  It
    operates by generating a random legal chess position and
    performing a two-ply search on the position.  It is expected that
    the search will terminate and return a legal move.

Author:

    Scott Gasch ([email protected]) 2 Jan 2005

Revision History:

**/

#include "chess.h"

#ifdef TEST
#define TIME_LIMIT 200.0

void
SetMoveTimerForTestingSearch(void)
{
    g_MoveTimer.uNodeCheckMask = 0x10000 - 1;
    g_MoveTimer.dStartTime = SystemTimeStamp();
    g_MoveTimer.bvFlags = 0;
    g_MoveTimer.dSoftTimeLimit = g_MoveTimer.dStartTime + TIME_LIMIT;
    g_MoveTimer.dHardTimeLimit = g_MoveTimer.dStartTime + TIME_LIMIT;
}

FLAG
TestSearch(void)
{
    SEARCHER_THREAD_CONTEXT *ctx;
    POSITION pos;
    ULONG u;
    GAME_RESULT result;
    FLAG fPost = g_Options.fShouldPost;
    FLAG fRet = FALSE;

    ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT));
    ASSERT(ctx);
    g_Options.fShouldPost = FALSE;
    Trace("Testing Search routine...\n");
    for (u = 0; u < 20; u++)
    {
        GenerateRandomLegalPosition(&pos);
        // Log the exact FEN before searching it -- a crash partway
        // through this loop otherwise gives no way to reproduce which
        // of the 20 random positions triggered it (this cost real
        // debugging time chasing an intermittent failure whose
        // position was never captured -- see board_representation/
        // MOVEGEN_MIGRATION.md section 6b).
        {
            char *pszFen = PositionToFen(&pos);
            Trace("TestSearch position %lu/20: %s\n", u + 1,
                  pszFen ? pszFen : "(PositionToFen failed)");
        }
        InitializeSearcherContext(&pos, ctx);

        g_MoveTimer.bvFlags = 0;
        g_Options.fPondering = FALSE;
        g_Options.fThinking = TRUE;
        g_Options.fSuccessfulPonder = FALSE;
        
        MaintainDynamicMoveOrdering();
        DirtyHashTable();
        
        //
        // TODO: Any preEval?
        //
        
        //
        // Set a very long time limit on the search
        //
        SetMoveTimerForTestingSearch();
        g_Options.uMaxDepth = 2;
        
        //
        // TODO: Set draw value
        //
#if (PERF_COUNTERS && MP)
        ClearHelperThreadIdleness();
#endif
        result = Iterate(ctx);

        //
        // How long did that take?
        //
        if (SystemTimeStamp() - g_MoveTimer.dStartTime > TIME_LIMIT)
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, "TestSearch", NULL, NULL,
                      __FILE__, __LINE__);
        }

        //
        // Did we get a sane move?
        //
        if (RESULT_IN_PROGRESS == result.eResult)
        {
            if (FALSE == SanityCheckMove(&pos, ctx->mvRootMove))
            {
                UtilPanic(TESTCASE_FAILURE,
                          NULL, "TestSearch", NULL, NULL,
                          __FILE__, __LINE__);
            }
        }
#ifdef DEBUG
        else if (RESULT_WHITE_WON == result.eResult)
        {
            ASSERT(InCheck(&pos, BLACK));
        }
        else if (RESULT_BLACK_WON == result.eResult)
        {
            ASSERT(InCheck(&pos, WHITE));
        }
#endif
    }
    fRet = TRUE;

    g_Options.fShouldPost = fPost;
    SystemFreeMemory(ctx);
    return(fRet);
}


//
// Shared setup for the hash-consistency and zugzwang tests below: run
// one fixed-depth search on a fresh SEARCHER_THREAD_CONTEXT-relative
// position (ctx is caller-owned and reused across calls, matching
// TestSearch's own pattern -- SystemAllocateMemory'ing a fresh 75MB
// context per call would be wasteful for tests that need many runs
// over the same handful of positions) and return the root score.
// Does NOT touch the hash table itself (no Clear/Dirty call) -- that
// decision is the caller's, since the whole point of the hash tests
// below is controlling exactly what's in the table before each call.
//
// 2026-10-04: calls ClearDynamicMoveOrdering(), not
// MaintainDynamicMoveOrdering() (the real game-play decay-only
// maintenance call, still used as-is at its other call sites in
// root.c/util.c). InitializeSearcherContext clears ctx-local state
// (killers, countermove table) but g_HistoryCounters/
// g_ContinuationHistory/g_FailHighs are process-global and persist
// across calls to this function otherwise -- decaying them (what
// MaintainDynamicMoveOrdering does) still leaves real accumulated
// evidence behind. Search is not a pure function of (position, depth)
// in the presence of that evidence: a move's own GetMoveFailHighPct
// Thousandths reading (feeding GetLMRReduction/ShouldLatePrune/EFP)
// depends on it, and it accumulates LIVE during a search as sibling/
// cousin nodes are visited -- so two calls that visit nodes in a
// different order (which a warm vs. cold hash table, by design, makes
// them do) can legitimately reduce/prune the same move differently,
// producing a different score with no bug involved anywhere. A full
// clear here is what actually isolates "did the hash table change the
// answer" (what TestSearchHashConsistency, below, means to test) from
// "did ordinary order-dependent move-ordering heuristics change the
// answer" (expected, unrelated to hash-table correctness, and true of
// this engine with or without LMR).
static SCORE
_FixedDepthSearchScore(SEARCHER_THREAD_CONTEXT *ctx,
                       POSITION *pos,
                       ULONG uMaxDepth)
{
    GAME_RESULT result;
    FLAG fPost = g_Options.fShouldPost;

    g_Options.fShouldPost = FALSE;
    InitializeSearcherContext(pos, ctx);
    g_MoveTimer.bvFlags = 0;
    g_Options.fPondering = FALSE;
    g_Options.fThinking = TRUE;
    g_Options.fSuccessfulPonder = FALSE;
    ClearDynamicMoveOrdering();
    SetMoveTimerForTestingSearch();
    g_Options.uMaxDepth = uMaxDepth;
#if (PERF_COUNTERS && MP)
    ClearHelperThreadIdleness();
#endif
    result = Iterate(ctx);
    g_Options.fShouldPost = fPost;
    if (RESULT_IN_PROGRESS != result.eResult)
    {
        // Mate/stalemate/draw at the root -- no root score was set by
        // this iteration (there's no move to score). Not a bug, just
        // not a comparable data point for the callers below.
        return(INVALID_SCORE);
    }
    return(ctx->iRootScore);
}


//
// Hash-table correctness, exercised through real search rather than
// synthetic store/probe calls -- the actual bug class this is meant
// to catch (stale entries surviving a generation boundary, a bound
// getting misapplied, ADJUST_MATE_IN_N misfiring on an entry that
// shouldn't get it) only shows up when a search's outcome actually
// depends on what it reads back out of the table, which a
// hand-constructed store()-then-probe() unit test can't exercise --
// see TESTING_PLAN.md's "hash correctness" section for the case for a
// synthetic store/probe test too; this is the complementary
// behavioral half, not a replacement for it.
//
// Two invariants, intended to care only about the hash table being
// *transparent* (its presence changes performance, never the answer),
// not about search internals (move ordering, PV, node count) changing
// across future search work -- but see invariant 2's own note below,
// 2026-10-04: that intent does not actually hold for invariant 2 once
// any move-order-sensitive heuristic (this engine has several; LMR is
// the one that exposed it) is in the search, so it is diagnostic-only
// now, not asserted.
//
//   1. Searching the same position to the same depth twice in a row
//      (second time with the table already populated by the first)
//      must produce the same score both times. Still asserted: the
//      second run's hash move at every node is the SAME move the
//      first run itself discovered as best there (same position, same
//      depth), so warming the table cannot promote a DIFFERENT move
//      to be tried first and thereby shift anything's ordinal
//      position -- there is no move-order-sensitivity window for this
//      invariant the way there is for invariant 2.
//   2. Searching to depth D2 with the table pre-populated by a
//      shallower depth-D1 search of the same position was meant to
//      produce the same score as searching directly to D2 from a
//      freshly cleared table -- catching a depth-D1 entry wrongly
//      trusted as exact at the deeper D2 probe. Downgraded to
//      diagnostic-only (logged, not asserted) 2026-10-04: proven (via
//      bisection against DISABLE_LMR, with g_HistoryCounters/
//      g_ContinuationHistory/g_FailHighs already fully cleared between
//      every search below -- see _FixedDepthSearchScore's own comment)
//      to fail even on the symmetric starting position, for a reason
//      that has nothing to do with any hash-table bug: the shallower
//      warm-up leaves a DIFFERENT move in the table as this node's
//      hash move than a cold search would pick on its own, which
//      promotes a different move to be tried first, which shifts
//      every OTHER move's ordinal position by one -- and LMR's own
//      "lateness" admission signal (MoveNumBucket(uLegalMoves),
//      feeding the joint table's uPredictedFH) depends on exactly that
//      ordinal position. Two equally-legitimate searches of the same
//      nominal depth can therefore reduce a given move in one and not
//      the other, with zero dependence on any learned/dynamic table --
//      this is a property of combining a hash table with ANY
//      move-order-sensitive pruning/reduction heuristic, not a defect
//      in this one. The genuine bug class this invariant was meant to
//      catch (a shallow bound trusted as exact at a deeper probe) is
//      real and still worth watching for by eye in the log; it is just
//      no longer something this test can assert without false
//      positives from ordinary LMR behavior.
//
FLAG
TestSearchHashConsistency(void)
{
    static const char *rgszFen[] =
    {
        "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",
        "8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1",
    };
    const ULONG uD1 = 4;
    const ULONG uD2 = 6;
    SEARCHER_THREAD_CONTEXT *ctx;
    POSITION pos;
    SCORE iFirst, iSecond, iShallow, iDirect;
    ULONG u;
    FLAG fRet = TRUE;

    Trace("Testing hash table consistency through search...\n");
    ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT));
    ASSERT(ctx);

    for (u = 0; u < ARRAY_LENGTH(rgszFen); u++)
    {
        if (FALSE == FenToPosition(&pos, (char *)rgszFen[u]))
        {
            UtilPanic(INCONSISTENT_STATE,
                      NULL, NULL, NULL, NULL,
                      __FILE__, __LINE__);
        }

        // Invariant 1: repeat-with-warm-table stability.
        ClearHashTable();
        DirtyHashTable();
        iFirst = _FixedDepthSearchScore(ctx, &pos, uD1);
        DirtyHashTable();
        iSecond = _FixedDepthSearchScore(ctx, &pos, uD1);
        if ((INVALID_SCORE != iFirst) &&
            (INVALID_SCORE != iSecond) &&
            (iFirst != iSecond))
        {
            Trace("TestSearchHashConsistency: position %lu: same-depth "
                  "rerun with warm hash table diverged (%d vs %d) -- "
                  "FEN: %s\n", u, iFirst, iSecond, rgszFen[u]);
            fRet = FALSE;
        }

        // Invariant 2: diagnostic-only now -- see this function's
        // top-of-file comment for why a mismatch here is expected
        // (LMR's move-order-sensitive lateness signal) and does not
        // indicate a hash-table bug. Logged so a wildly outlying case
        // still catches a human's eye, but never fails the suite.
        ClearHashTable();
        DirtyHashTable();
        iShallow = _FixedDepthSearchScore(ctx, &pos, uD1);
        DirtyHashTable();
        iSecond = _FixedDepthSearchScore(ctx, &pos, uD2);

        ClearHashTable();
        DirtyHashTable();
        iDirect = _FixedDepthSearchScore(ctx, &pos, uD2);

        if ((INVALID_SCORE != iSecond) &&
            (INVALID_SCORE != iDirect) &&
            (iSecond != iDirect))
        {
            Trace("TestSearchHashConsistency: position %lu: depth-%lu "
                  "search seeded by a depth-%lu warm-up (%d) disagreed "
                  "with a from-scratch depth-%lu search (%d) -- FEN: "
                  "%s (diagnostic only, not a failure -- see top-of-"
                  "file comment)\n", u, uD2, uD1, iSecond, uD2, iDirect,
                  rgszFen[u]);
        }
        (void)iShallow;
    }

    if (FALSE == fRet)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "TestSearchHashConsistency", NULL, NULL,
                  __FILE__, __LINE__);
    }
    ClearHashTable();
    SystemFreeMemory(ctx);
    return(fRet);
}


// Null-move soundness is intentionally NOT tested here as a C unit
// test. An earlier version of this file asserted against
// ctx->sCounters.extension.uZugzwang (searchsup.c's verification-
// search counter) using the three classic "verified null-move
// pruning" zugzwang positions -- but on this codebase's own material
// gates (WeShouldTryNullmovePruning's `> 2` non-pawn-count guard,
// TryNullmovePruning's `< 4` verification window) and this box's
// Syzygy coverage, none of the three ever actually reached the
// mechanism: two have too little material for null-move pruning to
// be attempted at all, and the third gets resolved directly off the
// local tablebase before search ever touches null-move logic. That
// made the internal-counter approach fragile and environment-
// dependent in a way a real best-move suite isn't. See
// tests/zugzwang.epd (run with the `epd` command, e.g. `epd
// tests/zugzwang.epd`) instead -- five known zugzwang positions
// checked by best-move outcome, which doesn't care why the engine
// gets it right, just whether it does.
//

//
// QSearch is meant to stay small and shallow (search.c's own
// ASSERT(pf->uQsearchNodes < 20000) at its only call site is a
// no-op in a release build -- this makes a version of that bound a
// real, always-checked test instead of a DEBUG-only assertion).
//
// Note this checks ctx->sCounters.tree.u64TotalNodeCount (whole
// search, root.c's own unconditional per-node ++), not
// u64QNodeCount specifically -- that counter, and every other field
// in sCounters, is wrapped in the INC() macro (chess.h), which
// compiles to nothing unless PERF_COUNTERS is defined, and this
// self-test suite is built with plain `gmake TEST=1` (see CLAUDE.md),
// which doesn't define it (confirmed live: a real `sd 3; go` on this
// TEST-only binary reports "0 qnodes" no matter how much qsearch
// activity actually happened). A whole-search bound is a strictly
// weaker signal than a qsearch-only one -- it wouldn't distinguish
// "qsearch exploded" from "full-width search exploded" -- but it's
// the honest thing this build can actually check; rebuilding with
// PERF_COUNTERS added would be needed to test u64QNodeCount for real.
//
// "Small" is also exactly what makes qsearch trees hand-auditable in
// principle: a person could Trace() every node visited on one of the
// positions below and read the resulting tree start to finish against
// the board, unlike a full alpha-beta tree at real search depth. No
// such tracing is wired up here (that would need a new instrumented
// build define, not written this session) -- noting it as a
// worthwhile follow-up, not implying it already exists.
//
FLAG
TestQSearchSanity(void)
{
    static const char *rgszFen[] =
    {
        // Quiet position -- qsearch should do almost nothing (stand
        // pat immediately, no captures available).
        "4k3/8/8/8/8/8/8/4K3 w - - 0 1",
        // A short, bounded capture sequence on one square.
        "4k3/8/8/3p4/2P5/8/8/4K3 w - - 0 1",
        // A deeper capturing melee -- the kind of position qsearch
        // exists for.
        "r1bq1rk1/pp2bppp/2n1pn2/2pp4/3P4/2NBPN2/PP3PPP/R1BQ1RK1 w - - 0 1",
        "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",
    };
    const ULONG uDepth = 3;
    SEARCHER_THREAD_CONTEXT *ctx;
    POSITION pos;
    SCORE iScore;
    ULONG u;
    FLAG fRet = TRUE;

    Trace("Testing QSearch sanity (node-count bound, termination)...\n");
    ctx = SystemAllocateMemory(sizeof(SEARCHER_THREAD_CONTEXT));
    ASSERT(ctx);

    for (u = 0; u < ARRAY_LENGTH(rgszFen); u++)
    {
        if (FALSE == FenToPosition(&pos, (char *)rgszFen[u]))
        {
            UtilPanic(INCONSISTENT_STATE,
                      NULL, NULL, NULL, NULL,
                      __FILE__, __LINE__);
        }
        // uMaxDepth == 3 plies -- enough that the last full-width ply
        // (uDepth == 0 in Search()'s ONE_PLY units) actually falls
        // below Search()'s THREE_QUARTERS_PLY qsearch-entry threshold
        // and real qsearch nodes get visited (measured live: depth 1
        // resolved every position here without qsearch ever firing --
        // g_uQNodeCount stayed 0 -- since a two-king or short-capture
        // position this shallow settles via CommonSearchInit's own
        // early-outs before the qsearch dispatch is ever reached).
        // Still small enough to trace by hand per this function's own
        // header comment.
        ClearHashTable();
        DirtyHashTable();
        iScore = _FixedDepthSearchScore(ctx, &pos, uDepth);

        if ((INVALID_SCORE != iScore) &&
            !IS_VALID_SCORE(iScore))
        {
            Trace("TestQSearchSanity: position %lu returned an "
                  "invalid score %d -- FEN: %s\n", u, iScore,
                  rgszFen[u]);
            fRet = FALSE;
        }
        Trace("TestQSearchSanity: position %lu total nodes this "
              "search: %llu\n", u,
              ctx->sCounters.tree.u64TotalNodeCount);

        // Not the same invariant as search.c's per-entry
        // ASSERT(pf->uQsearchNodes < 20000) (that resets per qsearch
        // entry point and counts qsearch nodes only; this is a
        // whole-search cumulative total, per this function's header
        // comment on why), but a real, always-checked (not DEBUG-only)
        // ceiling on "a shallow fixed-depth search on a small position
        // stays small" -- a qsearch that's stopped terminating cleanly
        // (e.g. a check-extension/repetition interaction letting
        // QPLIES_OF_NON_CAPTURE_CHECKS get bypassed) will blow through
        // this by orders of magnitude, not marginally, regardless of
        // it being mixed in with full-width nodes here.
        if (ctx->sCounters.tree.u64TotalNodeCount > 500000)
        {
            Trace("TestQSearchSanity: position %lu total node count "
                  "%llu is wildly outside the expected 'small' range "
                  "for depth %lu -- FEN: %s\n", u,
                  ctx->sCounters.tree.u64TotalNodeCount, uDepth,
                  rgszFen[u]);
            fRet = FALSE;
        }
    }

    if (FALSE == fRet)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "TestQSearchSanity", NULL, NULL,
                  __FILE__, __LINE__);
    }
    ClearHashTable();
    SystemFreeMemory(ctx);
    return(fRet);
}
#endif