src/search.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     search.c
   8
   9 Abstract:
  10
  11     Recursive chess tree searching.  See also split.c.
  12
  13     "A type 1 node is also called a PV node.  The root of the tree is
  14     a type-1 node, and the *first* successor of a type-1 node is a
  15     type-1 node also.  A type-1 node must have all branches examined,
  16     but it is unique in that we don't know anything about alpha and
  17     beta yet, because we haven't searched the first move to establish
  18     them.
  19
  20     A type 2 node is either (a) a successor of any type-3 node, or,
  21     (b) it's any successor (other than the first) of a type-1 node.
  22     With perfect move ordering, the first branch at a type-2 node will
  23     "refute" the move made at the previous ply via the alpha/beta
  24     algorithm.  This node requires good move ordering, because you
  25     have to find a move good enough that your opponent would not play
  26     the move he chose that led to this position.  If you try a poor
  27     move first, it won't produce a cutoff, and you have to search
  28     another move (or more) until you find the "good" move that would
  29     make him not play his move.
  30
  31     A type-3 node follows a type-2 node.  Here, you have to try every
  32     move at your disposal.  Since your opponent (at the previous ply)
  33     has played a "strong" move (supposedly the "best" move) you are
  34     going to have to try every move you have in an effort to refute
  35     this move.  None will do so (unless your opponent tried some poor
  36     move first due to incorrect move ordering).  Here, move ordering
  37     is not worth the trouble, since the ordering won't let you avoid
  38     searching some moves.  Of course, with the transposition /
  39     refutation table, ordering might help you get more "hits" if your
  40     table is not large enough...
  41
  42     As you can see, at type-1 nodes you have to do good move ordering
  43     to choose that "1" move (or to choose that one out of a very few)
  44     that is good enough to cause a cutoff, while avoiding choosing
  45     those that are no good.  At a type-1 node, the same thing applies.
  46     If you don't pick the best move first (take the moves at the root
  47     for example) you will search an inferior move, establish alpha or
  48     beta incorrectly, and thereby increase the size of the total tree
  49     by a *substantial* amount.
  50
  51     By the way, some authors call type-1 nodes "PV" nodes, type-2
  52     nodes "CUT" nodes, and type-3 nodes "ALL" nodes.  These make it
  53     easier to read, but, unfortunately, I "cut my teeth" on the
  54     Knuth/Moore paper and think in terms of type 1,2,3."
  55
  56                                                  --Bob Hyatt, r.g.c.c
  57
  58 Author:
  59
  60     Scott Gasch ([email protected]) 21 May 2004
  61
  62 Revision History:
  63
  64     $Id: search.c 345 2007-12-02 22:56:42Z scott $
  65
  66 **/
  67
  68 #include "chess.h"
  69
  70 extern ULONG g_uIterateDepth;
  71 extern FLAG g_fCanSplit[MAX_PLY_PER_SEARCH];
  72
  73 #define TRY_HASH_MOVE         (0)
  74 #define GENERATE_MOVES        (1)
  75 #define PREPARE_TO_TRY_MOVES  (2)
  76 #define TRY_GENERATED_MOVES   (3)
  77
  78 #ifdef DEBUG
  79 #define VERIFY_HASH_HIT                                \
  80     ASSERT(IS_VALID_SCORE(iScore));                    \
  81     ASSERT(((ULONG)pHash->uDepth << 4) >= uDepth);     \
  82     switch (pHash->bvFlags & HASH_FLAG_VALID_BOUNDS)   \
  83     {                                                  \
  84         case HASH_FLAG_LOWER:                          \
  85             ASSERT(iScore >= iBeta);                   \
  86             ASSERT(iScore > -NMATE);                   \
  87             ASSERT(iScore <= +NMATE);                  \
  88             break;                                     \
  89         case HASH_FLAG_UPPER:                          \
  90             ASSERT(iScore <= iAlpha);                  \
  91             ASSERT(iScore < +NMATE);                   \
  92             ASSERT(iScore >= -NMATE);                  \
  93             break;                                     \
  94         case HASH_FLAG_EXACT:                          \
  95             ASSERT((-NMATE <= iScore) &&               \
  96                    (iScore <= +NMATE));                \
  97             break;                                     \
  98         default:                                       \
  99             ASSERT(FALSE);                             \
 100     }
 101 #else
 102 #define VERIFY_HASH_HIT
 103 #endif
 104
 105 /**
 106
 107 Routine description:
 108
 109     This is the full-width portion of the main chess tree search.  In
 110     general, its job is to ask the move generator to make a list of
 111     all the moves possible at the board position in ctx, to make each
 112     move in turn, and to search each resulting position recursively.
 113
 114 Parameters:
 115
 116     SEARCHER_THREAD_CONTEXT *ctx : the context to search in
 117     SCORE iAlpha : the lower bound of the interesting score window
 118     SCORE iBeta : the upper bound of the interesting score window
 119     ULONG uDepth : the depth remaining before QSearch is invoked
 120
 121 Return value:
 122
 123     SCORE : a score
 124
 125     Also affects the transposition table, searcher context, and just
 126     about every other large data structure in the engine...
 127
 128 **/
 129 SCORE FASTCALL
 130 Search(IN SEARCHER_THREAD_CONTEXT *ctx,
 131        IN SCORE iAlpha,
 132        IN SCORE iBeta,
 133        IN ULONG uDepth)
 134 {
 135     POSITION *pos = &ctx->sPosition;
 136     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
 137     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
 138     MOVE mvLast = (pi-1)->mv;
 139     SCORE iBestScore = -INFINITY;
 140     SCORE iInitialAlpha;
 141     SCORE iRoughEval;
 142     MOVE mv, mvBest, mvHash;
 143     ULONG x = 0;
 144     SCORE iScore;
 145     INT iOrigExtend = 0;
 146     INT iExtend;
 147     ULONG uNextDepth;
 148     ULONG uLegalMoves = 0;
 149     HASH_ENTRY *pHash;
 150     FLAG fThreat;
 151     FLAG fSkipNull;
 152     FLAG fIsDraw;
 153     ULONG uStage = TRY_HASH_MOVE;
 154     ULONG u;
 155     ULONG uFutilityMargin = 0;
 156 #ifdef DEBUG
 157     ASSERT(IS_VALID_SCORE(iAlpha));
 158     ASSERT(IS_VALID_SCORE(iBeta));
 159     ASSERT(iAlpha < iBeta);
 160     ASSERT(ctx->uPly > 0);
 161     ASSERT((mvLast.uMove != 0) || (pf->fAvoidNullmove == TRUE));
 162     ASSERT(IS_VALID_FLAG(pf->fAvoidNullmove));
 163     ASSERT(IS_VALID_FLAG(pf->fVerifyNullmove));
 164     memcpy(&pi->sPosition, pos, sizeof(POSITION));
 165 #endif
 166
 167     // Jump directly to Qsearch if remaining depth is low enough.
 168     // This is the only place Qsearch is entered.
 169     if (uDepth < ONE_PLY)
 170     {
 171         pf->fCouldStandPat[BLACK] = pf->fCouldStandPat[WHITE] = FALSE;
 172         pf->uQsearchNodes = pf->uQsearchDepth = 0;
 173         pf->uQsearchCheckDepth = QPLIES_OF_NON_CAPTURE_CHECKS;
 174         pi->fInQsearch = TRUE;
 175         iBestScore = QSearch(ctx, iAlpha, iBeta);
 176         ASSERT(pf->uQsearchNodes < 20000);
 177         ASSERT(pf->uQsearchDepth == 0);
 178         goto end;
 179     }
 180     pi->fInQsearch = FALSE;
 181
 182     // Common initialization code (which may cause a cutoff or change the
 183     // bounds or decide that we need to stop searching now).
 184     if (TRUE == CommonSearchInit(ctx,
 185                                  &iAlpha,
 186                                  &iBeta,
 187                                  &iBestScore))
 188     {
 189         goto end;
 190     }
 191     DTEnterNode(ctx, uDepth, FALSE, iAlpha, iBeta);
 192     iInitialAlpha = iAlpha;
 193     ASSERT((IS_CHECKING_MOVE(mvLast) && (TRUE == pi->fInCheck)) ||
 194            (!IS_CHECKING_MOVE(mvLast) && (FALSE == pi->fInCheck)));
 195
 196     // Prepare next depth for nullmove and hashtable lookup
 197     uNextDepth = uDepth - SelectNullmoveRFactor(ctx, uDepth) - ONE_PLY;
 198     if (uNextDepth > MAX_DEPTH_PER_SEARCH) uNextDepth = 0;
 199
 200     // Check the transposition table.  This may give us a cutoff
 201     // without doing any work if we have previously stored the score
 202     // of this search in the hash.  It also may set mvHash even if it
 203     // can't give us a cutoff.  It also may set fSkipNull (see below)
 204     // based on uNextDepth to inform us that a nullmove search is
 205     // unlikely to succeed here.
 206     mvHash.uMove = 0;
 207     pHash = HashLookup(ctx,
 208                        uDepth,
 209                        uNextDepth,
 210                        iAlpha,
 211                        iBeta,
 212                        &fThreat,
 213                        &fSkipNull,
 214                        &mvHash,
 215                        &iScore);
 216     if (NULL != pHash)
 217     {
 218         VERIFY_HASH_HIT;
 219         u = pHash->bvFlags & HASH_FLAG_VALID_BOUNDS;
 220         if (0 != mvHash.uMove)
 221         {
 222             // This is an idea posted by Dieter Brusser on CCC:  If we
 223             // get a hash hit that leads to a draw then only accept it
 224             // if it has a score of zero, allows us to fail high when
 225             // a draw would also have allowed a fail high, or allows a
 226             // fail low when a draw would also have allowed a fail
 227             // low.
 228             VERIFY(MakeMove(ctx, mvHash));
 229             fIsDraw = IsDraw(ctx);
 230             UnmakeMove(ctx, mvHash);
 231             if ((FALSE == fIsDraw) || (iScore == 0) ||
 232                ((u == HASH_FLAG_LOWER) && (iScore >= iBeta) && (0 >= iBeta)) ||
 233                ((u == HASH_FLAG_UPPER) && (iScore <= iAlpha) && (0 <= iAlpha)))
 234             {
 235                 if ((iAlpha < iScore) && (iScore < iBeta))
 236                 {
 237                     UpdatePV(ctx, HASHMOVE);
 238                 }
 239                 iBestScore = iScore;
 240                 goto end;
 241             }
 242         }
 243         else
 244         {
 245             // The hash move is empty.  Either this is an upper bound
 246             // in which case we have no best move since the node that
 247             // generated it was a fail low -or- this is a lower bound
 248             // recorded after a null move search.  In the latter case
 249             // we only accept the cutoff if we are considering null
 250             // moves at this node too.
 251             ASSERT(u != HASH_FLAG_EXACT);
 252             if ((HASH_FLAG_UPPER == u) || (FALSE == pf->fAvoidNullmove))
 253             {
 254                 ASSERT(((u == HASH_FLAG_UPPER) && (iScore <= iAlpha)) ||
 255                        ((u == HASH_FLAG_LOWER) && (iScore >= iBeta)));
 256                 iBestScore = iScore;
 257                 goto end;
 258             }
 259         }
 260     }
 261
 262     // Probe interior node recognizers; allow probes of ondisk EGTB files
 263     // if it looks like we can get hit.
 264     switch(RecognLookup(ctx, &iScore, ctx->uPly <= (g_uIterateDepth / 2)))
 265     {
 266         case UNRECOGNIZED:
 267             break;
 268         case RECOGN_EXACT:
 269         case RECOGN_EGTB:
 270             if ((iAlpha < iScore) && (iScore < iBeta))
 271             {
 272                 UpdatePV(ctx, RECOGNMOVE);
 273             }
 274             iBestScore = iScore;
 275             goto end;
 276         case RECOGN_LOWER:
 277             if (iScore >= iBeta)
 278             {
 279                 iBestScore = iScore;
 280                 goto end;
 281             }
 282             break;
 283         case RECOGN_UPPER:
 284             if (iScore <= iAlpha)
 285             {
 286                 iBestScore = iScore;
 287                 goto end;
 288             }
 289             break;
 290 #ifdef DEBUG
 291         default:
 292             ASSERT(FALSE);
 293 #endif
 294     }
 295
 296     // Maybe do nullmove pruning
 297     iRoughEval = GetRoughEvalScore(ctx, iAlpha, iBeta, FALSE);
 298     GENERATE_NO_MOVES;
 299     if (!fSkipNull &&
 300         !fThreat &&
 301         WeShouldTryNullmovePruning(ctx,
 302                                    iAlpha,
 303                                    iBeta,
 304                                    iRoughEval,
 305                                    uNextDepth))
 306     {
 307         if (TryNullmovePruning(ctx,
 308                                &fThreat,
 309                                iAlpha,
 310                                iBeta,
 311                                uNextDepth,
 312                                &iOrigExtend,
 313                                &iScore))
 314         {
 315             if (iScore > iBeta) {
 316                 StoreLowerBound(mvHash, pos, iScore, uDepth, FALSE);
 317             }
 318             iBestScore = iScore; // TODO: try just beta here
 319             goto end;
 320         }
 321     }
 322
 323     // Maybe increment positional extension level b/c of nullmove search
 324     // or hash table results.
 325     if (fThreat)
 326     {
 327         iOrigExtend += THREE_QUARTERS_PLY;
 328         INC(ctx->sCounters.extension.uMateThreat);
 329     }
 330
 331     // Main search loop, try moves under this position.  Before we get
 332     // into the move loop, save the extensions merited by this
 333     // position in the tree (pre-move) and the original search flags.
 334     // Also clear the avoid null bit in the search flags -- we were
 335     // either told to avoid it or not but there is no need to avoid it
 336     // for the rest of the line...
 337     mvBest.uMove = 0;
 338     pf->fAvoidNullmove = FALSE;
 339     do
 340     {
 341         ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 342
 343         // Becase we want to try the hash move before generating any
 344         // moves (in case it fails high and we can avoid the work) we
 345         // have this ugly crazy looking switch statement...
 346         switch(uStage)
 347         {
 348             case TRY_HASH_MOVE:
 349                 uStage++;
 350                 x = 0;
 351                 ASSERT(iBestScore == -INFINITY);
 352                 ASSERT(uLegalMoves == 0);
 353                 if (mvHash.uMove != 0)
 354                 {
 355                     mv = mvHash;
 356                     break;
 357                 }
 358                 // else fall through
 359
 360             case GENERATE_MOVES:
 361                 ASSERT(ctx->uPly > 0);
 362                 ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 363                 x = ctx->sMoveStack.uBegin[ctx->uPly];
 364                 uStage++;
 365                 if (IS_CHECKING_MOVE(mvLast))
 366                 {
 367                     ASSERT(InCheck(pos, pos->uToMove));
 368                     GenerateMoves(ctx, mvHash, GENERATE_ESCAPES);
 369                     if (MOVE_COUNT(ctx, ctx->uPly))
 370                     {
 371                         if (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1)
 372                         {
 373                             iOrigExtend += QUARTER_PLY;
 374                             INC(ctx->sCounters.extension.uMultiCheck);
 375                         } else if (NUM_KING_MOVES(ctx, ctx->uPly) == 0) {
 376                             iOrigExtend += QUARTER_PLY;
 377                             INC(ctx->sCounters.extension.uNoLegalKingMoves);
 378                         }
 379                     }
 380                 }
 381                 else
 382                 {
 383                     ASSERT(!InCheck(pos, pos->uToMove));
 384                     GenerateMoves(ctx, mvHash, GENERATE_ALL_MOVES);
 385                 }
 386                 // fall through
 387
 388             case PREPARE_TO_TRY_MOVES:
 389                 ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]);
 390                 ASSERT((uLegalMoves == 0) ||
 391                        ((uLegalMoves == 1) && (mvHash.uMove)));
 392 #ifdef DO_IID
 393                 if (MOVE_COUNT(ctx, ctx->uPly))
 394                 {
 395                     SelectBestNoHistory(ctx, x);
 396
 397                     // EXPERIMENT: If we got no best move from the
 398                     // hash table and the best move we got from the
 399                     // generator looks crappy (i.e. is not a winning
 400                     // or even capture/promotion) then rescore the
 401                     // moves we generated at this ply using a
 402                     // shallower search.  "Internal Iterative
 403                     // Deepening" or something like it.
 404                     if ((iAlpha + 1 != iBeta) &&
 405                         (mvHash.uMove == 0) &&
 406                         (ctx->sMoveStack.mvf[x].iValue < SORT_THESE_FIRST) &&
 407                         (uDepth >= FOUR_PLY))
 408                     {
 409                         ASSERT(uDepth >= (IID_R_FACTOR + ONE_PLY));
 410                         ASSERT(ctx->sSearchFlags.fAvoidNullmove == FALSE);
 411                         ctx->sSearchFlags.fAvoidNullmove = TRUE;
 412                         RescoreMovesViaSearch(ctx, uDepth, iAlpha, iBeta);
 413                         ctx->sSearchFlags.fAvoidNullmove = FALSE;
 414                     }
 415                 }
 416 #endif
 417                 // This is very similar to Ernst Heinz's "extended
 418                 // futility pruning" except that it uses the added
 419                 // dynamic criteria of "ValueOfMaterialInTrouble"
 420                 // condition as a safety net.  Note: before we actually
 421                 // prune away moves we will also make sure there is
 422                 // no per-move extension.
 423                 ASSERT(!uFutilityMargin);
 424                 if ((iRoughEval + VALUE_ROOK <= iAlpha) &&
 425                     (uDepth <= TWO_PLY) &&
 426                     (ctx->uPly >= 2) &&
 427                     (iOrigExtend == 0) &&
 428                     (ctx->sPlyInfo[ctx->uPly - 2].iExtensionAmount <= 0) &&
 429                     (ValueOfMaterialInTroubleDespiteMove(pos, pos->uToMove)))
 430                 {
 431                     uFutilityMargin = (iAlpha - iRoughEval) / 2;
 432                     ASSERT(uFutilityMargin);
 433                 }
 434                 uStage++;
 435                 ASSERT(x == ctx->sMoveStack.uBegin[ctx->uPly]);
 436                 // fall through
 437
 438             case TRY_GENERATED_MOVES:
 439                 if (x < ctx->sMoveStack.uEnd[ctx->uPly])
 440                 {
 441                     ASSERT(x >= ctx->sMoveStack.uBegin[ctx->uPly]);
 442                     if (uLegalMoves < SEARCH_SORT_LIMIT(ctx->uPly))
 443                     {
 444                         SelectBestWithHistory(ctx, x);
 445                     }
 446                     mv = ctx->sMoveStack.mvf[x].mv;
 447 #ifdef DEBUG
 448                     ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags &
 449                                  MVF_MOVE_SEARCHED));
 450                     ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
 451 #endif
 452                     mv.bvFlags |= WouldGiveCheck(ctx, mv);
 453
 454                     // Note: x is the index of the NEXT move to be
 455                     // considered, this move's index is (x-1).
 456                     x++;
 457                     break;
 458                 }
 459                 // else fall through
 460
 461             default:
 462                 goto no_more_moves;
 463         }
 464         ASSERT(mv.uMove);
 465         ASSERT(SanityCheckMove(pos, mv));
 466
 467 #ifdef MP
 468         // Can we search the remaining moves in parallel?
 469         ASSERT((uDepth / ONE_PLY - 1) >= 0);
 470         ASSERT((uDepth / ONE_PLY - 1) < MAX_PLY_PER_SEARCH);
 471         if (((uLegalMoves >= 2)) &&
 472             (0 != g_uNumHelpersAvailable) &&
 473             (0 == uFutilityMargin) &&
 474             (TRUE == g_fCanSplit[uDepth / ONE_PLY - 1]) &&
 475             (MOVE_COUNT(ctx, ctx->uPly) > 3))
 476         {
 477             ASSERT(pf->fAvoidNullmove == FALSE);
 478             ASSERT(uStage == TRY_GENERATED_MOVES);
 479             ASSERT(x != 0);
 480             ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 481             ASSERT(iBestScore <= iAlpha);
 482             ctx->sMoveStack.mvf[x-1].bvFlags &= ~MVF_MOVE_SEARCHED;
 483             iScore = StartParallelSearch(ctx,
 484                                          &iAlpha,
 485                                          iBeta,
 486                                          &iBestScore,
 487                                          &mvBest,
 488                                          (x - 1),
 489                                          iOrigExtend,
 490                                          uDepth);
 491             ASSERT(iAlpha < iBeta);
 492             ASSERT((IS_SAME_MOVE(pi->PV[ctx->uPly], mvBest)) ||
 493                    (iScore <= iAlpha) || (iScore >= iBeta));
 494             ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 495 #ifdef DEBUG
 496             VerifyPositionConsistency(pos, FALSE);
 497 #endif
 498             if (IS_VALID_SCORE(iScore))
 499             {
 500                 pi->mvBest = mvBest;
 501                 goto no_more_moves;
 502             }
 503             else
 504             {
 505                 ASSERT(WE_SHOULD_STOP_SEARCHING);
 506                 iBestScore = iScore;
 507                 goto end;
 508             }
 509             ASSERT(FALSE);
 510         }
 511 #endif
 512
 513         if (TRUE == MakeMove(ctx, mv))
 514         {
 515             uLegalMoves++;
 516             ASSERT((IS_CHECKING_MOVE(mv) && InCheck(pos, pos->uToMove)) ||
 517                    (!IS_CHECKING_MOVE(mv) && !InCheck(pos, pos->uToMove)));
 518
 519             // Compute per-move extension (as opposed to per-position
 520             // extensions which are represented by iOrigExtend).
 521             iExtend = iOrigExtend;
 522             ComputeMoveExtension(ctx,
 523                                  iAlpha,
 524                                  iBeta,
 525                                  (x - 1),     // Note: x==0 if doing mvHash
 526                                  iRoughEval,
 527                                  uDepth,
 528                                  &iExtend);
 529
 530             // Decide whether or not to do history pruning
 531             if (TRUE == WeShouldDoHistoryPruning(iRoughEval,
 532                                                  iAlpha,
 533                                                  iBeta,
 534                                                  ctx,
 535                                                  uDepth,
 536                                                  uLegalMoves,
 537                                                  mv,
 538                                                  (x - 1), // Note: x==0 if hash
 539                                                  iExtend))
 540             {
 541                 ASSERT(iExtend == 0);
 542                 iExtend = -ONE_PLY;
 543                 pi->iExtensionAmount = -ONE_PLY;
 544             }
 545
 546             // Maybe even "futility prune" this move away.
 547             if ((x != 0) &&
 548                 (uLegalMoves > 1) &&
 549                 (uFutilityMargin) &&
 550                 (ComputeMoveScore(ctx, mv, (x - 1)) < uFutilityMargin) &&
 551                 (iExtend <= 0) &&
 552                 (!IS_ESCAPING_CHECK(mv)))
 553             {
 554                 // TODO: test this more carefully
 555                 ASSERT(!IS_CHECKING_MOVE(mv));
 556                 UnmakeMove(ctx, mv);
 557                 ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 558             }
 559             else
 560             {
 561                 // Compute the next search depth for this move/subtree.
 562                 uNextDepth = uDepth - ONE_PLY + iExtend;
 563                 if (uNextDepth >= MAX_DEPTH_PER_SEARCH) uNextDepth = 0;
 564                 ASSERT(pf->fAvoidNullmove == FALSE);
 565                 if (iBestScore == -INFINITY)
 566                 {
 567                     // First move, full a..b window.
 568                     ASSERT(uLegalMoves == 1);
 569                     iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
 570                 }
 571                 else
 572                 {
 573                     // Moves 2..N, try a minimal window search
 574                     iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uNextDepth);
 575                     if ((iAlpha < iScore) && (iScore < iBeta))
 576                     {
 577                         iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
 578                     }
 579                 }
 580
 581                 // Research deeper if history pruning failed
 582                 if ((iExtend < 0) && (iScore >= iBeta))
 583                 {
 584                     uNextDepth += ONE_PLY;
 585                     pi->iExtensionAmount = 0;
 586                     iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
 587                 }
 588                 UnmakeMove(ctx, mv);
 589                 ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 590                 if (WE_SHOULD_STOP_SEARCHING)
 591                 {
 592                     iBestScore = iScore;
 593                     goto end;
 594                 }
 595
 596                 // Check results
 597                 ASSERT(iBestScore <= iAlpha);
 598                 ASSERT(iAlpha < iBeta);
 599                 if (iScore > iBestScore)
 600                 {
 601                     iBestScore = iScore;
 602                     mvBest = mv;
 603                     pi->mvBest = mv;
 604
 605                     if (iScore > iAlpha)
 606                     {
 607                         if (iScore >= iBeta)
 608                         {
 609                             // Update history and killers list and store in
 610                             // the transposition table.
 611                             UpdateDynamicMoveOrdering(ctx,
 612                                                       uDepth,
 613                                                       mv,
 614                                                       iScore,
 615                                                       x);
 616                             StoreLowerBound(mv, pos, iScore, uDepth, fThreat);
 617                             KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
 618                             ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
 619                             goto end;
 620                         }
 621                         else
 622                         {
 623                             // PV move...
 624                             UpdatePV(ctx, mv);
 625                             iAlpha = iScore;
 626                         }
 627                     }
 628                 }
 629             }
 630         }
 631     }
 632     while(1); // foreach move
 633
 634  no_more_moves:
 635     ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
 636
 637     // Detect checkmates and stalemates
 638     if (0 == uLegalMoves)
 639     {
 640         if (pi->fInCheck)
 641         {
 642             ASSERT(IS_CHECKING_MOVE(mvLast));
 643             ASSERT(InCheck(pos, pos->uToMove));
 644             iBestScore = MATED_SCORE(ctx->uPly);
 645             ASSERT(iBestScore <= -NMATE);
 646             goto end;
 647         }
 648         else
 649         {
 650             iBestScore = 0;
 651             if ((iAlpha < iBestScore) && (iBestScore < iBeta))
 652             {
 653                 UpdatePV(ctx, DRAWMOVE);
 654             }
 655             goto end;
 656         }
 657     }
 658
 659     // Not checkmate/stalemate; store the result of this search in the
 660     // hash table.
 661     if (iAlpha != iInitialAlpha)
 662     {
 663         ASSERT(mvBest.uMove != 0);
 664         if (!IS_CAPTURE_OR_PROMOTION(mvBest))
 665         {
 666             UpdateDynamicMoveOrdering(ctx,
 667                                       uDepth,
 668                                       mvBest,
 669                                       iBestScore,
 670                                       0);
 671         }
 672         StoreExactScore(mvBest, pos, iBestScore, uDepth, fThreat, ctx->uPly);
 673     }
 674     else
 675     {
 676         // IDEA: "I am very well aware of the fact, that the scores
 677         // you get back outside of the window, are not trustable at
 678         // all. Still, I have mentioned the case, of all scores being
 679         // losing mate scores, but one is not. This move will be good
 680         // to try first. I have seen this, by investigating multi MB
 681         // large tree dumps, so it is not only there in theory. Often,
 682         // even with fail soft, I of course will also get multiple
 683         // moves with the same score (alpha). But then one can see the
 684         // "best" move as an additional killer move. It was most
 685         // probably the killer move anyway, when this position was
 686         // visited the last time. I cannot see a reason, why trying
 687         // such a move early could hurt. And I do see reductions of
 688         // tree sizes. I don't try upper-bound moves first. I try them
 689         // (more or less) after the good captures, and together with
 690         // the killer moves, but before history moves."
 691         //                                            --Ed Schroder
 692         StoreUpperBound(pos, iBestScore, uDepth, fThreat);
 693     }
 694
 695  end:
 696     ASSERT(IS_VALID_SCORE(iBeta));
 697     ASSERT(IS_VALID_SCORE(iAlpha));
 698     ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
 699     ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 700     DTLeaveNode(ctx, FALSE, iBestScore, mvBest);
 701     return(iBestScore);
 702 }
 703
 704
 705 /**
 706
 707 Routine description:
 708
 709     This routine is called by QSearch, the select part of the
 710     recursive search code.  Its job is to determine if a move
 711     generated is worth searching.
 712
 713 Parameters:
 714
 715     SEARCHER_THREAD_CONTEXT *ctx : searcher context
 716     ULONG uMoveNum : the move number we are considering
 717     SCORE iFutility : the futility line
 718
 719 Return value:
 720
 721     FLAG : TRUE if the move is worth considering,
 722            FALSE if it can be skipped
 723
 724 **/
 725 static FLAG INLINE
 726 _ShouldWeConsiderThisMove(IN SEARCHER_THREAD_CONTEXT *ctx,
 727                           IN ULONG uMoveNum,
 728                           IN SCORE iFutility,
 729                           IN FLAG fGeneratedChecks)
 730 {
 731     MOVE mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv;
 732     MOVE mv = ctx->sMoveStack.mvf[uMoveNum].mv;
 733     ULONG uColor;
 734     SCORE i;
 735
 736     ASSERT(!IS_CHECKING_MOVE(mvLast));
 737     ASSERT(!InCheck(&(ctx->sPosition), ctx->sPosition.uToMove));
 738
 739     if (IS_CAPTURE_OR_PROMOTION(mv))
 740     {
 741         // IDEA: if mvLast was a promotion, try everything here?
 742
 743         // Don't consider promotions to anything but queens unless
 744         // it's a knight and we are going for a knockout.
 745         if ((mv.pPromoted) && (!IS_QUEEN(mv.pPromoted)))
 746         {
 747             if (!IS_KNIGHT(mv.pPromoted) ||
 748                 !IS_CHECKING_MOVE(mv) ||
 749                 (FALSE == fGeneratedChecks))
 750             {
 751                 return(FALSE);
 752             }
 753         }
 754
 755         i = ctx->sMoveStack.mvf[uMoveNum].iValue;
 756         if (i >= SORT_THESE_FIRST)
 757         {
 758             i &= STRIP_OFF_FLAGS;
 759             ASSERT(i >= 0);
 760             if (mv.pCaptured)
 761             {
 762                 // If there are very few pieces left on the board,
 763                 // consider all captures because we could be, for
 764                 // example, taking the guy's last pawn and forcing a
 765                 // draw.  Even though the cap looks futile the draw
 766                 // might save the game...
 767                 uColor = GET_COLOR(mv.pCaptured);
 768                 ASSERT(OPPOSITE_COLORS(ctx->sPosition.uToMove, uColor));
 769                 if ((IS_PAWN(mv.pCaptured) &&
 770                      ctx->sPosition.uPawnCount[uColor] == 1) ||
 771                     (!IS_PAWN(mv.pCaptured) &&
 772                      ctx->sPosition.uNonPawnCount[uColor][0] == 2))
 773                 {
 774                     return(TRUE);
 775                 }
 776
 777                 // Also always consider "dangerous pawn" captures.
 778                 if (IS_PAWN(mv.pMoved) &&
 779                     (((GET_COLOR(mv.pMoved) == WHITE) && RANK7(mv.cTo)) ||
 780                      ((GET_COLOR(mv.pMoved) == BLACK) && RANK2(mv.cTo))))
 781                 {
 782                     return(TRUE);
 783                 }
 784
 785                 // Don't trust the SEE alone for alpha pruning decisions.
 786                 i = MAXU(i, PIECE_VALUE(mv.pCaptured));
 787
 788                 // Also try hard not to prune recaps, the bad trade
 789                 // penalty can make them look "futile" sometimes.
 790                 if ((PIECE_VALUE(mv.pCaptured) ==
 791                      PIECE_VALUE(mvLast.pCaptured)) &&
 792                     (i + 200 > iFutility))
 793                 {
 794                     return(TRUE);
 795                 }
 796             }
 797
 798             // Otherwise, even if a move is even/winning, make sure it
 799             // brings the score up to at least somewhere near alpha.
 800             if (i > iFutility)
 801             {
 802                 return(TRUE);
 803             }
 804         }
 805
 806         // If we get here the move was either a losing capture/prom
 807         // that checked or a "futile" winning capture/prom that may or
 808         // may not check.  Be more willing to play checking captures
 809         // even if they look bad.
 810         if (IS_CHECKING_MOVE(mv) && (TRUE == fGeneratedChecks))
 811         {
 812             return(iFutility < +VALUE_ROOK);
 813         }
 814     }
 815     else
 816     {
 817         // If we get here we have a checking move that does not
 818         // capture anything or promote anything.  We are interested in
 819         // these to some depth.
 820         ASSERT(IS_CHECKING_MOVE(mv));
 821         ASSERT(TRUE == fGeneratedChecks);
 822
 823         // IDEA: don't play obviously losing checks if we are already
 824         // way below alpha.
 825         if (iFutility < +VALUE_BISHOP)
 826         {
 827             return(TRUE);
 828         }
 829         return(SEE(&ctx->sPosition, mv) >= 0);
 830     }
 831     return(FALSE);
 832 }
 833
 834
 835 /**
 836
 837 Routine description:
 838
 839     Side to move is in check and may or may not have had a chance to
 840     stand pat at a qnode above this point.  Search all legal check
 841     evasions and return a mate-in-n score if this is checkmate.
 842     Possibly extend the depth to which we generate checks under this
 843     node.  If there's a stand pat qnode above us the mate-in-n will be
 844     weeded out.
 845
 846 Parameters:
 847
 848     IN SEARCHER_THREAD_CONTEXT *ctx,
 849     IN SCORE iAlpha,
 850     IN SCORE iBeta
 851
 852 Return value:
 853
 854     SCORE
 855
 856 **/
 857 SCORE
 858 QSearchFromCheckNoStandPat(IN SEARCHER_THREAD_CONTEXT *ctx,
 859                            IN SCORE iAlpha,
 860                            IN SCORE iBeta)
 861 {
 862     POSITION *pos = &ctx->sPosition;
 863     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
 864     ULONG x, uMoveCount;
 865     SCORE iBestScore = MATED_SCORE(ctx->uPly);
 866     SCORE iScore;
 867     MOVE mv;
 868     ULONG uLegalMoves = 0;
 869     ULONG uQsearchCheckExtension = 0;
 870
 871     ASSERT(InCheck(pos, pos->uToMove));
 872     GenerateMoves(ctx, NULLMOVE, GENERATE_ESCAPES);
 873     uMoveCount = MOVE_COUNT(ctx, ctx->uPly);
 874     if (uMoveCount > 0)
 875     {
 876         // Consider extending the number of qsearch plies we consider
 877         // non-capture checks at during this line.
 878         if ((pf->fCouldStandPat[pos->uToMove] == FALSE) &&
 879             (pf->uQsearchDepth < g_uIterateDepth / 2) &&
 880             (CountKingSafetyDefects(pos, pos->uToMove) > 1))
 881         {
 882             if (uMoveCount == 1) {
 883                 uQsearchCheckExtension = 2;
 884                 INC(ctx->sCounters.extension.uQExtend);
 885             } else if ((uMoveCount == 2) ||
 886                        (NUM_KING_MOVES(ctx, ctx->uPly) == 0) ||
 887                        (NUM_CHECKING_PIECES(ctx, ctx->uPly) > 1)) {
 888                 uQsearchCheckExtension = 1;
 889                 INC(ctx->sCounters.extension.uQExtend);
 890             }
 891             ctx->sPlyInfo[ctx->uPly].iExtensionAmount = uQsearchCheckExtension;
 892         }
 893     }
 894
 895     for (x = ctx->sMoveStack.uBegin[ctx->uPly];
 896          x < ctx->sMoveStack.uEnd[ctx->uPly];
 897          x++)
 898     {
 899         SelectBestNoHistory(ctx, x);
 900         mv = ctx->sMoveStack.mvf[x].mv;
 901         mv.bvFlags |= WouldGiveCheck(ctx, mv);
 902 #ifdef DEBUG
 903         ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED));
 904         ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
 905 #endif
 906
 907         // Note: no selectivity at in-check nodes; search every reply.
 908         // IDEA: prune if the side in check could have stood pat before.
 909         if (MakeMove(ctx, mv))
 910         {
 911             uLegalMoves++;
 912             pf->uQsearchNodes++;
 913             pf->uQsearchDepth++;
 914             ASSERT(uQsearchCheckExtension < 3);
 915             pf->uQsearchCheckDepth += uQsearchCheckExtension;
 916             ASSERT(pf->uQsearchDepth > 0);
 917             iScore = -QSearch(ctx,
 918                               -iBeta,
 919                               -iAlpha);
 920             pf->uQsearchCheckDepth -= uQsearchCheckExtension;
 921             pf->uQsearchDepth--;
 922             UnmakeMove(ctx, mv);
 923             if (WE_SHOULD_STOP_SEARCHING)
 924             {
 925                 iBestScore = iScore;
 926                 goto end;
 927             }
 928
 929             if (iScore > iBestScore)
 930             {
 931                 iBestScore = iScore;
 932                 ctx->sPlyInfo[ctx->uPly].mvBest = mv;
 933                 if (iScore > iAlpha)
 934                 {
 935                     if (iScore >= iBeta)
 936                     {
 937                         KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
 938                         ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
 939                         goto end;
 940                     }
 941                     else
 942                     {
 943                         UpdatePV(ctx, mv);
 944                         StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly);
 945                         iAlpha = iScore;
 946                     }
 947                 }
 948             }
 949         }
 950     }
 951     ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
 952
 953  end:
 954     ASSERT((uLegalMoves > 0) || (iBestScore <= -NMATE));
 955     ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
 956     return(iBestScore);
 957 }
 958
 959
 960
 961 /**
 962
 963 Routine description:
 964
 965     The QSearch (Quiescence Search) is a selective search called when
 966     there is no remaining depth in Search.  Its job is to search only
 967     moves that stabilize the position -- once it is quiescence (quiet)
 968     we will run a static evaluation on it and return the score.
 969
 970     This branch of the QSearch is called when the side to move is in
 971     danger somehow -- either he has two pieces en prise on the board
 972     or some piece that seems trapped.  We do not allow him an
 973     opportunity to stand pat in this position.
 974
 975 Parameters:
 976
 977     IN SEARCHER_THREAD_CONTEXT *ctx,
 978     IN SCORE iAlpha,
 979     IN SCORE iBeta
 980     IN SCORE iEval
 981
 982 Return value:
 983
 984     SCORE
 985
 986 **/
 987 SCORE
 988 QSearchInDangerNoStandPat(IN SEARCHER_THREAD_CONTEXT *ctx,
 989                           IN SCORE iAlpha,
 990                           IN SCORE iBeta)
 991 {
 992     POSITION *pos = &ctx->sPosition;
 993     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
 994     ULONG x;
 995     FLAG fIncludeChecks;
 996     SCORE iBestScore = iAlpha;
 997     SCORE iScore;
 998     SCORE iFutility;
 999     SCORE iEval = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE);
1000     MOVE mv;
1001     ULONG uLegalMoves = 0;
1002     static ULONG _WhatToGen[] =
1003     {
1004         GENERATE_CAPTURES_PROMS,
1005         GENERATE_CAPTURES_PROMS_CHECKS
1006     };
1007
1008
1009     // Set futility:
1010     //
1011     // iEval + move_value + margin < alpha
1012     //         move_value          < alpha - margin - iEval
1013     iFutility = 0;
1014     if (iAlpha < +NMATE)
1015     {
1016         iFutility = (iAlpha -
1017                      (FUTILITY_BASE_MARGIN + ctx->uPositional) -
1018                      iEval);
1019         iFutility = MAX0(iFutility);
1020     }
1021
1022     // We suspect that the guy on move is in sad shape if we're
1023     // here...  he has more than one piece en prise or he seems to
1024     // have a piece trapped.  Allow him to play checks in order to try
1025     // to save the situation.
1026     ASSERT(!InCheck(pos, pos->uToMove));
1027     fIncludeChecks = (pf->uQsearchDepth < g_uIterateDepth / 3);
1028     GenerateMoves(ctx, NULLMOVE, _WhatToGen[fIncludeChecks]);
1029
1030     for (x = ctx->sMoveStack.uBegin[ctx->uPly];
1031          x < ctx->sMoveStack.uEnd[ctx->uPly];
1032          x++)
1033     {
1034         SelectBestNoHistory(ctx, x);
1035         mv = ctx->sMoveStack.mvf[x].mv;
1036 #ifdef DEBUG
1037         ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED));
1038         ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
1039 #endif
1040
1041         // Prune except when pruning all moves could cause us to return
1042         // -INFINITY (mated) erroneously.
1043         if (iAlpha > -INFINITY)
1044         {
1045             if (ctx->sMoveStack.mvf[x].iValue <= 0)
1046             {
1047                 ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE | VERIFY_AFTER));
1048                 goto end;
1049             }
1050             if (FALSE == _ShouldWeConsiderThisMove(ctx,
1051                                                    x,
1052                                                    iFutility,
1053                                                    TRUE))
1054             {
1055                 continue;
1056             }
1057         }
1058
1059         if (FALSE == fIncludeChecks)
1060         {
1061             mv.bvFlags |= WouldGiveCheck(ctx, mv);
1062         }
1063
1064         if (MakeMove(ctx, mv))
1065         {
1066             uLegalMoves++;
1067             pf->uQsearchNodes++;
1068             pf->uQsearchDepth++;
1069             iScore = -QSearch(ctx,
1070                               -iBeta,
1071                               -iAlpha);
1072             pf->uQsearchDepth--;
1073             UnmakeMove(ctx, mv);
1074
1075             if (iScore > iBestScore)
1076             {
1077                 iBestScore = iScore;
1078                 ctx->sPlyInfo[ctx->uPly].mvBest = mv;
1079                 if (iScore > iAlpha)
1080                 {
1081                     if (iScore >= iBeta)
1082                     {
1083                         KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
1084                         ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
1085                         goto end;
1086                     }
1087                     else
1088                     {
1089                         UpdatePV(ctx, mv);
1090                         StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly);
1091                         iAlpha = iScore;
1092                     }
1093                 }
1094             }
1095             if (WE_SHOULD_STOP_SEARCHING) goto end;
1096         }
1097     }
1098     ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
1099
1100  end:
1101     // If iAlpha is -INFINITY and side on move has no captures,
1102     // promotes or checks then we must make up a "stand pat" score
1103     // here.  We don't want to let him stand pat with iEval because
1104     // the board looks dangerous.  But we likewise don't want to say
1105     // "mated" because he's not.
1106     ASSERT((uLegalMoves > 0) || (iBestScore == iAlpha));
1107     if (iBestScore == -INFINITY)
1108     {
1109         ASSERT(iAlpha == -INFINITY);
1110         iBestScore = iEval - VALUE_QUEEN;
1111     }
1112     ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
1113     return(iBestScore);
1114 }
1115
1116
1117 /**
1118
1119 Routine description:
1120
1121     The QSearch (Quiescence Search) is a selective search called when
1122     there is no remaining depth in Search.  Its job is to search only
1123     moves that stabilize the position -- once it is quiescence (quiet)
1124     we will run a static evaluation on it and return the score.
1125
1126     TODO: experiment with probing and storing in the hash table here.
1127
1128 Parameters:
1129
1130     SEARCHER_THREAD_CONTEXT *ctx : the searcher context
1131     SCORE iAlpha : lowerbound of search window
1132     SCORE iBeta : upperbound of search window
1133
1134 Return value:
1135
1136     SCORE : a score
1137
1138 **/
1139 SCORE FASTCALL
1140 QSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
1141         IN SCORE iAlpha,
1142         IN SCORE iBeta)
1143 {
1144     POSITION *pos = &ctx->sPosition;
1145     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
1146     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
1147     MOVE mvLast = (pi-1)->mv;
1148     MOVE mv;
1149     SCORE iBestScore;
1150     SCORE iScore;
1151     SCORE iEval;
1152     SCORE iFutility;
1153     ULONG x;
1154     ULONG uLegalMoves;
1155     FLAG fIncludeChecks;
1156     FLAG fOrigStandPat = ctx->sSearchFlags.fCouldStandPat[pos->uToMove];
1157     static ULONG _WhatToGen[] =
1158     {
1159         GENERATE_CAPTURES_PROMS,
1160         GENERATE_CAPTURES_PROMS_CHECKS
1161     };
1162
1163 #ifdef DEBUG
1164     ASSERT(IS_VALID_SCORE(iAlpha));
1165     ASSERT(IS_VALID_SCORE(iBeta));
1166     ASSERT(iAlpha < iBeta);
1167     ASSERT(ctx->uPly > 0);
1168     ASSERT(TRUE == pi->fInQsearch);
1169     memcpy(&pi->sPosition, pos, sizeof(POSITION));
1170 #endif
1171
1172     INC(ctx->sCounters.tree.u64QNodeCount);
1173     pi->iExtensionAmount = 0;
1174     if (TRUE == CommonSearchInit(ctx,
1175                                  &iAlpha,
1176                                  &iBeta,
1177                                  &iBestScore))
1178     {
1179         goto end;
1180     }
1181     DTEnterNode(ctx, 0, TRUE, iAlpha, iBeta);
1182
1183     // Probe interior node recognizers; do not allow probes into ondisk
1184     // EGTB files since we are in qsearch.
1185     switch(RecognLookup(ctx, &iScore, FALSE))
1186     {
1187         case UNRECOGNIZED:
1188             break;
1189         case RECOGN_EXACT:
1190         case RECOGN_EGTB:
1191             if ((iAlpha < iScore) && (iScore < iBeta))
1192             {
1193                 UpdatePV(ctx, RECOGNMOVE);
1194             }
1195             iBestScore = iScore;
1196             goto end;
1197         case RECOGN_LOWER:
1198             if (iScore >= iBeta)
1199             {
1200                 iBestScore = iScore;
1201                 goto end;
1202             }
1203             break;
1204         case RECOGN_UPPER:
1205             if (iScore <= iAlpha)
1206             {
1207                 iBestScore = iScore;
1208                 goto end;
1209             }
1210             break;
1211 #ifdef DEBUG
1212         default:
1213             ASSERT(FALSE);
1214 #endif
1215     }
1216
1217     // If the side is in check, don't let him stand pat.  Search every
1218     // reply to check and return a MATE score if applicable.  If the
1219     // side had a chance to stand pat above then the MATE score will
1220     // be disregarded there since it's not forced.
1221     if (IS_CHECKING_MOVE(mvLast))
1222     {
1223         ASSERT(InCheck(pos, pos->uToMove));
1224         iBestScore = QSearchFromCheckNoStandPat(ctx, iAlpha, iBeta);
1225         goto end;
1226     }
1227     ASSERT(!InCheck(pos, pos->uToMove));
1228
1229     // Even if the side is not in check, do not let him stand pat if
1230     // his position looks dangerous (i.e. more than one piece en prise
1231     // or a piece trapped).  Fail low if there's nothing that looks
1232     // good on this line.
1233     if (SideCanStandPat(pos, pos->uToMove) == FALSE)
1234     {
1235         iBestScore = QSearchInDangerNoStandPat(ctx, iAlpha, iBeta);
1236         goto end;
1237     }
1238
1239     // If we get here then side on move is not in check and this
1240     // position looks ok enough to allow him the option to stand pat
1241     // -or- we missed when we probed the dangerhash.  Also remember
1242     // that this side has had the option to stand pat when searching
1243     // below this point.
1244     uLegalMoves = 0;
1245     iEval = iBestScore = Eval(ctx, iAlpha, iBeta);
1246     if (iBestScore > iAlpha)
1247     {
1248         iAlpha = iBestScore;
1249         ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove == 0);
1250         ASSERT(pi->mvBest.uMove == 0);
1251         if (iBestScore >= iBeta)
1252         {
1253             goto end;
1254         }
1255     }
1256     ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = TRUE;
1257
1258     // He did not choose to stand pat here; we will be generating
1259     // moves and searching recursively.  Compute a futility score:
1260     // any move less than this will not be searched because it will
1261     // just cause a lazy eval answer; is has no shot to bring the
1262     // score close enough to alpha to even consider.
1263     //
1264     // iEval + move_value + margin < alpha
1265     //         move_value          < alpha - margin - iEval
1266     iFutility = 0;
1267     if (iAlpha < +NMATE)
1268     {
1269         iFutility = iAlpha - (FUTILITY_BASE_MARGIN + ctx->uPositional) - iEval;
1270         iFutility = MAX0(iFutility);
1271     }
1272
1273     // We know we are not in check.  Generate moves (including checks
1274     // if we are below the threshold and the other side has never been
1275     // allowed to stand pat).  Recurse.
1276     fIncludeChecks = ((pf->uQsearchDepth < pf->uQsearchCheckDepth) &&
1277                       (pf->fCouldStandPat[FLIP(pos->uToMove)] == FALSE) &&
1278                       (pos->uNonPawnMaterial[pos->uToMove] >
1279                        (VALUE_KING + VALUE_BISHOP)));
1280     GenerateMoves(ctx, NULLMOVE, _WhatToGen[fIncludeChecks]);
1281     for (x = ctx->sMoveStack.uBegin[ctx->uPly];
1282          x < ctx->sMoveStack.uEnd[ctx->uPly];
1283          x++)
1284     {
1285         SelectBestNoHistory(ctx, x);
1286         if (ctx->sMoveStack.mvf[x].iValue <= 0)
1287         {
1288             // We are only intersted in winning/even captures/promotions
1289             // and (if fIncludeChecks is TRUE) some checking moves too.
1290             // If we see a move whose value is zero, the rest of the moves
1291             // in this ply can be tossed.
1292             ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE | VERIFY_AFTER));
1293             ASSERT(iBestScore > -NMATE);
1294             goto end;
1295         }
1296         mv = ctx->sMoveStack.mvf[x].mv;
1297 #ifdef DEBUG
1298         ASSERT(0 == (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED));
1299         ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
1300 #endif
1301
1302         if (FALSE == _ShouldWeConsiderThisMove(ctx,
1303                                                x,
1304                                                iFutility,
1305                                                fIncludeChecks))
1306         {
1307             continue;
1308         }
1309
1310         // If fIncludeChecks is FALSE then we still need to see if
1311         // this move is going to check the opponent; GenerateMoves
1312         // didn't do it for us to save time in the event of a fail
1313         // high.
1314         if (FALSE == fIncludeChecks)
1315         {
1316             mv.bvFlags |= WouldGiveCheck(ctx, mv);
1317         }
1318
1319         if (MakeMove(ctx, mv))
1320         {
1321             uLegalMoves++;
1322             pf->uQsearchNodes++;
1323             pf->uQsearchDepth++;
1324             ASSERT(pf->uQsearchDepth > 0);
1325             iScore = -QSearch(ctx,
1326                               -iBeta,
1327                               -iAlpha);
1328             pf->uQsearchDepth--;
1329             UnmakeMove(ctx, mv);
1330
1331             if (iScore > iBestScore)
1332             {
1333                 iBestScore = iScore;
1334                 pi->mvBest = mv;
1335
1336                 if (iScore > iAlpha)
1337                 {
1338                     if (iScore >= iBeta)
1339                     {
1340                         KEEP_TRACK_OF_FIRST_MOVE_FHs(uLegalMoves == 1);
1341                         ASSERT(iBestScore > -NMATE);
1342                         ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
1343                         goto end;
1344                     }
1345                     else
1346                     {
1347                         UpdatePV(ctx, mv);
1348                         StoreExactScore(mv, pos, iScore, 0, FALSE, ctx->uPly);
1349                         iAlpha = iScore;
1350
1351                         // Readjust futility margin here; it can be wider now.
1352                         if (iAlpha < +NMATE)
1353                         {
1354                             iFutility = (iAlpha -
1355                                          (FUTILITY_BASE_MARGIN +
1356                                           ctx->uPositional) -
1357                                          iEval);
1358                             iFutility = MAX0(iFutility);
1359                         }
1360                     }
1361                 }
1362             }
1363             if (WE_SHOULD_STOP_SEARCHING) goto end;
1364         }
1365     }
1366     ASSERT(iBestScore > -NMATE);
1367     ASSERT(SanityCheckMoves(ctx, x, VERIFY_BEFORE));
1368
1369  end:
1370     ctx->sSearchFlags.fCouldStandPat[pos->uToMove] = fOrigStandPat;
1371     ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
1372     ASSERT(IS_VALID_SCORE(iBestScore) || WE_SHOULD_STOP_SEARCHING);
1373     DTLeaveNode(ctx, TRUE, iBestScore, pi->mvBest);
1374     return(iBestScore);
1375 }