path: root/src/search.c

/**

Copyright (c) Scott Gasch

Module Name:

    search.c

Abstract:

    Recursive chess tree searching.  See also split.c.

    "A type 1 node is also called a PV node.  The root of the tree is
    a type-1 node, and the *first* successor of a type-1 node is a
    type-1 node also.  A type-1 node must have all branches examined,
    but it is unique in that we don't know anything about alpha and
    beta yet, because we haven't searched the first move to establish
    them.

    A type 2 node is either (a) a successor of any type-3 node, or,
    (b) it's any successor (other than the first) of a type-1 node.
    With perfect move ordering, the first branch at a type-2 node will
    "refute" the move made at the previous ply via the alpha/beta
    algorithm.  This node requires good move ordering, because you
    have to find a move good enough that your opponent would not play
    the move he chose that led to this position.  If you try a poor
    move first, it won't produce a cutoff, and you have to search
    another move (or more) until you find the "good" move that would
    make him not play his move.

    A type-3 node follows a type-2 node.  Here, you have to try every
    move at your disposal.  Since your opponent (at the previous ply)
    has played a "strong" move (supposedly the "best" move) you are
    going to have to try every move you have in an effort to refute
    this move.  None will do so (unless your opponent tried some poor
    move first due to incorrect move ordering).  Here, move ordering
    is not worth the trouble, since the ordering won't let you avoid
    searching some moves.  Of course, with the transposition /
    refutation table, ordering might help you get more "hits" if your
    table is not large enough...

    As you can see, at type-1 nodes you have to do good move ordering
    to choose that "1" move (or to choose that one out of a very few)
    that is good enough to cause a cutoff, while avoiding choosing
    those that are no good.  At a type-1 node, the same thing applies.
    If you don't pick the best move first (take the moves at the root
    for example) you will search an inferior move, establish alpha or
    beta incorrectly, and thereby increase the size of the total tree
    by a *substantial* amount.

    By the way, some authors call type-1 nodes "PV" nodes, type-2
    nodes "CUT" nodes, and type-3 nodes "ALL" nodes.  These make it
    easier to read, but, unfortunately, I "cut my teeth" on the
    Knuth/Moore paper and think in terms of type 1,2,3."

                                                 --Bob Hyatt, r.g.c.c

Author:

    Scott Gasch ([email protected]) 21 May 2004

Revision History:

    $Id: search.c 345 2007-12-02 22:56:42Z scott $

**/

#include "chess.h"

extern ULONG g_uIterateDepth;
extern FLAG g_fCanSplit[MAX_PLY_PER_SEARCH];

#define TRY_HASH_MOVE         (0)
#define GENERATE_MOVES        (1)
#define PREPARE_TO_TRY_MOVES  (2)
#define TRY_GENERATED_MOVES   (3)

// EFP's fail-high-history exemption: below EFP_FH_MIN_SAMPLES
// observations, GetMoveFailHighPercentage's result isn't trusted
// enough to override the static-eval-based decision either way.
#define EFP_FH_MIN_SAMPLES     (5)
#define EFP_FH_PRUNE_THRESHOLD (10)

// EXPERIMENT: is history+continuation evidence predictive of a
// countermove match's own FH%? See chess.h's CM_EVIDENCE_BUCKETS
// comment. Buckets by log-ish bands rather than linear, since evidence
// values span 0 to ~STRIP_OFF_FLAGS*2 (~16.7M).
#ifdef PERF_COUNTERS
static ULONG
_CMEvidenceBucket(ULONG uEvidence)
{
    static const ULONG uFloors[CM_EVIDENCE_BUCKETS] =
        { 0, 1, 100, 1000, 10000, 100000, 1000000 };
    ULONG i;

    for (i = CM_EVIDENCE_BUCKETS; i > 0; i--)
    {
        if (uEvidence >= uFloors[i - 1])
        {
            return(i - 1);
        }
    }
    return(0);
}
#endif

#ifdef DEBUG
#define VERIFY_HASH_HIT                                \
    ASSERT(IS_VALID_SCORE(iScore));                    \
    ASSERT(((ULONG)pHash->uDepth << 4) >= uDepth);     \
    switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)   \
    {                                                  \
        case HASH_FLAG_LOWER:                          \
            ASSERT(iScore >= iBeta);                   \
            ASSERT(iScore > -NMATE);                   \
            ASSERT(iScore <= +NMATE);                  \
            break;                                     \
        case HASH_FLAG_UPPER:                          \
            ASSERT(iScore <= iAlpha);                  \
            ASSERT(iScore < +NMATE);                   \
            ASSERT(iScore >= -NMATE);                  \
            break;                                     \
        case HASH_FLAG_EXACT:                          \
            ASSERT((-NMATE <= iScore) &&               \
                   (iScore <= +NMATE));                \
            break;                                     \
        default:                                       \
            ASSERT(FALSE);                             \
    }
#else
#define VERIFY_HASH_HIT
#endif

/**

Routine description:

    This is the full-width portion of the main chess tree search.  In
    general, its job is to ask the move generator to make a list of
    all the moves possible at the board position in ctx, to make each
    move in turn, and to search each resulting position recursively.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx : the context to search in
    SCORE iAlpha : the lower bound of the interesting score window
    SCORE iBeta : the upper bound of the interesting score window
    ULONG uDepth : the depth remaining before QSearch is invoked

Return value:

    SCORE : a score

    Also affects the transposition table, searcher context, and just
    about every other large data structure in the engine...

**/
SCORE FASTCALL
Search(IN SEARCHER_THREAD_CONTEXT *ctx,
       IN SCORE iAlpha,
       IN SCORE iBeta,
       IN ULONG uDepth)
{
    POSITION *pos = &ctx->sPosition;
    PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
    CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
    MOVE mvLast = (pi-1)->mv;
    SCORE iBestScore = -INFINITY;
    SCORE iInitialAlpha;
    SCORE iEval;
    MOVE mv, mvBest, mvHash;
    ULONG x = 0;
    SCORE iScore;
    INT iOrigExtend = 0;
    INT iExtend;
    ULONG uNextDepth;
    ULONG uLegalMoves = 0;
    FLAG fIsLeftoverMove = FALSE;
#ifdef PERF_COUNTERS
    FLAG fThisMoveIsCountermoveMatch = FALSE;
    ULONG uCMEvidenceBucket = 0;
#endif
    HASH_ENTRY *pHash;
    FLAG fThreat;
    FLAG fSkipNull;
    FLAG fIsDraw;
    ULONG uStage = TRY_HASH_MOVE;
    ULONG u;
    ULONG uFutilityMargin = 0;
    FLAG fAnyMoveEFPPruned = FALSE;
    FLAG fThisMoveEFPPruned = FALSE;
    SCORE iCheckSee;
#ifdef DEBUG
    ASSERT(IS_VALID_SCORE(iAlpha));
    ASSERT(IS_VALID_SCORE(iBeta));
    ASSERT(iAlpha < iBeta);
    ASSERT(ctx->uPly > 0);
    ASSERT((mvLast.uMove != 0) || (pf->fAvoidNullmove == TRUE));
    ASSERT(IS_VALID_FLAG(pf->fAvoidNullmove));
    ASSERT(IS_VALID_FLAG(pf->fVerifyNullmove));
    memcpy(&pi->sPosition, pos, sizeof(POSITION));
#endif
    mvBest.uMove = 0;

    // Jump directly to Qsearch if remaining depth is low enough.
    // This is the only place Qsearch is entered.  Lowered from ONE_PLY to
    // THREE_QUARTERS_PLY to match the check extension's new flat amount
    // (searchsup.c's ComputeMoveExtension) -- a lone check (or short run
    // of them) still buys exactly one extra full-width ply as before, but
    // a long unbroken chain now pays QUARTER_PLY of real cost per check
    // instead of extending for free.  root.c compensates by trimming the
    // same QUARTER_PLY off the per-iteration depth budget so this doesn't
    // just add a blanket 1/4 ply to every search.
    if (uDepth < THREE_QUARTERS_PLY)
    {
        pf->fCouldStandPat[BLACK] = pf->fCouldStandPat[WHITE] = FALSE;
        pf->uQsearchNodes = pf->uQsearchDepth = 0;
        pf->uQsearchCheckDepth = QPLIES_OF_NON_CAPTURE_CHECKS;
        pi->fInQsearch = TRUE;
        iBestScore = QSearch(ctx, iAlpha, iBeta);
        ASSERT(pf->uQsearchNodes < 20000);
        ASSERT(pf->uQsearchDepth == 0);
        goto end;
    }
    pi->fInQsearch = FALSE;

    // Common initialization code (which may cause a cutoff or change the
    // bounds or decide that we need to stop searching now).
    if (TRUE == CommonSearchInit(ctx,
                                 &iAlpha,
                                 &iBeta,
                                 &iBestScore))
    {
        goto end;
    }
    DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta);
    iInitialAlpha = iAlpha;
    pi->fPvNode = (iBeta != iAlpha + 1);
    pi->fMovesRescoredByIID = FALSE;
    ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) ||
           (!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck)));

    // Prepare next depth for nullmove and hashtable lookup
    uNextDepth = uDepth - SelectNullmoveRFactor(ctx, uDepth) - ONE_PLY;
    if (uNextDepth > MAX_DEPTH_PER_SEARCH) uNextDepth = 0;

    // Check the transposition table.  This may give us a cutoff
    // without doing any work if we have previously stored the score
    // of this search in the hash.  It also may set mvHash even if it
    // can't give us a cutoff.  It also may set fSkipNull (see below)
    // based on uNextDepth to inform us that a nullmove search is
    // unlikely to succeed here.
    mvHash.uMove = 0;
    pHash = HashLookup(ctx,
                       uDepth,
                       uNextDepth,
                       iAlpha,
                       iBeta,
                       &fThreat,
                       &fSkipNull,
                       &mvHash,
                       &iScore);
    if (NULL != pHash)
    {
        VERIFY_HASH_HIT;
        u = pHash->bvFlags & HASH_FLAG_VALID_BOUNDS;
        if (0 != mvHash.uMove)
        {
            // This is an idea posted by Dieter Brusser on CCC:  If we
            // get a hash hit that leads to a draw then only accept it
            // if it has a score of zero, allows us to fail high when
            // a draw would also have allowed a fail high, or allows a
            // fail low when a draw would also have allowed a fail
            // low.
            VERIFY(MakeMove(ctx, mvHash));
            fIsDraw = IsDraw(ctx);
            UnmakeMove(ctx, mvHash);
            if ((FALSE == fIsDraw) || (iScore == g_iDrawScore[pos->uToMove]) ||
               ((u == HASH_FLAG_LOWER) && (iScore >= iBeta) && (g_iDrawScore[pos->uToMove] >= iBeta)) ||
               ((u == HASH_FLAG_UPPER) && (iScore <= iAlpha) && (g_iDrawScore[pos->uToMove] <= iAlpha)))
            {
                // If the hash move leads to a draw, the score actually
                // produced by playing it is g_iDrawScore[pos->uToMove]
                // (from the mover's point of view), not the stale iScore
                // recorded along whatever non-repeating path originally
                // stored this entry -- the checks above only established
                // that the draw score clears the same bound iScore does,
                // not that iScore itself is an accurate value to return.
                SCORE iRetScore = fIsDraw ? g_iDrawScore[pos->uToMove] : iScore;
                if ((iAlpha < iRetScore) && (iRetScore < iBeta))
                {
                    UpdatePV(ctx, HASHMOVE);
                }
                iBestScore = iRetScore;
                goto end;
            }
        }
        else
        {
            // The hash move is empty.  Either this is an upper bound
            // in which case we have no best move since the node that
            // generated it was a fail low -or- this is a lower bound
            // recorded after a null move search.  In the latter case
            // we only accept the cutoff if we are considering null
            // moves at this node too.
            ASSERT(u != HASH_FLAG_EXACT);
            if ((HASH_FLAG_UPPER == u) || (FALSE == pf->fAvoidNullmove))
            {
                ASSERT(((u == HASH_FLAG_UPPER) && (iScore <= iAlpha)) ||
                       ((u == HASH_FLAG_LOWER) && (iScore >= iBeta)));
                iBestScore = iScore;
                goto end;
            }
        }
    }

    // Probe interior node recognizers; allow probes of ondisk EGTB files
    // if it looks like we can get hit.
    switch(RecognLookup(ctx, &iScore, ctx->uPly <= (g_uIterateDepth / 2)))
    {
        case UNRECOGNIZED:
            break;
        case RECOGN_EXACT:
        case RECOGN_EGTB:
            if ((iAlpha < iScore) && (iScore < iBeta))
            {
                UpdatePV(ctx, RECOGNMOVE);
            }
            iBestScore = iScore;
            goto end;
        case RECOGN_LOWER:
            if (iScore >= iBeta)
            {
                iBestScore = iScore;
                goto end;
            }
            break;
        case RECOGN_UPPER:
            if (iScore <= iAlpha)
            {
                iBestScore = iScore;
                goto end;
            }
            break;
#ifdef DEBUG
        default:
            ASSERT(FALSE);
#endif
    }

    // Maybe do nullmove pruning
    pi->iEval = iEval = GetRoughEvalScore(ctx, iAlpha, iBeta, FALSE);
    SCORE iImprovement = 0;
    if (ctx->uPly > 1)
    {
        iImprovement = (iEval - ctx->sPlyInfo[ctx->uPly - 2].iEval);
    }


    GENERATE_NO_MOVES;
    if (!fSkipNull &&
        !fThreat &&
        WeShouldTryNullmovePruning(ctx,
                                   iAlpha,
                                   iBeta,
                                   iEval,
                                   iImprovement,
                                   uNextDepth))
    {
        if (TryNullmovePruning(ctx,
                               &fThreat,
                               iAlpha,
                               iBeta,
                               uNextDepth,
                               &iOrigExtend,
                               &iScore))
        {
            if (iScore > iBeta) {
                StoreLowerBound(mvHash, pos, iScore, uDepth, FALSE);
            }
            iBestScore = iScore;
            goto end;
        }
    }

    // Maybe increment positional extension level b/c of nullmove search
    // or hash table results.
    if (fThreat)
    {
        iOrigExtend += THREE_QUARTERS_PLY;
        INC(ctx->sCounters.extension.uMateThreat);
    }

    // Main search loop, try moves under this position.  Before we get
    // into the move loop, save the extensions merited by this
    // position in the tree (pre-move) and the original search flags.
    // Also clear the avoid null bit in the search flags -- we were
    // either told to avoid it or not but there is no need to avoid it
    // for the rest of the line...
    pf->fAvoidNullmove = FALSE;
    do
    {
        ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));

        // Becase we want to try the hash move before generating any
        // moves (in case it fails high and we can avoid the work) we
        // have this ugly crazy looking switch statement...
        switch(uStage)
        {
            case TRY_HASH_MOVE:
                uStage++;
                x = 0;
                ASSERT(iBestScore == -INFINITY);
                ASSERT(uLegalMoves == 0);
                if (mvHash.uMove != 0)
                {
                    mv = mvHash;
                    break;
                }
                // else fall through

            case GENERATE_MOVES:
                ASSERT(ctx->uPly > 0);
                ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
                x = ctx->sMoveStack.uBegin[ctx->uPly];
                uStage++;
                if (IS_CHECKING_MOVE(mvLast))
                {
                    ASSERT(InCheck(pos, pos->uToMove));
                    GenerateMoves(ctx, mvHash, GENERATE_ESCAPES);
                    if (MOVE_COUNT(ctx, ctx->uPly))
                    {
                        if (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1)
                        {
                            iOrigExtend += QUARTER_PLY;
                            INC(ctx->sCounters.extension.uMultiCheck);
                        } else if (NUM_KING_MOVES(ctx, ctx->uPly) == 0) {
                            iOrigExtend += QUARTER_PLY;
                            INC(ctx->sCounters.extension.uNoLegalKingMoves);
                        }
                    }
                }
                else
                {
                    ASSERT(!InCheck(pos, pos->uToMove));
                    GenerateMoves(ctx, mvHash, GENERATE_ALL_MOVES);
                }

                // The threat/multi-check/no-legal-king-move bonuses above
                // are independent and can stack past ONE_PLY; clamp the
                // combined per-position extension to what the rest of the
                // code (e.g. split.c's HelpSearch) assumes is the max for
                // a single node.
                iOrigExtend = MIN(iOrigExtend, ONE_PLY);
                // fall through

            case PREPARE_TO_TRY_MOVES:
                ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]);
                ASSERT((uLegalMoves == 0) ||
                       ((uLegalMoves == 1) && (mvHash.uMove)));
#ifdef DO_IID
                if (MOVE_COUNT(ctx, ctx->uPly))
                {
                    SelectBestNoHistory(ctx, x);

                    // EXPERIMENT: If we got no best move from the
                    // hash table and the best move we got from the
                    // generator looks crappy (i.e. is not a winning
                    // or even capture/promotion, AND not a killer --
                    // a killer move already proved itself elsewhere in
                    // the tree, unlike an untested quiet move, so it
                    // doesn't need IID's help) then rescore the moves
                    // we generated at this ply using a shallower
                    // search.  "Internal Iterative Deepening" or
                    // something like it.
                    if ((TRUE == pi->fPvNode) &&
                        (mvHash.uMove == 0) &&
                        (ctx->sMoveStack.mvf[x].iValue < SORT_THESE_FIRST) &&
                        (0 == (ctx->sMoveStack.mvf[x].iValue &
                               (FIRST_KILLER | SECOND_KILLER |
                                THIRD_KILLER | FOURTH_KILLER))) &&
                        (uDepth >= FOUR_PLY))
                    {
                        ASSERT(uDepth >= (IID_R_FACTOR + ONE_PLY));
                        ASSERT(ctx->sSearchFlags.fAvoidNullmove == FALSE);
                        ctx->sSearchFlags.fAvoidNullmove = TRUE;
                        RescoreMovesViaSearch(ctx, uDepth, iAlpha, iBeta);
                        ctx->sSearchFlags.fAvoidNullmove = FALSE;
                        // NOT always TRUE here -- pre-existing bug, found
                        // via debug_smoke_test.sh (a deeper/larger-than-
                        // usual sample finally hit the rare path).
                        // RescoreMovesViaSearch's own fail-high branch
                        // (searchsup.c) deliberately leaves this FALSE by
                        // design -- a fail-high only proves uBest is good
                        // enough, not honest eval-axis scores for every
                        // move, so claiming fMovesRescoredByIID would be a
                        // lie. This assert demanded the opposite of that
                        // documented contract; DO_IID is unconditionally
                        // compiled in (chess.h) so this could fire on any
                        // DEBUG build given an unlucky enough rescore --
                        // ASSERT is a no-op in release, so this never
                        // crashed in production, but it made the DEBUG/
                        // TEST harness itself unreliable at random.
                    }
                }
#endif
                // Ernst Heinz's forward-pruning-by-material-margin idea,
                // rewritten to match his book's actual two-tier
                // schedule (this previously used a single flat
                // VALUE_ROOK margin across the whole uDepth <= TWO_PLY
                // range, which is neither of the two numbers Heinz
                // actually gives for that range): "selective futility"
                // at the frontier (VALUE_KNIGHT, his 200-400
                // pawn-equivalent range) and "extended futility
                // pruning" proper one ply further back (VALUE_ROOK, his
                // 500-600 range). Common conditions (PV-node guard,
                // ply floor, no per-position extension here or two
                // plies back) are the same for both tiers, so they're
                // checked once; only the depth band and margin differ
                // per tier. Deliberately drops the old
                // ValueOfMaterialInTroubleDespiteMove requirement (an
                // en-prise/trapped-piece safety net) -- this is meant
                // to fire on ordinary quiet positions too, not just
                // ones where a piece is already known to be in danger.
                //
                // Tier boundaries are relative to THREE_QUARTERS_PLY
                // (the actual QSearch cutoff just below, not ONE_PLY --
                // lowered when the check-extension rework made a lone
                // check buy exactly one extra full-width ply rather
                // than a blanket extra 1/4 ply): "one ply above the
                // QSearch jump" is (THREE_QUARTERS_PLY, ONE_PLY +
                // THREE_QUARTERS_PLY], "two plies above" is the next
                // such band.
                //
                // "Limited razoring" (Heinz's third tier, pre-pre-
                // frontier, VALUE_QUEEN, ~900-1000) is a different
                // technique -- a per-node depth reduction, not a
                // per-move prune -- and is deliberately not implemented
                // here; see lmr_testing/RESULTS.md.
                //
                // PV-node guard: HEAD's original condition had none
                // (unlike GetLMRReduction, which has always required
                // FALSE == fPvNode) -- pruning a fail-high inside a PV
                // node can silently corrupt the actual principal
                // variation, not just tighten a sibling's bound, so
                // this closes a real gap rather than relying on it not
                // mattering in practice.
                ASSERT(!uFutilityMargin);
                if ((FALSE == pi->fPvNode) &&
                    (iOrigExtend == 0) &&
                    (ctx->uPly >= 2) &&
                    (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0))
                {
                    ASSERT(uDepth >= THREE_QUARTERS_PLY);

                    if (iEval < iAlpha)
                    {
                        if ((uDepth <= ONE_PLY + THREE_QUARTERS_PLY) &&
                            (iEval + VALUE_KNIGHT + iImprovement <= iAlpha))
                        {
                            uFutilityMargin = (iAlpha - iEval) / 2;
                        }
                        else if ((uDepth > ONE_PLY + THREE_QUARTERS_PLY) &&
                                 (uDepth <= TWO_PLY + THREE_QUARTERS_PLY) &&
                                 (iEval + VALUE_ROOK + iImprovement <= iAlpha))
                        {
                            uFutilityMargin = (iAlpha - iEval) / 2;
                        }
                    }
                }
                uStage++;
                ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]);
                // fall through

            case TRY_GENERATED_MOVES:
                if (x < ctx->sMoveStack.uEnd[ctx->uPly])
                {
                    ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]);
                    // Always fully select the best remaining move,
                    // regardless of tier -- retired the old
                    // NumLeftoverMovesToSelect budget (a depth-indexed
                    // cutoff on how many "leftover", i.e. sub-GOOD_MOVE,
                    // moves were worth a full SelectBestWithHistory scan
                    // before taking the remainder in whatever order it
                    // sat in) once this session's evidence-calibration
                    // work (see chess.h's COUNTERMOVE_EVIDENCE_THRESHOLD/
                    // FLEE_BONUS) showed the leftover pool has real,
                    // findable signal -- countermove matches and
                    // continuation-history-backed quiet moves both fail
                    // high at rates well above the pool's average -- so
                    // a bailout budget was discarding real information
                    // for a node-count savings that didn't hold up
                    // net-net once measured properly (solve counts and
                    // leftover fail-high rates, not raw node counts,
                    // which are too noisy on small suites to trust
                    // alone). GOOD_MOVE itself is still meaningful here:
                    // it's generate.c's own quality floor (below every
                    // killer tier and SORT_THESE_FIRST's winning/even-
                    // capture range), used below only to classify a
                    // move as "leftover" for EFP eligibility and
                    // instrumentation, not to gate how it's searched.
                    //
                    // On an IID-rescored ply, iValue is a real eval-axis
                    // score (see RescoreMovesViaSearch/ComputeMoveScore)
                    // -- GOOD_MOVE is meaningless on that axis, so this
                    // never classifies an IID-rescored move as a
                    // leftover (matches pre-retirement behavior).
                    fIsLeftoverMove = FALSE;
                    if (TRUE == pi->fMovesRescoredByIID)
                    {
                        SelectBestNoHistory(ctx, x);
                    }
                    else
                    {
                        SelectBestWithHistory(ctx, x);
                        fIsLeftoverMove = (ctx->sMoveStack.mvf[x].iValue < GOOD_MOVE);
                    }
                    mv = ctx->sMoveStack.mvf[x].mv;
#ifdef DEBUG
                    ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags &
                                 MVF_MOVE_SEARCHED));
                    ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
#endif
                    // Countermove evidence calibration -- ongoing check
                    // that COUNTERMOVE_EVIDENCE_THRESHOLD (chess.h) is
                    // still well-calibrated: log every countermove-
                    // matched move tried, bucketed by its own
                    // accumulated history+continuation evidence.
#ifdef PERF_COUNTERS
                    fThisMoveIsCountermoveMatch = FALSE;
                    if ((!IS_CAPTURE_OR_PROMOTION(mv)) &&
                        (ctx->uPly > 0) &&
                        (0 != (pi - 1)->mv.uMove) &&
                        (IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX((pi - 1)->mv)][0]) ||
                         IS_SAME_MOVE(mv, ctx->mvCounter[MOVE_TO_INDEX((pi - 1)->mv)][1])))
                    {
                        ULONG uEvidence = g_HistoryCounters[mv.pMoved][mv.cTo] +
                            g_ContinuationHistory[(MOVE_TO_CONT_KEY((pi - 1)->mv) *
                                                   CONT_KEY_RANGE) +
                                                  MOVE_TO_CONT_KEY(mv)];
                        fThisMoveIsCountermoveMatch = TRUE;
                        uCMEvidenceBucket = _CMEvidenceBucket(uEvidence);
                    }
#endif
                    mv.bvFlags |= WouldGiveCheck(ctx, mv);

                    // Note: x is the index of the NEXT move to be
                    // considered, this move's index is (x-1).
                    x++;
                    break;
                }
                // else fall through

            default:
                goto no_more_moves;
        }
        ASSERT(mv.uMove);
        ASSERT(SanityCheckMove(pos, mv));

#ifdef MP
        // Can we search the remaining moves in parallel?  Note:
        // uDepth can legitimately be < ONE_PLY here (fractional
        // depth from a reduction) -- uDepth/ONE_PLY - 1 would
        // underflow (ULONG) in that case, which is exactly why the
        // uDepth >= ONE_PLY check below short-circuits before the
        // g_fCanSplit[] indexing ever evaluates it.
        if (((uLegalMoves >= 2) && fIsLeftoverMove) &&
            (0 != g_uNumHelpersAvailable) &&
            (FALSE == pi->fMovesRescoredByIID) &&
            (0 == uFutilityMargin) &&
            (uDepth >= ONE_PLY) &&
            (TRUE == g_fCanSplit[uDepth / ONE_PLY - 1]) &&
            (MOVE_COUNT(ctx, ctx->uPly) > 4))
        {
            ASSERT(pf->fAvoidNullmove == FALSE);
            ASSERT(uStage == TRY_GENERATED_MOVES);
            ASSERT(x != 0);
            ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
            ASSERT(iBestScore <= iAlpha);
            ctx->sMoveStack.mvf[x-1].bvFlags &= ~MVF_MOVE_SEARCHED;
            iScore = StartParallelSearch(ctx,
                                         &iAlpha,
                                         iBeta,
                                         iImprovement,
                                         &iBestScore,
                                         &mvBest,
                                         (x - 1),
                                         iOrigExtend,
                                         uDepth);
            ASSERT(iAlpha < iBeta);
            ASSERT((IS_SAME_MOVE(pi->PV[ctx->uPly], mvBest)) ||
                   (iScore <= iAlpha) || (iScore >= iBeta));
            ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
#ifdef DEBUG
            VerifyPositionConsistency(pos, FALSE);
#endif
            if (IS_VALID_SCORE(iScore))
            {
                pi->mvBest = mvBest;
                goto no_more_moves;
            }
            else
            {
                ASSERT(WE_SHOULD_STOP_SEARCHING);
                iBestScore = iScore;
                goto end;
            }
            ASSERT(FALSE);
        }
#endif

        // SEE must be computed on the PRE-move position -- see.c's
        // exchange walk needs the piece still sitting on cFrom. Only
        // needed for checking moves, where ComputeMoveExtension uses it
        // to gate the check extension on soundness (Crafty-style: don't
        // extend a checking move that's really just a losing sacrifice).
        iCheckSee = 0;
        if (IS_CHECKING_MOVE(mv))
        {
            iCheckSee = GetCheckSee(ctx,
                                    mv,
                                    (uStage == TRY_GENERATED_MOVES) ?
                                        (x - 1) : (ULONG)-1);
        }

        if (TRUE == MakeMove(ctx, mv))
        {
            uLegalMoves++;
            ASSERT((IS_CHECKING_MOVE(mv) && InCheck(pos, pos->uToMove)) ||
                   (!IS_CHECKING_MOVE(mv) && !InCheck(pos, pos->uToMove)));

            // Compute per-move extension (as opposed to per-position
            // extensions which are represented by iOrigExtend).
            iExtend = iOrigExtend;
            ComputeMoveExtension(ctx,
                                 iAlpha,
                                 iBeta,
                                 (x - 1),     // Note: x==0 if doing mvHash
                                 iEval,
                                 uDepth,
                                 iCheckSee,
                                 &iExtend);

            // Note: MAX_EXTEND_PER_LINE (a flat, non-depth-relative cap on
            // total extension spent per line) used to be applied here.
            // Removed -- g_uExtensionReduction[] (consumed inside
            // ComputeMoveExtension, scaled off g_uIterateDepth) is the
            // sole extension-runaway guard now; see root.c's construction
            // of that table.

            // Decide how much (if any) to reduce this move's depth --
            // graded LMR.
            if ((uDepth > TWO_PLY) &&
                !pi->fPvNode &&
                !(ctx->sPlyInfo[ctx->uPly - 1].fPvNode) &&
                (uLegalMoves > 5) &&
                (0 == iExtend) &&
                (!IS_ESCAPING_CHECK(mv)) &&
                (!IS_CAPTURE_OR_PROMOTION(mv)) &&
                (!IS_CHECKING_MOVE(mv)))
            {
                INT iLMR = GetLMRReduction(iEval,
                                           iAlpha,
                                           iBeta,
                                           iImprovement,
                                           ctx,
                                           uDepth,
                                           uLegalMoves,
                                           mv,
                                           (x - 1), // Note: x==0 if hash
                                           iExtend);
                if (iLMR < 0)
                {
                    ASSERT(iExtend == 0);
                    iExtend = iLMR;
                    pi->iExtensionAmount = iLMR;
                }
            }

            // Extended futility pruning -- per-move checklist. EFP
            // pruning a fail-high is unrecoverable (unlike an LMR
            // reduction, which only delays discovery), so this is
            // deliberately stricter than GetLMRReduction's own
            // checklist, not just a copy of it: explicit capture/
            // promotion/checking-move exemptions (not just an ASSERT
            // that they can't reach here, which is all the old code
            // had), a killer-adjacency exemption (ply-1 and ply-3,
            // borrowed from GetLMRReduction), a well-evidenced
            // fail-high-history exemption (GetMoveFailHighPercentage,
            // requiring at least EFP_FH_MIN_SAMPLES observations before
            // trusting the percentage either way), an en-prise-escape
            // exemption, and a node-wide suppression when this node's
            // own null-move probe raised fThreat. See
            // lmr_testing/RESULTS.md for the individual experiments
            // that arrived at this checklist.
            //
            // Explicit leftover-only gate (fIsLeftoverMove, this move's
            // own iValue < GOOD_MOVE): every high-performer move
            // (winning/even capture, killer, killer-mate, sufficiently-
            // evidenced countermove match) is excluded from pruning
            // consideration by construction, not just as a side effect
            // of the capture/check/killer exemptions above happening to
            // cover the same ground. Belt-and-suspenders on purpose --
            // this is the one thing that must never be true of a move
            // we skip outright.
            fThisMoveEFPPruned = FALSE;
            if ((x != 0) &&
                (uLegalMoves > 1) &&
                (uFutilityMargin) &&
                (TRUE == fIsLeftoverMove) &&
                (iExtend <= 0) &&
                (!IS_ESCAPING_CHECK(mv)) &&
                (!IS_CAPTURE_OR_PROMOTION(mv)) &&
                (!IS_CHECKING_MOVE(mv)) &&
                (!fThreat) &&
                (ComputeMoveScore(ctx, mv, (x - 1)) < uFutilityMargin))
            {
                ULONG uFHAttempts = 0;
                ULONG uFHPct = GetMoveFailHighPercentage(mv, &uFHAttempts);
                fThisMoveEFPPruned =
                    ((uFHAttempts < EFP_FH_MIN_SAMPLES) ||
                     (uFHPct <= EFP_FH_PRUNE_THRESHOLD)) &&
                    (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0])) &&
                    (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) &&
                    ((ctx->uPly < 3) ||
                     (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) &&
                      !IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1])));
            }
            if (TRUE == fThisMoveEFPPruned)
            {
                fAnyMoveEFPPruned = TRUE;
                UnmakeMove(ctx, mv);
                ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
            }
            else
            {
#ifdef PERF_COUNTERS
                if (TRUE == fIsLeftoverMove)
                {
                    INC(ctx->sCounters.tree.u64LeftoverTries);
                }
                if (TRUE == fThisMoveIsCountermoveMatch)
                {
                    INC(ctx->sCounters.tree.u64CMEvidenceTries[uCMEvidenceBucket]);
                }
#endif
                // Compute the next search depth for this move/subtree.
                uNextDepth = uDepth - ONE_PLY + iExtend;
                if (uNextDepth >= MAX_DEPTH_PER_SEARCH) uNextDepth = 0;
                pf->iCumulativeExtend += iExtend;
                ASSERT(pf->fAvoidNullmove == FALSE);
                if (iBestScore == -INFINITY)
                {
                    // First move, full a..b window.
                    ASSERT(uLegalMoves == 1);
                    iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
                }
                else
                {
                    // Moves 2..N, try a minimal window search
                    iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uNextDepth);
                    if ((iAlpha < iScore) && (iScore < iBeta))
                    {
                        iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
                    }
                }

                // Research deeper if history pruning failed
                if ((iExtend < 0) && (iScore >= iBeta))
                {
                    uNextDepth -= iExtend; // undo the full reduction, whatever its magnitude
                    pi->iExtensionAmount = 0;
                    iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
                }
                UnmakeMove(ctx, mv);
                pf->iCumulativeExtend -= iExtend;
                ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
                if (WE_SHOULD_STOP_SEARCHING)
                {
                    iBestScore = iScore;
                    goto end;
                }

                // Check results
                ASSERT(iBestScore <= iAlpha);
                ASSERT(iAlpha < iBeta);
                if (iScore > iBestScore)
                {
                    iBestScore = iScore;
                    mvBest = mv;
                    pi->mvBest = mv;

                    if (iScore > iAlpha)
                    {
                        if (iScore >= iBeta)
                        {
#ifdef PERF_COUNTERS
                            if (TRUE == fIsLeftoverMove)
                            {
                                INC(ctx->sCounters.tree.u64LeftoverFH);
                            }
                            if (TRUE == fThisMoveIsCountermoveMatch)
                            {
                                INC(ctx->sCounters.tree.u64CMEvidenceFH[uCMEvidenceBucket]);
                            }
#endif
                            // Update history and killers list and store in
                            // the transposition table.
                            UpdateDynamicMoveOrdering(ctx,
                                                      uDepth,
                                                      mv,
                                                      iScore,
                                                      x);
                            StoreLowerBound(mv, pos, iScore, uDepth, fThreat);

                            // A fail-high capturing a non-pawn piece is
                            // search-proven evidence that piece was en
                            // prise -- but the victim belongs to the
                            // *other* side, i.e. whoever is to move at
                            // ctx->uPly - 1 (ply parity), not here --
                            // "despite the move you're about to make,
                            // this piece stays in trouble."  Skip near
                            // mate: a fail-high there means the whole
                            // subtree is winning regardless of this
                            // particular piece, not that it was
                            // specifically hanging.
                            if (mv.pCaptured && !IS_PAWN(mv.pCaptured) &&
                                (iBeta < +NMATE))
                            {
                                ASSERT(ctx->uPly > 0);
                                RecordEnprisePieceAtPly(ctx, ctx->uPly - 1,
                                                        mv.cTo);
                            }
                            KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
                            ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
                            goto end;
                        }
                        else
                        {
#ifdef PERF_COUNTERS
                            if (TRUE == fIsLeftoverMove)
                            {
                                INC(ctx->sCounters.tree.u64LeftoverAlpha);
                            }
#endif
                            // PV move...
                            UpdatePV(ctx, mv);
                            iAlpha = iScore;
                        }
                    }
                }
            }
        }
    }
    while(1); // foreach move

 no_more_moves:
    ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));

    // Detect checkmates and stalemates
    if (0 == uLegalMoves)
    {
        if (pi->fInCheck)
        {
            ASSERT(IS_CHECKING_MOVE(mvLast));
            ASSERT(InCheck(pos, pos->uToMove));
            iBestScore = MATED_SCORE(ctx->uPly);
            if ((iAlpha < iBestScore) && (iBestScore < iBeta))
            {
                INC(ctx->sCounters.tree.u64LeafCount);
                UpdatePV(ctx, MATEMOVE);
            }
            ASSERT(iBestScore <= -NMATE);
            goto end;
        }
        else
        {
            iBestScore = g_iDrawScore[pos->uToMove];
            if ((iAlpha < iBestScore) && (iBestScore < iBeta))
            {
                INC(ctx->sCounters.tree.u64LeafCount);
                UpdatePV(ctx, DRAWMOVE);
            }
            goto end;
        }
    }

    // Not checkmate/stalemate; store the result of this search in the
    // hash table.
    //
    // Ernst Heinz's warning (the book EFP is from): a node whose search
    // depended on alpha/beta via forward pruning (a move skipped
    // entirely, not just reduced -- LMR still searches its move, just
    // shallower, so it isn't affected) cannot have its result stored as
    // an exact score or a sound upper bound. If EFP skipped a move here
    // without searching it, that move might have actually been the
    // best one -- the true value could be *higher* than what we
    // computed, in either case. An "exact" claim needs to know nothing
    // better existed; an upper-bound claim needs the true value to be
    // <= what we stored, both of which a skipped-but-possibly-better
    // move can violate. mvBest/iBestScore (when found) remains a sound
    // LOWER bound regardless -- we have a real line proving the
    // position is at least this good -- so that's the most this node
    // can honestly claim once fAnyMoveEFPPruned is set.
    if ((iAlpha != iInitialAlpha) && (FALSE == fAnyMoveEFPPruned))
    {
        ASSERT(mvBest.uMove != 0);
        if (!IS_CAPTURE_OR_PROMOTION(mvBest))
        {
            UpdateDynamicMoveOrdering(ctx,
                                      uDepth,
                                      mvBest,
                                      iBestScore,
                                      0);
        }
        StoreExactScore(mvBest, pos, iBestScore, uDepth, fThreat, ctx->uPly);
    }
    else if ((iAlpha != iInitialAlpha) && (TRUE == fAnyMoveEFPPruned))
    {
        // Downgrade: mvBest proves a real achieving line, so this is a
        // sound lower bound, just not provably exact.
        ASSERT(mvBest.uMove != 0);
        if (!IS_CAPTURE_OR_PROMOTION(mvBest))
        {
            UpdateDynamicMoveOrdering(ctx,
                                      uDepth,
                                      mvBest,
                                      iBestScore,
                                      0);
        }
        StoreLowerBound(mvBest, pos, iBestScore, uDepth, fThreat);
    }
    else if (FALSE == fAnyMoveEFPPruned)
    {
        // IDEA: "I am very well aware of the fact, that the scores
        // you get back outside of the window, are not trustable at
        // all. Still, I have mentioned the case, of all scores being
        // losing mate scores, but one is not. This move will be good
        // to try first. I have seen this, by investigating multi MB
        // large tree dumps, so it is not only there in theory. Often,
        // even with fail soft, I of course will also get multiple
        // moves with the same score (alpha). But then one can see the
        // "best" move as an additional killer move. It was most
        // probably the killer move anyway, when this position was
        // visited the last time. I cannot see a reason, why trying
        // such a move early could hurt. And I do see reductions of
        // tree sizes. I don't try upper-bound moves first. I try them
        // (more or less) after the good captures, and together with
        // the killer moves, but before history moves."
        //                                            --Ed Schroder
        StoreUpperBound(pos, iBestScore, uDepth, fThreat);
    }
    // else: fail-low (iAlpha == iInitialAlpha) AND fAnyMoveEFPPruned --
    // no sound bound in either direction to store (the skipped move
    // could have raised the true value above iBestScore, so it's not a
    // valid upper bound; there's no mvBest to offer as a lower bound
    // either, since nothing beat alpha). Store nothing rather than
    // cache an unsound result.

 end:
    ASSERT(IS_VALID_SCORE(iBeta));
    ASSERT(IS_VALID_SCORE(iAlpha));
    ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
    ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
    DTLeaveNode(ctx, FALSE, iBestScore, mvBest);
    return(iBestScore);
}


/**

Routine description:

    This routine is called by QSearch, the select part of the
    recursive search code.  Its job is to determine if a move
    generated is worth searching.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx : searcher context
    ULONG uMoveNum : the move number we are considering
    SCORE iFutility : the futility line

Return value:

    FLAG : TRUE if the move is worth considering,
           FALSE if it can be skipped

**/
#ifdef CALIBRATE_QSEARCH_FUTILITY
// 2026-09-08: measures whether _ShouldWeConsiderThisMove's futility
// gates are set correctly, by -- at the moment a move would be
// rejected -- actually searching it anyway (fully unpruned, via
// ctx->fDiagUnprunedSubtree) and checking whether it would genuinely
// have raised alpha. Never changes real search behavior: the
// diagnostic re-search's result is used only to log a sample, then
// discarded (same non-interference pattern as CALIBRATE_MARGIN_SAFETY
// in eval.c).
//
// Bucketed by (gate, margin-neutral distance short of the relevant
// threshold, piPositional bucket, which Eval() tier supplied
// piPositional) so a single run answers several questions at once:
// is the margin itself wide enough (distance-vs-surprise-rate curve
// within a gate), does piPositional actually predict surprises
// (compare curves across piPositional buckets at the same distance),
// and does that answer differ by tier (super-lazy vs regular-lazy vs
// full eval).
#define QFUT_DIST_BUCKETS (6)
#define QFUT_POS_BUCKETS  (4)

static UINT64 g_uQFutTries[QFUT_GATE_COUNT][QFUT_DIST_BUCKETS][QFUT_POS_BUCKETS][EVAL_POSITIONAL_SOURCE_COUNT];
static UINT64 g_uQFutSurprises[QFUT_GATE_COUNT][QFUT_DIST_BUCKETS][QFUT_POS_BUCKETS][EVAL_POSITIONAL_SOURCE_COUNT];

static ULONG
_QFutDistanceBucket(IN SCORE iDistance)
/* iDistance: how far short of the relevant threshold this move was
   (positive = short; a move that actually cleared the bar never gets
   here, so this should always be > 0, but negative/zero is folded
   into bucket 0 defensively rather than asserting -- a measurement
   harness should never crash a calibration run over its own bucketing
   edge case). */
{
    if (iDistance <= 25)   return(0);
    if (iDistance <= 50)   return(1);
    if (iDistance <= 100)  return(2);
    if (iDistance <= 200)  return(3);
    if (iDistance <= 400)  return(4);
    return(5);
}

static ULONG
_QFutPositionalBucket(IN SCORE iPositional)
{
    if (iPositional < 0)    return(0);
    if (iPositional < 25)   return(1);
    if (iPositional < 75)   return(2);
    return(3);
}

static void
_QFutDiagnoseReject(IN SEARCHER_THREAD_CONTEXT *ctx,
                    IN ULONG uMoveNum,
                    IN SCORE iAlpha,
                    IN SCORE iBeta,
                    IN SCORE iPositional,
                    IN ULONG uPositionalSource,
                    IN ULONG uGate,
                    IN SCORE iDistance,
                    IN FLAG fGeneratedChecks)
/**

Routine description:

    A move is about to be rejected by one of _ShouldWeConsiderThisMove's
    futility gates. Before rejecting it for real, search it anyway
    (fully unpruned) to see whether it would actually have raised
    alpha, and log the outcome. The diagnostic search's result is
    discarded -- this function never changes what the caller does.

Return value:

    void

**/
{
    MOVE mv;
    SCORE iScore;
    ULONG uDistBucket, uPosBucket;

    // Never diagnose from inside an already-diagnostic (fully
    // unpruned) subtree -- structurally shouldn't happen anyway, since
    // nothing gets rejected while fDiagUnprunedSubtree is set, but
    // guard explicitly rather than relying on that.
    if (TRUE == ctx->fDiagUnprunedSubtree)
    {
        return;
    }
    ASSERT(uGate < QFUT_GATE_COUNT);
    ASSERT(uPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT);

    mv = ctx->sMoveStack.mvf[uMoveNum].mv;
    // Mirror QSearch's own move loop exactly: GenerateMoves only tags
    // MVF_CHECK/the checking-move bit when checks were actually being
    // generated this ply. Skipping this (as an earlier version of this
    // function did) leaves the flag unset on a move that objectively
    // does give check, which MakeMove/ply-info bookkeeping trusts
    // blindly -- the next ply's fInCheck-vs-InCheck() consistency
    // ASSERT (searchsup.c) catches the mismatch immediately.
    if (FALSE == fGeneratedChecks)
    {
        mv.bvFlags |= WouldGiveCheck(ctx, mv);
    }
    if (FALSE == MakeMove(ctx, mv))
    {
        return;
    }
    ctx->fDiagUnprunedSubtree = TRUE;
    ctx->sSearchFlags.uQsearchDepth++;
    iScore = -QSearch(ctx, -iBeta, -iAlpha);
    ctx->sSearchFlags.uQsearchDepth--;
    ctx->fDiagUnprunedSubtree = FALSE;
    UnmakeMove(ctx, mv);

    uDistBucket = _QFutDistanceBucket(iDistance);
    uPosBucket = _QFutPositionalBucket(iPositional);
    g_uQFutTries[uGate][uDistBucket][uPosBucket][uPositionalSource]++;
    if (iScore > iAlpha)
    {
        g_uQFutSurprises[uGate][uDistBucket][uPosBucket][uPositionalSource]++;
    }
}


static CHAR *g_szQFutGateNames[QFUT_GATE_COUNT] =
{
    "generic capture/promo",
    "checking capture/promo (VALUE_ROOK)",
    "quiet check (VALUE_BISHOP)",
};
static CHAR *g_szQFutSourceNames[EVAL_POSITIONAL_SOURCE_COUNT] =
{
    "full eval",
    "regular lazy",
    "super lazy",
};

void
DumpQSearchFutilityCalibration(void)
/**

Routine description:

    Print, per (gate, piPositional-source tier), the surprise rate
    (fraction of diagnostically-re-searched rejects that actually
    raised alpha) by distance-short-of-threshold bucket, and
    separately by piPositional bucket at the widest distance bucket --
    read the former for "is this gate's margin wide enough," the
    latter (compared across piPositional buckets at a fixed distance)
    for "does piPositional actually predict surprises."

Parameters:

    void

Return value:

    void

**/
{
    ULONG g, d, p, s;
    static CHAR *szDistLabel[QFUT_DIST_BUCKETS] =
        { "0-25", "25-50", "50-100", "100-200", "200-400", "400+" };
    static CHAR *szPosLabel[QFUT_POS_BUCKETS] =
        { "<0", "0-25", "25-75", "75+" };

    for (g = 0; g < QFUT_GATE_COUNT; g++)
    {
        Trace("QSearch futility gate: %s\n", g_szQFutGateNames[g]);
        for (s = 0; s < EVAL_POSITIONAL_SOURCE_COUNT; s++)
        {
            UINT64 u64TotalTries = 0;
            for (d = 0; d < QFUT_DIST_BUCKETS; d++)
            {
                for (p = 0; p < QFUT_POS_BUCKETS; p++)
                {
                    u64TotalTries += g_uQFutTries[g][d][p][s];
                }
            }
            if (0 == u64TotalTries)
            {
                continue;
            }
            Trace("  source=%s (n=%" COMPILER_LONGLONG_UNSIGNED_FORMAT "):\n",
                  g_szQFutSourceNames[s], u64TotalTries);
            Trace("    by distance short of bar (summed over piPositional buckets):\n");
            for (d = 0; d < QFUT_DIST_BUCKETS; d++)
            {
                UINT64 u64Tries = 0, u64Surprises = 0;
                for (p = 0; p < QFUT_POS_BUCKETS; p++)
                {
                    u64Tries += g_uQFutTries[g][d][p][s];
                    u64Surprises += g_uQFutSurprises[g][d][p][s];
                }
                if (0 == u64Tries)
                {
                    continue;
                }
                Trace("      dist %8s: %6.2f%% surprise rate (n=%"
                      COMPILER_LONGLONG_UNSIGNED_FORMAT ")\n",
                      szDistLabel[d],
                      100.0 * (double)u64Surprises / (double)u64Tries,
                      u64Tries);
            }
            Trace("    by piPositional bucket (summed over distance buckets):\n");
            for (p = 0; p < QFUT_POS_BUCKETS; p++)
            {
                UINT64 u64Tries = 0, u64Surprises = 0;
                for (d = 0; d < QFUT_DIST_BUCKETS; d++)
                {
                    u64Tries += g_uQFutTries[g][d][p][s];
                    u64Surprises += g_uQFutSurprises[g][d][p][s];
                }
                if (0 == u64Tries)
                {
                    continue;
                }
                Trace("      pos %6s: %6.2f%% surprise rate (n=%"
                      COMPILER_LONGLONG_UNSIGNED_FORMAT ")\n",
                      szPosLabel[p],
                      100.0 * (double)u64Surprises / (double)u64Tries,
                      u64Tries);
            }
            // The marginals above can each look flat on their own even
            // when piPositional genuinely matters (its effect might
            // only show up at a fixed distance) -- this is the actual
            // Q2 answer: read a single distance row across columns. If
            // the percentages don't move across piPositional buckets
            // at a fixed distance, it isn't predictive; if they fall
            // as piPositional rises, it is.
            Trace("    cross-tab, surprise%% (rows=distance, cols=piPositional "
                  "%s/%s/%s/%s):\n",
                  szPosLabel[0], szPosLabel[1], szPosLabel[2], szPosLabel[3]);
            for (d = 0; d < QFUT_DIST_BUCKETS; d++)
            {
                UINT64 u64RowTries = 0;
                for (p = 0; p < QFUT_POS_BUCKETS; p++)
                {
                    u64RowTries += g_uQFutTries[g][d][p][s];
                }
                if (0 == u64RowTries)
                {
                    continue;
                }
                Trace("      dist %8s:", szDistLabel[d]);
                for (p = 0; p < QFUT_POS_BUCKETS; p++)
                {
                    UINT64 u64Tries = g_uQFutTries[g][d][p][s];
                    if (0 == u64Tries)
                    {
                        Trace("   n/a        ");
                    }
                    else
                    {
                        Trace(" %5.1f%% (n=%5" COMPILER_LONGLONG_UNSIGNED_FORMAT ")",
                              100.0 * (double)g_uQFutSurprises[g][d][p][s] /
                                  (double)u64Tries,
                              u64Tries);
                    }
                }
                Trace("\n");
            }
        }
    }
}
#endif // CALIBRATE_QSEARCH_FUTILITY


// Flat bonus added to a checking capture/promotion's own (real,
// winning/even) iMoveValue before comparing against iFutility --
// replaces the retired VALUE_ROOK position-level cutoff for exactly
// this population (see _ShouldWeConsiderThisMove's comment at its use
// site for why). Provisional -- no calibration data yet for this
// specific split; re-measure with `calibrate qsearchfutility`.
#define CHECK_BONUS (150)


static FLAG INLINE
_ShouldWeConsiderThisMove(IN SEARCHER_THREAD_CONTEXT *ctx,
                          IN ULONG uMoveNum,
                          IN SCORE iFutility,
                          IN FLAG fGeneratedChecks
#ifdef CALIBRATE_QSEARCH_FUTILITY
                          , IN SCORE iAlpha
                          , IN SCORE iBeta
                          , IN SCORE iPositional
                          , IN ULONG uPositionalSource
#endif
                          )
{
#ifdef DEBUG
    MOVE mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv;
#endif
    MOVE mv = ctx->sMoveStack.mvf[uMoveNum].mv;
    ULONG uColor;
    SCORE iMoveValue;
    // TRUE once iMoveValue holds a real, comparable SEE-derived value
    // (winning/even captures and promotions) rather than the raw,
    // not-directly-comparable generation-time score a losing capture
    // keeps. Used both for real control flow (the checking-move
    // branch below needs to know which of two populations it's
    // looking at) and, under CALIBRATE_QSEARCH_FUTILITY, to decide
    // whether a reject is worth diagnosing.
    FLAG fHaveMoveValue = FALSE;

    ASSERT(!IS_CHECKING_MOVE(mvLast));
    ASSERT(!InCheck(&(ctx->sPosition), ctx->sPosition.uToMove));

    if (IS_CAPTURE_OR_PROMOTION(mv))
    {
        // IDEA: if mvLast was a promotion, try everything here?

        // Don't consider promotions to anything but queens unless
        // it's a knight and we are going for a knockout.
        if ((mv.pPromoted) && (!IS_QUEEN(mv.pPromoted)))
        {
            if (!IS_KNIGHT(mv.pPromoted) ||
                !IS_CHECKING_MOVE(mv) ||
                (FALSE == fGeneratedChecks))
            {
                return(FALSE);
            }
        }

        iMoveValue = ctx->sMoveStack.mvf[uMoveNum].iValue;
        if (iMoveValue >= SORT_THESE_FIRST)
        {
            fHaveMoveValue = TRUE;
            iMoveValue &= STRIP_OFF_FLAGS;
            ASSERT(iMoveValue >= 0);
            iMoveValue -= MOVE_SCORE_ORDERING_BIAS(mv);
            if (mv.pCaptured)
            {
                // If there are very few pieces left on the board,
                // consider all captures because we could be, for
                // example, taking the guy's last pawn and forcing a
                // draw.  Even though the cap looks futile the draw
                // might save the game...
                uColor = GET_COLOR(mv.pCaptured);
                ASSERT(OPPOSITE_COLORS(ctx->sPosition.uToMove, uColor));
                if ((IS_PAWN(mv.pCaptured) &&
                     ctx->sPosition.uPawnCount[uColor] == 1) ||
                    (!IS_PAWN(mv.pCaptured) &&
                     ctx->sPosition.uNonPawnCount[uColor][0] == 2))
                {
                    return(TRUE);
                }

                // Also always consider "dangerous pawn" captures.
                if (IS_PAWN(mv.pMoved) &&
                    (((GET_COLOR(mv.pMoved) == WHITE) && RANK7(mv.cTo)) ||
                     ((GET_COLOR(mv.pMoved) == BLACK) && RANK2(mv.cTo))))
                {
                    return(TRUE);
                }

                // Don't trust the SEE alone for alpha pruning decisions.
                iMoveValue = MAXU(iMoveValue, PIECE_VALUE(mv.pCaptured));

                // RETIRED 2026-09-08: used to give recaptures (same
                // captured-piece value as mvLast) a flat +100 bonus
                // here ("the bad trade penalty can make them look
                // futile sometimes"). CALIBRATE_QSEARCH_FUTILITY data
                // showed it wasn't testing real recaptures at all --
                // this check never compared mv.cTo to mvLast.cTo, so
                // "recapture-shaped" meant "captured a same-valued
                // piece anywhere on the board," diluting genuine
                // recaptures (usually safe) with unrelated captures
                // (not specially safe) under one bonus. That mismatch
                // is the more likely explanation for the gate's high,
                // slowly-decaying surprise rate (13.25% at distance
                // 0-25, still 3.29% at 400+) than the constant being
                // merely too small. Removed rather than re-tuned;
                // reintroduce with a same-square check if a bonus
                // still looks warranted once the generic gate's own
                // margin is fixed.
            }

            // Otherwise, even if a move is even/winning, make sure it
            // brings the score up to at least somewhere near alpha.
            if (iMoveValue > iFutility)
            {
                return(TRUE);
            }
        }

        // If we get here the move was either a losing capture/prom
        // that checked or a "futile" winning capture/prom that may or
        // may not check.  Be more willing to play checking captures
        // even if they look bad.
        //
        // RETIRED VALUE_ROOK 2026-09-08: used to judge both
        // populations below by a single position-level "iFutility <
        // VALUE_ROOK" cutoff, discarding iMoveValue entirely even
        // when a real one existed. CALIBRATE_QSEARCH_FUTILITY data
        // showed a flat, non-decaying-with-distance surprise rate
        // (8-16%, no better far past the threshold than right at it)
        // -- the signature of a position-level test standing in for a
        // move-level question it can't actually answer. Split into
        // the two populations that were being conflated: a move with
        // a real (winning/even) iMoveValue gets the same value-plus-
        // flat-bonus treatment as any other capture; a move with no
        // usable value (SEE already called it losing) falls back to
        // GetCheckSee's real tactical judgment, exactly like the
        // quiet-check (VALUE_BISHOP) branch already does below.
        if (IS_CHECKING_MOVE(mv) && (TRUE == fGeneratedChecks))
        {
            if (TRUE == fHaveMoveValue)
            {
                FLAG fConsider = (iMoveValue + CHECK_BONUS > iFutility);
#ifdef CALIBRATE_QSEARCH_FUTILITY
                if (FALSE == fConsider)
                {
                    _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta,
                                        iPositional, uPositionalSource,
                                        QFUT_GATE_CHECK_ROOK,
                                        iFutility - (iMoveValue + CHECK_BONUS),
                                        fGeneratedChecks);
                }
#endif
                return(fConsider);
            }
            {
                FLAG fConsider = (GetCheckSee(ctx, mv, uMoveNum) >= 0);
#ifdef CALIBRATE_QSEARCH_FUTILITY
                if (FALSE == fConsider)
                {
                    // No value-level threshold left for this
                    // population (that's the point) -- iFutility
                    // itself is the only position-level number left
                    // to bucket by, used as-is rather than a
                    // difference from some retired constant.
                    _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta,
                                        iPositional, uPositionalSource,
                                        QFUT_GATE_CHECK_ROOK,
                                        iFutility,
                                        fGeneratedChecks);
                }
#endif
                return(fConsider);
            }
        }

#ifdef CALIBRATE_QSEARCH_FUTILITY
        // Falls through to the final reject below -- either not a
        // checking move, or a checking move we weren't generating
        // checks for this ply (rare; the generic gate is still what
        // decided this, so tag it the same way).
        if (TRUE == fHaveMoveValue)
        {
            _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta,
                                iPositional, uPositionalSource,
                                QFUT_GATE_GENERIC_CAPTURE,
                                iFutility - iMoveValue,
                                fGeneratedChecks);
        }
#endif
    }
    else
    {
        // If we get here we have a checking move that does not
        // capture anything or promote anything.  We are interested in
        // these to some depth.
        ASSERT(IS_CHECKING_MOVE(mv));
        ASSERT(TRUE == fGeneratedChecks);

        // IDEA: don't play obviously losing checks if we are already
        // way below alpha.
        if (iFutility < +VALUE_BISHOP)
        {
            return(TRUE);
        }
        {
            FLAG fConsider = (GetCheckSee(ctx, mv, uMoveNum) >= 0);
#ifdef CALIBRATE_QSEARCH_FUTILITY
            if (FALSE == fConsider)
            {
                _QFutDiagnoseReject(ctx, uMoveNum, iAlpha, iBeta,
                                    iPositional, uPositionalSource,
                                    QFUT_GATE_CHECK_BISHOP,
                                    iFutility - (SCORE)VALUE_BISHOP,
                                    fGeneratedChecks);
            }
#endif
            return(fConsider);
        }
    }
    return(FALSE);
}


/**

Routine description:

    Side to move is in check and may or may not have had a chance to
    stand pat at a qnode above this point.  Search all legal check
    evasions and return a mate-in-n score if this is checkmate.
    Possibly extend the depth to which we generate checks under this
    node.  If there's a stand pat qnode above us the mate-in-n will be
    weeded out.

Parameters:

    IN SEARCHER_THREAD_CONTEXT *ctx,
    IN SCORE iAlpha,
    IN SCORE iBeta

Return value:

    SCORE

**/
SCORE
QSearchFromCheckNoStandPat(IN SEARCHER_THREAD_CONTEXT *ctx,
                           IN SCORE iAlpha,
                           IN SCORE iBeta)
{
    POSITION *pos = &ctx->sPosition;
    CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
    ULONG x, uMoveCount;
    SCORE iBestScore = MATED_SCORE(ctx->uPly);
    SCORE iScore;
    MOVE mv;
#if defined(DEBUG) || defined(PERF_COUNTERS)
    ULONG uLegalMoves = 0;
#endif
    ULONG uQsearchCheckExtension = 0;

    ASSERT(InCheck(pos, pos->uToMove));
    GenerateMoves(ctx, NULLMOVE, GENERATE_ESCAPES);
    uMoveCount = MOVE_COUNT(ctx, ctx->uPly);
    if (uMoveCount > 0)
    {
        // Consider extending the number of qsearch check-generating
        // plies for our opponent if this looks good -- we have not
        // yet been able to stand pat and they might mate us.
        if ((pf->uQsearchDepth < pf->uQsearchCheckDepth) &&
            (pf->uQsearchDepth < g_uIterateDepth / 4) &&
            (pf->fCouldStandPat[pos->uToMove] == FALSE) &&
            (CountKingSafetyDefects(pos, pos->uToMove) > 4))
        {
            if ((uMoveCount == 1) ||
              (NUM_KING_MOVES(ctx, ctx->uPly) == 0) ||
              (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1))
            {
                uQsearchCheckExtension = 2;
                INC(ctx->sCounters.extension.uQExtend);
            }
            ctx->sPlyInfo[ctx->uPly].iExtensionAmount = uQsearchCheckExtension;
        }
    }

    for (x = ctx->sMoveStack.uBegin[ctx->uPly];
         x < ctx->sMoveStack.uEnd[ctx->uPly];
         x++)
    {
        SelectBestNoHistory(ctx, x);
        mv = ctx->sMoveStack.mvf[x].mv;
        mv.bvFlags |= WouldGiveCheck(ctx, mv);
#ifdef DEBUG
        ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED));
        ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
#endif

        // Note: no selectivity at in-check nodes; search every reply.
        // IDEA: prune if the side in check could have stood pat before.
        if (MakeMove(ctx, mv))
        {
#if defined(DEBUG) || defined(PERF_COUNTERS)
            uLegalMoves++;
#endif
            pf->uQsearchNodes++;
            pf->uQsearchDepth++;
            ASSERT(uQsearchCheckExtension < 3);
            pf->uQsearchCheckDepth += uQsearchCheckExtension;
            ASSERT(pf->uQsearchDepth > 0);
            iScore = -QSearch(ctx,
                              -iBeta,
                              -iAlpha);
            pf->uQsearchCheckDepth -= uQsearchCheckExtension;
            pf->uQsearchDepth--;
            UnmakeMove(ctx, mv);
            if (WE_SHOULD_STOP_SEARCHING)
            {
                iBestScore = iScore;
                goto end;
            }

            if (iScore > iBestScore)
            {
                iBestScore = iScore;
                ctx->sPlyInfo[ctx->uPly].mvBest = mv;
                if (iScore > iAlpha)
                {
                    if (iScore >= iBeta)
                    {
                        KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
                        ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
                        goto end;
                    }
                    else
                    {
                        UpdatePV(ctx, mv);
                        StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly);
                        iAlpha = iScore;
                    }
                }
            }
        }
    }
    ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));

 end:
    ASSERT((uLegalMoves > 0) || (iBestScore <= -NMATE));
    ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
    return(iBestScore);
}


// 2026-09-08: was one flat FUTILITY_BASE_MARGIN (150) regardless of
// which Eval() exit tier produced iEval/rgiPositional this call.
// CALIBRATE_QSEARCH_FUTILITY data (1500 real-game positions,
// tests/twic_sample.ep_, sd 6) showed the three tiers need very
// different margins to reach a similar surprise rate: full-eval
// source was still failing 1.65-6.4% of diagnosed rejects even
// hundreds of centipawns short of the bar, regular-lazy was already
// close to safe (1.26% down to 0.43%), super-lazy was only risky very
// close to the bar (7.96% at distance 0-25, 0.54% by 400+). Indexed
// by ctx->uLastPositionalSource (set inside Eval() -- see
// EVAL_POSITIONAL_SOURCE_* in chess.h). Provisional, derived from one
// run at sd 6; re-derive with `calibrate qsearchfutility` if search
// behavior affecting typical qsearch iEval/iFutility gaps changes.
static const SCORE FUTILITY_BASE_MARGIN_BY_SOURCE[EVAL_POSITIONAL_SOURCE_COUNT] =
{
    FUTILITY_BASE_MARGIN_FULL,      // EVAL_POSITIONAL_SOURCE_FULL
    FUTILITY_BASE_MARGIN_LAZY,      // EVAL_POSITIONAL_SOURCE_LAZY
    FUTILITY_BASE_MARGIN_SUPERLAZY, // EVAL_POSITIONAL_SOURCE_SUPERLAZY
};


/**

Routine description:

    The QSearch (Quiescence Search) is a selective search called when
    there is no remaining depth in Search.  Its job is to search only
    moves that stabilize the position -- once it is quiescence (quiet)
    we will run a static evaluation on it and return the score.

    TODO: experiment with probing and storing in the hash table here.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx : the searcher context
    SCORE iAlpha : lowerbound of search window
    SCORE iBeta : upperbound of search window

Return value:

    SCORE : a score

**/
SCORE FASTCALL
QSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
        IN SCORE iAlpha,
        IN SCORE iBeta)
{
    POSITION *pos = &ctx->sPosition;
    CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
    PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
    MOVE mvLast = (pi-1)->mv;
    MOVE mv;
    SCORE iBestScore;
    SCORE iScore;
    SCORE iEval;
    SCORE iFutility;
    SCORE rgiPositional[2];
    ULONG x;
#ifdef PERF_COUNTERS
    ULONG uLegalMoves;
#endif
    FLAG fIncludeChecks;
    FLAG fOrigStandPat = ctx->sSearchFlags.fCouldStandPat[pos->uToMove];
    static ULONG _WhatToGen[] =
    {
        GENERATE_CAPTURES_PROMS,
        GENERATE_CAPTURES_PROMS_CHECKS
    };

#ifdef DEBUG
    ASSERT(IS_VALID_SCORE(iAlpha));
    ASSERT(IS_VALID_SCORE(iBeta));
    ASSERT(iAlpha < iBeta);
    ASSERT(ctx->uPly > 0);
    ASSERT(TRUE == pi->fInQsearch);
    memcpy(&pi->sPosition, pos, sizeof(POSITION));
#endif

    INC(ctx->sCounters.tree.u64QNodeCount);
    pi->iExtensionAmount = 0;
    if (TRUE == CommonSearchInit(ctx,
                                 &iAlpha,
                                 &iBeta,
                                 &iBestScore))
    {
        goto end;
    }
    DTEnterNode(ctx, 0, TRUE, iAlpha, iBeta);

    // Probe interior node recognizers; do not allow probes into ondisk
    // EGTB files since we are in qsearch.
    switch(RecognLookup(ctx, &iScore, FALSE))
    {
        case UNRECOGNIZED:
            break;
        case RECOGN_EXACT:
        case RECOGN_EGTB:
            if ((iAlpha < iScore) && (iScore < iBeta))
            {
                UpdatePV(ctx, RECOGNMOVE);
            }
            iBestScore = iScore;
            goto end;
        case RECOGN_LOWER:
            if (iScore >= iBeta)
            {
                iBestScore = iScore;
                goto end;
            }
            break;
        case RECOGN_UPPER:
            if (iScore <= iAlpha)
            {
                iBestScore = iScore;
                goto end;
            }
            break;
#ifdef DEBUG
        default:
            ASSERT(FALSE);
#endif
    }

    // If the side is in check, don't let him stand pat.  Search every
    // reply to check and return a MATE score if applicable.  If the
    // side had a chance to stand pat above then the MATE score will
    // be disregarded there since it's not forced.
    if (IS_CHECKING_MOVE(mvLast))
    {
        ASSERT(InCheck(pos, pos->uToMove));
        iBestScore = QSearchFromCheckNoStandPat(ctx, iAlpha, iBeta);
        goto end;
    }
    ASSERT(!InCheck(pos, pos->uToMove));

    iEval = iBestScore = Eval(ctx, iAlpha, iBeta, &rgiPositional);

    // If that Eval (above) was full (i.e. not lazy) it may have set
    // en prise and trapped piece indicators.  Likewise, other nodes
    // at this depth may have set en prise piece hints.  If these are
    // set and valid, it means this is not a "quiet" position -- don't
    // let this side stand pat, force them to play a move and recurse.
    // This is deliberately independent of fCouldStandPat: whether an
    // ancestor node in this qsearch line had a moment of safety says
    // nothing about whether *this* node's material danger is real --
    // a hanging piece doesn't stop hanging because the position was
    // quiet three plies ago. fCouldStandPat's job is different (see
    // its other uses: deciding whether a *whole line* looks forcing
    // enough to justify extra qsearch depth/breadth), not gating
    // per-node stand-pat correctness.
    if (0 != ValueOfMaterialInTroubleDespiteMove(ctx, pos->uToMove))
    {
        iBestScore = iAlpha;
    }
    else
    {
        ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE;
        if (iBestScore > iAlpha)
        {
            iAlpha = iBestScore;
            ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0);
            ASSERT(pi->mvBest.uMove == 0);
            if (iBestScore >= iBeta)
            {
                goto end;
            }
        }
    }

    // He did not choose to stand pat here or we did not allow it.  We
    // will be generating moves and searching recursively.  Compute a
    // futility score: any move less than this will not be searched
    // because it will just cause a lazy eval answer; is has no shot
    // to bring the score close enough to alpha to even consider.
    //
    // iEval + move_value + margin < alpha
    //         move_value          < alpha - margin - iEval
    iFutility = 0;
    if (iAlpha < +NMATE)
    {
#ifdef CALIBRATE_QSEARCH_FUTILITY
        if (TRUE == ctx->fDiagUnprunedSubtree)
        {
            // We're inside a diagnostic "what if this rejected move
            // had been searched anyway" re-search (see
            // _QFutDiagnoseReject) -- force every gate in this
            // function wide open so the diagnostic subtree isn't
            // contaminated by the same pruning it exists to measure.
            iFutility = -NMATE;
        }
        else
#endif
#ifdef DIAG_NO_QSEARCH_FUTILITY
        // Diagnostic-only (never defined in a normal build): forces
        // _ShouldWeConsiderThisMove's gates wide open so every
        // capture/checking-move margin question in this file passes
        // trivially, to measure the node-count/time cost of qsearch
        // futility pruning as a whole -- not for shipping, just for
        // sizing how expensive a "fully unpruned diagnostic subtree"
        // would be for the qsearch-futility calibration harness.
        iFutility = -NMATE;
#else
        ASSERT(ctx->uLastPositionalSource < EVAL_POSITIONAL_SOURCE_COUNT);
        iFutility = iAlpha -
            (FUTILITY_BASE_MARGIN_BY_SOURCE[ctx->uLastPositionalSource] +
             rgiPositional[pos->uToMove]) - iEval;
        iFutility = MAX0(iFutility);
#endif
    }

    // We know we are not in check.  If we are early in the qsearch,
    // and the other side has not yet been able to stand pat yet, and
    // we have material OR we have hanging pieces, generate checks
    // here too.  Checks are a "good way" to escape from "trouble".
    fIncludeChecks = (
        (pf->uQsearchDepth < pf->uQsearchCheckDepth) &&
        (
            (
                (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) &&
                (pos->uNonPawnMaterial[pos->uToMove] > (VALUE_KING + VALUE_BISHOP))
            )
            ||
            (FALSE == ctx->sSearchFlags.fCouldStandPat[pos->uToMove])
        )
    );
    GenerateMoves(ctx, NULLMOVE, _WhatToGen[fIncludeChecks]);

#ifdef PERF_COUNTERS
    uLegalMoves = 0;
#endif
    for (x = ctx->sMoveStack.uBegin[ctx->uPly];
         x < ctx->sMoveStack.uEnd[ctx->uPly];
         x++)
    {
        SelectBestNoHistory(ctx, x);
        if (ctx->sMoveStack.mvf[x].iValue <= 0)
        {
            // We are only intersted in winning/even captures/promotions
            // and (if fIncludeChecks is TRUE) some checking moves too.
            // If we see a move whose value is zero, the rest of the moves
            // in this ply can be tossed.
            ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE | VERIFY_AFTER));
            goto end;
        }
        mv = ctx->sMoveStack.mvf[x].mv;
#ifdef DEBUG
        ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED));
        ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
#endif

        if (FALSE == _ShouldWeConsiderThisMove(ctx,
                                               x,
                                               iFutility,
                                               fIncludeChecks
#ifdef CALIBRATE_QSEARCH_FUTILITY
                                               , iAlpha
                                               , iBeta
                                               , rgiPositional[pos->uToMove]
                                               , ctx->uLastPositionalSource
#endif
                                               ))
        {
            continue;
        }

        // If fIncludeChecks is FALSE then we still need to see if
        // this move is going to check the opponent; GenerateMoves
        // didn't do it for us to save time in the event of a fail
        // high.
        if (FALSE == fIncludeChecks)
        {
            mv.bvFlags |= WouldGiveCheck(ctx, mv);
        }

        if (MakeMove(ctx, mv))
        {
#ifdef PERF_COUNTERS
            uLegalMoves++;
#endif
            pf->uQsearchNodes++;
            pf->uQsearchDepth++;
            ASSERT(pf->uQsearchDepth > 0);
            iScore = -QSearch(ctx,
                              -iBeta,
                              -iAlpha);
            pf->uQsearchDepth--;
            UnmakeMove(ctx, mv);
            if (WE_SHOULD_STOP_SEARCHING) goto end;

            if (iScore > iBestScore)
            {
                iBestScore = iScore;
                pi->mvBest = mv;

                if (iScore > iAlpha)
                {
                    if (iScore >= iBeta)
                    {
                        // A fail-high capturing a non-pawn piece is
                        // search-proven evidence that piece was en
                        // prise -- victim belongs to the mover at
                        // ctx->uPly - 1, not here (see the same
                        // reasoning in the main Search() fail-high
                        // branch).  Skip near mate.
                        if (mv.pCaptured && !IS_PAWN(mv.pCaptured) &&
                            (iBeta < +NMATE))
                        {
                            ASSERT(ctx->uPly > 0);
                            RecordEnprisePieceAtPly(ctx, ctx->uPly - 1,
                                                    mv.cTo);
                        }
                        KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
                        ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
                        goto end;
                    }
                    else
                    {
                        UpdatePV(ctx, mv);
                        StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly);
                        iAlpha = iScore;

                        // Readjust futility margin here; it can be wider now.
                        if (iAlpha < +NMATE)
                        {
                            ASSERT(ctx->uLastPositionalSource <
                                   EVAL_POSITIONAL_SOURCE_COUNT);
                            iFutility = (iAlpha -
                                         (FUTILITY_BASE_MARGIN_BY_SOURCE[
                                              ctx->uLastPositionalSource] +
                                          rgiPositional[pos->uToMove]) -
                                         iEval);
                            iFutility = MAX0(iFutility);
                        }
                    }
                }
            }
        }
    }
    ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));

 end:
    ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = fOrigStandPat;
    ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
    ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
    DTLeaveNode(ctx, TRUE, iBestScore, pi->mvBest);

    // Note: iBestScore can be +INFINITY or -INFINITY here even in the
    // absence of a legitimate mate detected if we disallowed stand
    // pat due to perceived danger early on, when the a..b window had
    // an extreme bound.  This is "legitimate" but weird.
    return(iBestScore);
}