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;
                        ASSERT(TRUE == pi->fMovesRescoredByIID);
                    }
                }
#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 >= 3)) &&
            (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);

            // Cap how many extension plies this line may spend in total
            // (root to here) so that a chain of checks/threats/etc. can't
            // stall uDepth's descent indefinitely and burn the entire
            // MAX_PLY_PER_SEARCH ply budget on one forcing sequence.
            if (iExtend > 0)
            {
                iExtend = MIN(iExtend,
                              MAX(MAX_EXTEND_PER_LINE - pf->iCumulativeExtend, 0));
            }

            // Decide how much (if any) to reduce this move's depth --
            // graded LMR.
            {
                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 =
                    (mv.cFrom != FindEnprisePiece(ctx, pos->uToMove)) &&
                    ((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

**/
#define QSEARCH_CONSIDER_MARGIN (120)

static FLAG INLINE
_ShouldWeConsiderThisMove(IN SEARCHER_THREAD_CONTEXT *ctx,
                          IN ULONG uMoveNum,
                          IN SCORE iFutility,
                          IN FLAG fGeneratedChecks)
{
    MOVE mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv;
    MOVE mv = ctx->sMoveStack.mvf[uMoveNum].mv;
    ULONG uColor;
    SCORE i;

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

        i = ctx->sMoveStack.mvf[uMoveNum].iValue;
        if (i >= SORT_THESE_FIRST)
        {
            i &= STRIP_OFF_FLAGS;
            ASSERT(i >= 0);
            i -= 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.
                i = MAXU(i, PIECE_VALUE(mv.pCaptured));

                // Also try hard not to prune recaps, the bad trade
                // penalty can make them look "futile" sometimes.
                if ((PIECE_VALUE(mv.pCaptured) ==
                     PIECE_VALUE(mvLast.pCaptured)) &&
                    (i + 200 + QSEARCH_CONSIDER_MARGIN > iFutility))
                {
                    return(TRUE);
                }
            }

            // Otherwise, even if a move is even/winning, make sure it
            // brings the score up to at least somewhere near alpha.
            if (i + QSEARCH_CONSIDER_MARGIN > 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.
        if (IS_CHECKING_MOVE(mv) && (TRUE == fGeneratedChecks))
        {
            return(iFutility < +VALUE_ROOK);
        }
    }
    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);
        }
        return(GetCheckSee(ctx, mv, uMoveNum) >= 0);
    }
    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) > 2))
        {
            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);
}


/**

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 iPositional;
    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, &iPositional);

    // 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
    {
        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;
            }
        }
        ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE;
    }

    // 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)
    {
        iFutility = iAlpha - (FUTILITY_BASE_MARGIN + iPositional) - iEval;
        iFutility = MAX0(iFutility);
    }

    // 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))
        {
            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)
                        {
                            iFutility = (iAlpha -
                                         (FUTILITY_BASE_MARGIN +
                                          iPositional) -
                                         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);
}