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


// 2026-10-08: TestSearchHashConsistency (both its "invariants") was
// removed. Its entire premise -- that a hash table should be provably
// *transparent* (changes performance, never the answer) and that this
// is checkable by comparing scores across searches that visit
// different subsets of the tree -- does not hold in this engine and
// cannot be patched into holding. LMP/LMR pruning decisions depend on
// GLOBAL, LIVE-ACCUMULATING evidence tables (g_HistoryCounters,
// g_ContinuationHistory, g_FailHighs) that update as a side effect of
// actually VISITING a node, not as a side effect of that node's final
// score. A hash cutoff resolves a subtree with a perfectly sound bound
// but without visiting it -- so two searches that visit different
// subsets of the same tree (which is the entire point of a hash table:
// a cold run visits everything, a warm run skips subtrees a previous
// identical run already resolved) can legitimately reach a later
// sibling move with different accumulated evidence, prune/reduce it
// differently, and return a different final score -- with zero
// hash-table bug anywhere. This was already known and documented for
// "invariant 2" (depth-D1-warmup vs depth-D2-direct, downgraded to
// diagnostic-only 2026-10-04); what was missed is that the identical
// mechanism applies just as much to "invariant 1" (same-depth
// back-to-back rerun), which was still asserted and panicking the
// self-test suite on nothing but this structural, expected effect. A
// real hash-table correctness test needs a synthetic store/probe unit
// test (see TESTING_PLAN.md's "hash correctness" section) that can
// control exactly what the table returns, not a real search compared
// against another real search -- any two of which are free to visit
// different nodes by design.


// 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