src/searchsup.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     searchsup.c
   8
   9 Abstract:
  10
  11     Search support routines.  See also search.c, root.c, and split.c.
  12
  13 Author:
  14
  15     Scott Gasch ([email protected]) 06 Oct 2005
  16
  17 Revision History:
  18
  19 **/
  20
  21 #include "chess.h"
  22
  23 extern SCORE g_iRootScore[2];
  24 extern ULONG g_uHardExtendLimit;
  25 extern ULONG g_uIterateDepth;
  26
  27 void
  28 UpdatePV(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv)
  29 /**
  30
  31 Routine description:
  32
  33     Update the principle variation at this depth.
  34
  35 Parameters:
  36
  37     SEARCHER_THREAD_CONTEXT *ctx,
  38     MOVE mv
  39
  40 Return value:
  41
  42     void
  43
  44 **/
  45 {
  46     PLY_INFO *this = &(ctx->sPlyInfo[ctx->uPly]);
  47     PLY_INFO *next = (this + 1);
  48     ULONG u = ctx->uPly;
  49
  50     ASSERT(u < MAX_PLY_PER_SEARCH);
  51     this->PV[u] = mv;
  52     u++;
  53     while(u < MAX_PLY_PER_SEARCH)
  54     {
  55         this->PV[u] = next->PV[u];
  56         if (0 == this->PV[u].uMove)
  57         {
  58             break;
  59         }
  60         u++;
  61     }
  62 }
  63
  64
  65 FLAG
  66 CheckInputAndTimers(IN SEARCHER_THREAD_CONTEXT *ctx)
  67 /**
  68
  69 Routine description:
  70
  71     This code is called from search when the total number of nodes
  72     searched is a multiple of g_MoveTimer.uNodeCheckMask.  Its job is
  73     to check for user input waiting on the input queue and to check to
  74     see if we are over a time limit.
  75
  76 Parameters:
  77
  78     void
  79
  80 Return value:
  81
  82     static FLAG : TRUE if the search should terminate and unroll,
  83                   FALSE if the search can continue
  84
  85 **/
  86 {
  87     double dTimeStamp;
  88
  89     //
  90     // See if there's user input to process.
  91     //
  92     if ((ctx->uThreadNumber == 0) && (NumberOfPendingInputEvents() != 0))
  93     {
  94         ParseUserInput(TRUE);
  95
  96         //
  97         // If the user input can be handled in the middle of the
  98         // search then it will have been.  If it cannot be handled
  99         // without stopping the search then ParseUserInput will flip
 100         // this bit in the MoveTimer to tell us (any any other
 101         // searcher threads) to stop and unroll.
 102         //
 103         if (WE_SHOULD_STOP_SEARCHING)
 104         {
 105             return(TRUE);
 106         }
 107     }
 108
 109     //
 110     // Also check time limits now.
 111     //
 112     if (-1 != g_MoveTimer.dSoftTimeLimit)
 113     {
 114         dTimeStamp = SystemTimeStamp();
 115         if ((g_MoveTimer.bvFlags & TIMER_CURRENT_OBVIOUS) ||
 116             (g_MoveTimer.bvFlags & TIMER_CURRENT_WONT_UNBLOCK))
 117         {
 118             Trace("OBVIOUS MOVE / WON'T UNBLOCK --> stop searching now\n");
 119             g_MoveTimer.bvFlags |= TIMER_STOPPING;
 120             return(TRUE);
 121         }
 122
 123         if (dTimeStamp > g_MoveTimer.dSoftTimeLimit)
 124         {
 125             //
 126             // If we have exceeded the soft time limit, move now unless...
 127             //
 128             if ((!(g_MoveTimer.bvFlags & TIMER_JUST_OUT_OF_BOOK)) &&
 129                 (!(g_MoveTimer.bvFlags & TIMER_ROOT_POSITION_CRITICAL)) &&
 130                 (!(g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FL)) &&
 131                 (!(g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FH)) &&
 132                 (!(g_MoveTimer.bvFlags & TIMER_MANY_ROOT_FLS)) &&
 133                 (g_MoveTimer.bvFlags & TIMER_SEARCHING_FIRST_MOVE))
 134             {
 135                 Trace("SOFT TIMER (%3.1f sec) --> "
 136                       "stop searching now\n",
 137                       dTimeStamp - g_MoveTimer.dStartTime);
 138                 g_MoveTimer.bvFlags |= TIMER_STOPPING;
 139                 return(TRUE);
 140             }
 141         }
 142
 143         //
 144         // If we have exceeded the hard limit, we have to move no matter
 145         // what.
 146         //
 147         if (dTimeStamp > g_MoveTimer.dHardTimeLimit)
 148         {
 149             Trace("HARD TIMER (%3.1f sec) --> "
 150                   "stop searching now\n",
 151                   dTimeStamp - g_MoveTimer.dStartTime);
 152             g_MoveTimer.bvFlags |= TIMER_STOPPING;
 153             return(TRUE);
 154         }
 155     }
 156
 157     //
 158     // Also check raw node count limit here.
 159     //
 160     if (g_Options.u64MaxNodeCount != 0ULL &&
 161         ctx->sCounters.tree.u64TotalNodeCount > g_Options.u64MaxNodeCount)
 162     {
 163         Trace("NODE COUNT LIMIT (limit %llu, searched %llu) "
 164               "--> stop searching now\n", g_Options.u64MaxNodeCount,
 165               ctx->sCounters.tree.u64TotalNodeCount);
 166         g_MoveTimer.bvFlags |= TIMER_STOPPING;
 167         return(TRUE);
 168     }
 169     return(FALSE);
 170 }
 171
 172
 173 FLAG
 174 ThreadUnderTerminatingSplit(IN SEARCHER_THREAD_CONTEXT *ctx)
 175 {
 176     ULONG u;
 177
 178     for (u = 0; u < NUM_SPLIT_PTRS_IN_CONTEXT; u++)
 179     {
 180         if (ctx->pSplitInfo[u] != NULL)
 181         {
 182             if (ctx->pSplitInfo[u]->fTerminate == TRUE) return(TRUE);
 183             return(FALSE);
 184         }
 185     }
 186     return(FALSE);
 187 }
 188
 189
 190 FLAG
 191 WeShouldDoHistoryPruning(IN SCORE iRoughEval,
 192                          IN SCORE iAlpha,
 193                          IN SCORE iBeta,
 194                          IN SEARCHER_THREAD_CONTEXT *ctx,
 195                          IN ULONG uRemainingDepth,
 196                          IN ULONG uLegalMoves,
 197                          IN MOVE mv,
 198                          IN ULONG uMoveNum,
 199                          IN INT iExtend)
 200 /**
 201
 202 Routine description:
 203
 204     Decide whether or not to do history pruning at this node for the
 205     given move.  Note: this function is called after the move has
 206     been played on the board.
 207
 208 Parameters:
 209
 210     SEARCHER_THREAD_CONTEXT *ctx,
 211     ULONG uRemainingDepth,
 212     ULONG uLegalMoves,
 213     MOVE mv,
 214     INT iExtend
 215
 216 Return value:
 217
 218     FLAG
 219
 220 **/
 221 {
 222     ASSERT(ctx->uPly > 0);
 223     ASSERT(mv.uMove);
 224     ASSERT((uMoveNum > 0) || (uLegalMoves == 0));
 225     if ((uRemainingDepth >= TWO_PLY) &&
 226         (iBeta == (iAlpha + 1)) &&
 227         (uLegalMoves > 5) &&
 228         (0 == iExtend) &&
 229 //        (iRoughEval + ComputeMoveScore(ctx, mv, uMoveNum - 1) + 200 < iAlpha) &&
 230         (!IS_ESCAPING_CHECK(mv)) &&
 231         (!IS_CAPTURE_OR_PROMOTION(mv)) &&
 232         (!IS_CHECKING_MOVE(mv)) &&
 233         (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][0])) &&
 234         (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-1][1])) &&
 235         ((ctx->uPly < 3) ||
 236          (!IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][0]) &&
 237           !IS_SAME_MOVE(mv, ctx->mvKiller[ctx->uPly-3][1]))) &&
 238         (GetMoveFailHighPercentage(mv) <= 10))
 239     {
 240         ASSERT(!InCheck(&ctx->sPosition, ctx->sPosition.uToMove));
 241         return(TRUE);
 242     }
 243     return(FALSE);
 244 }
 245
 246
 247 SCORE
 248 ComputeMoveScore(IN SEARCHER_THREAD_CONTEXT *ctx,
 249                  IN MOVE mv,
 250                  IN ULONG uMoveNum)
 251 {
 252     SCORE iMoveScore = (PIECE_VALUE(mv.pCaptured) +
 253                         PIECE_VALUE(mv.pPromoted));
 254     if (uMoveNum != (ULONG)-1)
 255     {
 256         ASSERT(uMoveNum < MAX_MOVE_STACK);
 257         ASSERT(IS_SAME_MOVE(mv, ctx->sMoveStack.mvf[uMoveNum].mv));
 258         iMoveScore = ctx->sMoveStack.mvf[uMoveNum].iValue;
 259         if (iMoveScore >= SORT_THESE_FIRST)
 260         {
 261             ASSERT(iMoveScore > 0);
 262             iMoveScore &= STRIP_OFF_FLAGS;
 263         }
 264         else
 265         {
 266             iMoveScore = MIN0(iMoveScore);
 267         }
 268     }
 269     return(iMoveScore);
 270 }
 271
 272
 273 void
 274 ComputeMoveExtension(IN SEARCHER_THREAD_CONTEXT *ctx,
 275                      IN SCORE iAlpha,
 276                      IN SCORE iBeta,
 277                      IN ULONG uMoveNum,
 278                      IN SCORE iRoughEval,
 279                      IN ULONG uDepth,
 280                      IN OUT INT *piExtend)
 281 /**
 282
 283 Routine description:
 284
 285     This routine is called by Search and by HelpSearch (in split.c).
 286     It's job is to assign a move-based extension for the move mv.
 287     This extension should be between -ONE_PLY (reduction) and +ONE_PLY
 288     (extension).
 289
 290     Note: this code is executed after the move has already been played
 291     on the board!
 292
 293 Parameters:
 294
 295     IN SEARCHER_THREAD_CONTEXT *ctx : the searcher thread's context
 296     IN SCORE iAlpha : current alpha
 297     IN SCORE iBeta : current beta
 298     IN ULONG uMoveNum : move number in stack
 299     IN ULONG uDepth : remaining depth
 300     IN OUT INT *piExtend : extension amount (in/out)
 301
 302 Return value:
 303
 304     void
 305
 306 **/
 307 {
 308     static const SCORE _window[MAX_PLY_PER_SEARCH] = {
 309          -1,  -1, 500, 500, 425, 425, 350, 350, 275, 275, 200, 200, // 0..11
 310         150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 12..23
 311         150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 24..35
 312         150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 36..47
 313         150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, // 48..59
 314         150, 150, 150, 150                                          // 60..63
 315     };
 316     POSITION *pos = &ctx->sPosition;
 317     MOVE mvLast = ctx->sPlyInfo[ctx->uPly-2].mv;
 318     MOVE mv = ctx->sPlyInfo[ctx->uPly-1].mv;
 319     ULONG uColor = GET_COLOR(mv.pMoved);
 320     SCORE iMoveScore;
 321 #ifdef DEBUG
 322     int iM;
 323
 324     //
 325     // Preconditions
 326     //
 327     ASSERT(IS_VALID_SCORE(iAlpha));
 328     ASSERT(IS_VALID_SCORE(iBeta));
 329     ASSERT(iAlpha < iBeta);
 330     ASSERT(ctx->uPly >= 2);
 331     ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH);
 332     ASSERT(mv.uMove);
 333     ASSERT(*piExtend >= 0);
 334 #endif
 335
 336     // Checking move extension.
 337     if (IS_CHECKING_MOVE(mv))
 338     {
 339         ASSERT(InCheck(pos, pos->uToMove));
 340         INC(ctx->sCounters.extension.uCheck);
 341         *piExtend += ONE_PLY;
 342         if (pos->uNonPawnMaterial[FLIP(pos->uToMove)] >
 343             (VALUE_KING + VALUE_BISHOP))
 344         {
 345             goto enforce_ceiling;
 346         }
 347         *piExtend -= THREE_QUARTERS_PLY;
 348     }
 349
 350     // Pawn push extension
 351     if (IS_PAWN(mv.pMoved))
 352     {
 353         if (((GET_COLOR(mv.pMoved) == WHITE) && RANK7(mv.cTo)) ||
 354             ((GET_COLOR(mv.pMoved) == BLACK) && RANK2(mv.cTo)))
 355         {
 356             *piExtend += THREE_QUARTERS_PLY;
 357             if (DISTANCE(pos->cNonPawns[GET_COLOR(mv.pMoved)][0], mv.cTo) < 3)
 358             {
 359                 *piExtend += QUARTER_PLY;
 360             }
 361             INC(ctx->sCounters.extension.uPawnPush);
 362             goto enforce_ceiling;
 363         }
 364     }
 365
 366     // Responses to check extensions:
 367     if (IS_CHECKING_MOVE(mvLast))
 368     {
 369         ASSERT(IS_ESCAPING_CHECK(mv));
 370         iMoveScore = iRoughEval + ComputeMoveScore(ctx, mv, uMoveNum);
 371
 372         // One legal move in reply to check...
 373         if (ONE_LEGAL_MOVE(ctx, ctx->uPly - 1) &&
 374             CountKingSafetyDefects(&ctx->sPosition, uColor) > 1)
 375         {
 376             *piExtend += (QUARTER_PLY +
 377                           HALF_PLY *
 378                           (iMoveScore + VALUE_KNIGHT > iAlpha));
 379             INC(ctx->sCounters.extension.uOneLegalMove);
 380         }
 381
 382         // Singular response to check...
 383         if ((mv.pCaptured) &&
 384             (iRoughEval + 225 < iAlpha) &&
 385             (iMoveScore + 75 > iAlpha))
 386         {
 387             *piExtend += ONE_PLY;
 388             INC(ctx->sCounters.extension.uSingularReplyToCheck);
 389             goto enforce_ceiling;
 390         }
 391     }
 392
 393     // These last ones only happen if we are close to the root score.
 394     ASSERT(_window[ctx->uPly] > 0);
 395     if ((iRoughEval >= (g_iRootScore[uColor] - _window[ctx->uPly] * 2)) &&
 396         (iRoughEval <= (g_iRootScore[uColor] + _window[ctx->uPly] * 2)))
 397     {
 398         // Endgame extension
 399         if ((ctx->sPlyInfo[1].uTotalNonPawns > 2) &&
 400             ((pos->uNonPawnCount[BLACK][0] +
 401               pos->uNonPawnCount[WHITE][0]) == 2))
 402         {
 403             if ((mv.pCaptured && !IS_PAWN(mv.pCaptured)) ||
 404                 (mvLast.pCaptured && !IS_PAWN(mvLast.pCaptured)))
 405             {
 406                 *piExtend += HALF_PLY;
 407                 INC(ctx->sCounters.extension.uEndgame);
 408             }
 409         }
 410
 411         // Recapture extension
 412         if ((iRoughEval >= (g_iRootScore[uColor] - _window[ctx->uPly])) &&
 413             (iRoughEval <= (g_iRootScore[uColor] + _window[ctx->uPly])))
 414         {
 415             if (uDepth <= THREE_PLY)
 416             {
 417                 if ((mv.pCaptured) && !IS_PAWN(mv.pCaptured) &&
 418                     ((PIECE_VALUE(mv.pCaptured) ==
 419                       PIECE_VALUE(mvLast.pCaptured)) ||
 420                      ((mvLast.pPromoted) && (mv.cTo == mvLast.cTo))))
 421                 {
 422                     iMoveScore = ComputeMoveScore(ctx, mv, uMoveNum);
 423                     if (iMoveScore >= 0)
 424                     {
 425                         *piExtend += HALF_PLY;
 426                         INC(ctx->sCounters.extension.uRecapture);
 427                     }
 428                 }
 429             }
 430         }
 431     }
 432
 433  enforce_ceiling:
 434
 435     // Don't let extensions add up to > 1 ply
 436 #ifdef DEBUG
 437     iM = MIN(ONE_PLY, *piExtend);
 438 #endif
 439     ASSERT(!(*piExtend & 0x80000000));
 440     *piExtend = MINU(ONE_PLY, *piExtend);
 441     ASSERT(iM == *piExtend);
 442
 443     // Scale back extensions that are very far from the root:
 444     //
 445     //        Iterate   g_Soft              g_Hard
 446     // |    |    |    |    |    |    |    |    |
 447     // 0         1         2   3/2   3         4       (x Iterate)
 448     // |-------------------|----|----|---------|----...
 449     // |full full full full|-1/4|-1/2|-3/4 -3/4|none...
 450     ASSERT(ctx->uPly != 0);
 451     ASSERT(ctx->uPly <= MAX_PLY_PER_SEARCH);
 452     *piExtend -= g_uExtensionReduction[ctx->uPly-1];
 453 #ifdef DEBUG
 454     iM = MAX(0, *piExtend);
 455 #endif
 456     *piExtend = MAX0(*piExtend);
 457     ASSERT(iM == *piExtend);
 458     ctx->sPlyInfo[ctx->uPly-1].iExtensionAmount = *piExtend;
 459     ASSERT((0 <= *piExtend) && (*piExtend <= ONE_PLY));
 460 }
 461
 462
 463
 464
 465 #ifdef DO_IID
 466 SCORE
 467 RescoreMovesViaSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
 468                       IN ULONG uDepth,
 469                       IN SCORE iAlpha,
 470                       IN SCORE iBeta)
 471 /**
 472
 473 Routine description:
 474
 475     This is my implementation of "internal iterative deepening".  It's
 476     not really IID because it doesn't recurse on the same position.
 477     This code is called when we are at a PV node and have no hash move
 478     and no good capture from the generator.  Instead of relying on
 479     only history / killer heuristics to order the moves instead we
 480     reduce the depth by two ply and search all the moves generated.
 481     The scores that come out of the reduced-depth search are then used
 482     to order the moves at the regular-depth search.  This is somewhat
 483     recursive because the first move considered by the reduced-depth
 484     search may also have no hash move / good capture and invoke the
 485     whole process again.
 486
 487 Parameters:
 488
 489     IN SEARCHER_THREAD_CONTEXT *ctx,
 490     IN ULONG uDepth,
 491     IN SCORE iAlpha,
 492     IN SCORE iBeta
 493
 494 Return value:
 495
 496     SCORE
 497
 498 **/
 499 {
 500     ULONG x;
 501     MOVE mv;
 502     SCORE iScore;
 503     SCORE iBestScore = -INFINITY;
 504     ULONG uBest;
 505
 506     //
 507     // Preconditions
 508     //
 509     ASSERT(IS_VALID_SCORE(iAlpha));
 510     ASSERT(IS_VALID_SCORE(iBeta));
 511     ASSERT(iAlpha < iBeta);
 512     ASSERT(uDepth >= (IID_R_FACTOR + ONE_PLY));
 513
 514     //
 515     // Compute next depth, possibly recurse
 516     //
 517     uDepth -= (IID_R_FACTOR + ONE_PLY);
 518     if (uDepth >= (IID_R_FACTOR + ONE_PLY))
 519     {
 520         (void)RescoreMovesViaSearch(ctx, uDepth, iAlpha, iBeta);
 521     }
 522     ASSERT(uDepth < MAX_DEPTH_PER_SEARCH);
 523
 524     //
 525     // Search the moves and remember the scores
 526     //
 527     for (x = uBest = ctx->sMoveStack.uBegin[ctx->uPly];
 528          x < ctx->sMoveStack.uEnd[ctx->uPly];
 529          x++)
 530     {
 531         SelectBestNoHistory(ctx, x);
 532         mv = ctx->sMoveStack.mvf[x].mv;
 533         mv.bvFlags |= WouldGiveCheck(ctx, mv);
 534         if (TRUE == MakeMove(ctx, mv))
 535         {
 536             if (-INFINITY == iBestScore)
 537             {
 538                 iScore = -Search(ctx, -iBeta, -iAlpha, uDepth);
 539             }
 540             else
 541             {
 542                 iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uDepth);
 543                 if (iScore > iAlpha)
 544                 {
 545                     iScore = -Search(ctx, -iBeta, -iAlpha, uDepth);
 546                 }
 547             }
 548             UnmakeMove(ctx, mv);
 549             ctx->sMoveStack.mvf[x].iValue = iScore;
 550             if (iScore > iBestScore)
 551             {
 552                 uBest = x;
 553                 iBestScore = iScore;
 554                 if (iScore >= iBeta)
 555                 {
 556                     goto end;
 557                 }
 558             }
 559         }
 560     }
 561
 562  end:
 563     //
 564     // Clear the values from the current move to the end of the
 565     // moves in the list so that if we failed high we don't have
 566     // stale move values in the list for moves we did not search
 567     // the subtrees for.
 568     //
 569     while(x < ctx->sMoveStack.uEnd[ctx->uPly])
 570     {
 571         ctx->sMoveStack.mvf[x].iValue = -INFINITY;
 572         x++;
 573     }
 574     ctx->sMoveStack.mvf[uBest].iValue |= SORT_THESE_FIRST;
 575     ASSERT(IS_VALID_SCORE(iBestScore));
 576     return(iBestScore);
 577 }
 578 #endif
 579
 580
 581 FLAG
 582 MateDistancePruningCutoff(IN ULONG uPly,
 583                           IN FLAG fInCheck,
 584                           IN OUT SCORE *piBestScore,
 585                           IN OUT SCORE *piAlpha,
 586                           IN OUT SCORE *piBeta)
 587 /**
 588
 589 Routine description:
 590
 591     This idea (shamelessly?) "borrowed" from Fruit.  The idea is that
 592     the worst score we can return from any node in the tree is if we
 593     are in checkmate right now (indeed, if we're not in check right
 594     now than the worst score we can return is mated-in-2-ply).
 595
 596     Likewise the best score we can return from here is mate-in-1-ply.
 597     Use these facts to attempt to narrow the alpha..beta window.
 598     Indeed there are some cases where we can prune this entire tree
 599     branch.
 600
 601 Parameters:
 602
 603     ULONG uPly : ply from root
 604     FLAG InCheck : are we in check?
 605     SCORE *piBestScore : pointer to bestscore
 606     SCORE *piAlpha : pointer to alpha
 607     SCORE *piBeta : pointer to beta
 608
 609 Return value:
 610
 611     FLAG : TRUE if we can prune the branch outright, FALSE otherwise
 612
 613 **/
 614 {
 615     SCORE iScore = MATED_SCORE(uPly + 2 * !fInCheck);
 616
 617     //
 618     // Do the alpha side
 619     //
 620     if (*piAlpha < iScore)
 621     {
 622         *piAlpha = iScore;
 623         if (iScore >= *piBeta)
 624         {
 625             *piBestScore = iScore;
 626             return(TRUE);
 627         }
 628     }
 629
 630     //
 631     // Do the beta side
 632     //
 633     iScore = -1 * MATED_SCORE(uPly + 1);
 634     if (iScore < *piBeta)
 635     {
 636         *piBeta = iScore;
 637         if (iScore <= *piAlpha)
 638         {
 639             *piBestScore = iScore;
 640             return(TRUE);
 641         }
 642     }
 643     return(FALSE);
 644 }
 645
 646
 647 void
 648 DumpPlyInfoStack(IN SEARCHER_THREAD_CONTEXT *ctx,
 649                  IN SCORE iAlpha,
 650                  IN SCORE iBeta)
 651 /**
 652
 653 Routine description:
 654
 655     Dump some information about the current search line; mainly here as
 656     a debugging aide.
 657
 658     Note: this will not work on an MP searcher thread that is under a
 659     split node.
 660
 661 Parameters:
 662
 663     SEARCHER_THREAD_CONTEXT *ctx : searcher context to dump
 664
 665 Return value:
 666
 667     void
 668
 669 **/
 670 {
 671     ULONG u, v;
 672     POSITION *pos = GetRootPosition();
 673     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
 674     char *p = PositionToFen(pos);
 675     PLY_INFO *q;
 676     FLAG fSeenQ = FALSE;
 677     SCORE iEval;
 678     static SEARCHER_THREAD_CONTEXT temp;
 679
 680     InitializeSearcherContext(pos, &temp);
 681
 682     Trace("Iterate Depth: %2u\tCurrent Ply: %2u\n", g_uIterateDepth,
 683           ctx->uPly);
 684     Trace("Qsearch Check: %2u\tCurrent Qdepth: %2u\n", pf->uQsearchCheckDepth,
 685           pf->uQsearchDepth);
 686     Trace("Current a..b: %d .. %d\n", iAlpha, iBeta);
 687     if (NULL != p)
 688     {
 689         Trace("Root: %s\n", p);
 690         SystemFreeMemory(p);
 691     }
 692     Trace("\n");
 693     Trace("move\t number\t exten\t   eval       b.keval      w.keval   Danger Squares\n"
 694           "----------------------------------------------------------------------------\n");
 695
 696     ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH);
 697     for (u = 0; u < ctx->uPly; u++)
 698     {
 699         q = &ctx->sPlyInfo[u];
 700         ASSERT(PositionsAreEquivalent(&q->sPosition, &temp.sPosition));
 701
 702         if ((FALSE == fSeenQ) && (q->fInQsearch == TRUE))
 703         {
 704             p = PositionToFen(&temp.sPosition);
 705             if (NULL != p)
 706             {
 707                 Trace("\nHorizon: %s\n\n", p);
 708                 SystemFreeMemory(p);
 709             }
 710             fSeenQ = TRUE;
 711         }
 712
 713         Trace("%02u.%-6s ", u, MoveToSan(q->mv, &temp.sPosition));
 714         for (v = ctx->sMoveStack.uBegin[u];
 715              v < ctx->sMoveStack.uEnd[u];
 716              v++)
 717         {
 718             if (IS_SAME_MOVE(q->mv, ctx->sMoveStack.mvf[v].mv))
 719             {
 720                 Trace("%u/%u", v - ctx->sMoveStack.uBegin[u] + 1,
 721                       MOVE_COUNT(ctx, u));
 722             }
 723         }
 724         Trace("\t");
 725
 726         if (FALSE == MakeMove(&temp, q->mv))
 727         {
 728             Trace("Illegal move?!\n");
 729             return;
 730         }
 731
 732         if (q->iExtensionAmount != 0)
 733         {
 734             Trace("%-3u\t", q->iExtensionAmount);
 735         }
 736         else
 737         {
 738             Trace("   \t");
 739         }
 740
 741         iEval = Eval(&temp, -INFINITY, +INFINITY);
 742         Trace("%5s (%+2d) | ", ScoreToString(iEval),
 743               temp.sPosition.iMaterialBalance[temp.sPosition.uToMove] / 100);
 744         Trace("%5s (%2u) | ",
 745               ScoreToString(temp.sPlyInfo[temp.uPly].iKingScore[BLACK]),
 746               CountKingSafetyDefects(&temp.sPosition, BLACK));
 747         Trace("%5s (%2u)  ",
 748               ScoreToString(temp.sPlyInfo[temp.uPly].iKingScore[WHITE]),
 749               CountKingSafetyDefects(&temp.sPosition, WHITE));
 750         Trace("\n");
 751     }
 752
 753     p = PositionToFen(&ctx->sPosition);
 754     if (NULL != p)
 755     {
 756         Trace("\n");
 757         Trace("Now: %s\n", p);
 758         SystemFreeMemory(p);
 759     }
 760 }
 761
 762
 763 FLAG
 764 CommonSearchInit(IN SEARCHER_THREAD_CONTEXT *ctx,
 765                  IN OUT SCORE *piAlpha,
 766                  IN OUT SCORE *piBeta,
 767                  IN OUT SCORE *piScore)
 768 /**
 769
 770 Routine description:
 771
 772     A set of common code that is called by Search and QSearch.  It does
 773     the following:
 774
 775        1. Increment the total node counter
 776        2. Clears pi->mvBest and cDanger squares
 777        3. Possibly check for user input or timer expiration
 778        4. Checks to see if the position is a draw
 779        5. Makes sure ctx->uPly is not too deep
 780        6. Sets pi->fInCheck
 781        7. Does mate-distance pruning
 782
 783 Parameters:
 784
 785     IN SEARCHER_THREAD_CONTEXT *ctx,
 786     IN OUT SCORE *piAlpha,
 787     IN OUT SCORE *piBeta,
 788     IN OUT SCORE *piScore
 789
 790 Return value:
 791
 792     FLAG : TRUE if the search node should be aborted (return *piScore)
 793            FALSE otherwise (*piAlpha, *piBeta possibly adjusted)
 794
 795 **/
 796 {
 797     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
 798     FLAG fRet = TRUE;
 799
 800     ASSERT(*piAlpha < *piBeta);
 801
 802     //
 803     // Increment node count and see if we need to check input / timer
 804     //
 805     ctx->sCounters.tree.u64TotalNodeCount++;
 806     ASSERT(ctx->sCounters.tree.u64TotalNodeCount > 0);
 807     if ((ctx->sCounters.tree.u64TotalNodeCount &
 808          g_MoveTimer.uNodeCheckMask) == 0)
 809     {
 810         (void)CheckInputAndTimers(ctx);
 811     }
 812
 813     //
 814     // Make sure that the time allotted to search in has not expired
 815     // and (if this is an MP search) that we are still doing relevant work.
 816     //
 817     if (WE_SHOULD_STOP_SEARCHING)
 818     {
 819         pi->mvBest.uMove = 0;
 820         *piScore = INVALID_SCORE;
 821         goto end;
 822     }
 823
 824     //
 825     // Make sure we have not exceeded max ply; note that since this
 826     // is checked at the beginning of search/qsearch and if we let
 827     // the past they will call MakeMove this must cut off one ply
 828     // before the hard limit.
 829     //
 830     if ((ctx->uPly >= (MAX_PLY_PER_SEARCH - 1)) ||
 831         (ctx->sSearchFlags.uQsearchDepth >= g_uHardExtendLimit))
 832     {
 833         *piScore = *piBeta;
 834         DTTRACE("<toodeep/>");
 835         goto end;
 836     }
 837
 838     //
 839     // Erase deeper killer moves
 840     //
 841     if (ctx->uPly + 2 < MAX_PLY_PER_SEARCH)
 842     {
 843         ctx->mvKiller[ctx->uPly + 2][0].uMove = 0;
 844         ctx->mvKiller[ctx->uPly + 2][1].uMove = 0;
 845     }
 846
 847     //
 848     // Set fInCheck in this ply info struct
 849     //
 850     pi->fInCheck = (IS_CHECKING_MOVE((pi-1)->mv) != 0);
 851     ASSERT((pi->fInCheck &&
 852             (InCheck(&ctx->sPosition, ctx->sPosition.uToMove))) ||
 853            (!pi->fInCheck &&
 854             (!InCheck(&ctx->sPosition, ctx->sPosition.uToMove))));
 855
 856     //
 857     // This code is for a debug option where I dump paths from root
 858     // to leaf along with extensions and evals at each node in the
 859     // path for debugging/brainstorming purposes.
 860     //
 861     pi->PV[ctx->uPly].uMove = 0;
 862     pi->mvBest.uMove = 0;
 863     pi->iExtensionAmount = 0;
 864     pi->iEval = INVALID_SCORE;
 865 #if 0
 866     if ((g_uIterateDepth > 5) &&
 867         (ctx->uPly > 2.5 * g_uIterateDepth))
 868     {
 869         DumpPlyInfoStack(ctx, *piAlpha, *piBeta);
 870     }
 871 #endif
 872
 873     //
 874     // See if this position is a draw
 875     //
 876     if (TRUE == IsDraw(ctx))
 877     {
 878         INC(ctx->sCounters.tree.u64LeafCount);
 879         *piScore = 0;
 880         if ((*piAlpha < *piScore) && (*piScore < *piBeta))
 881         {
 882             UpdatePV(ctx, DRAWMOVE);
 883         }
 884         DTTRACE("<i bold=\"draw\"/>");
 885         goto end;
 886     }
 887
 888     //
 889     // Do mate-distance pruning
 890     //
 891     if (TRUE == MateDistancePruningCutoff(ctx->uPly,
 892                                           pi->fInCheck,
 893                                           piScore,
 894                                           piAlpha,
 895                                           piBeta))
 896     {
 897         ASSERT(*piScore != -INFINITY);
 898         ASSERT((*piScore <= *piAlpha) || (*piScore >= *piBeta));
 899         goto end;
 900     }
 901 #ifdef DEBUG
 902     pi->iAlpha = *piAlpha;
 903     pi->iBeta = *piBeta;
 904 #endif
 905     fRet = FALSE;
 906
 907  end:
 908     ASSERT(IS_VALID_FLAG(fRet));
 909     return(fRet);
 910 }
 911
 912
 913 ULONG
 914 SelectNullmoveRFactor(SEARCHER_THREAD_CONTEXT *ctx,
 915                       INT uDepth)
 916 {
 917     ULONG u = TWO_PLY;
 918     ULONG uMaxPiecesPerSide = MAXU(ctx->sPosition.uNonPawnCount[WHITE][0],
 919                                    ctx->sPosition.uNonPawnCount[BLACK][0]);
 920     ASSERT(uMaxPiecesPerSide <= 16);
 921
 922     if ((uDepth > 8 * ONE_PLY) ||
 923         ((uDepth > 6 * ONE_PLY) && (uMaxPiecesPerSide >= 3)))
 924     {
 925         u = THREE_PLY;
 926     }
 927     ASSERT((u == TWO_PLY) || (u == THREE_PLY));
 928     return(u);
 929 }
 930
 931
 932 FLAG
 933 WeShouldTryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx,
 934                            SCORE iAlpha,
 935                            SCORE iBeta,
 936                            SCORE iRoughEval,
 937                            ULONG uNullDepth)
 938 {
 939     static SCORE _iDistAlphaSkipNull[] = {
 940       700, 950, 1110, 1150, 1190, 1230, 1270, 0
 941     };
 942     POSITION *pos = &ctx->sPosition;
 943     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
 944     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
 945     ULONG u;
 946
 947     ASSERT(IS_VALID_SCORE(iAlpha) && IS_VALID_SCORE(iBeta));
 948     ASSERT(iAlpha < iBeta);
 949     ASSERT(IS_VALID_SCORE(iRoughEval));
 950     ASSERT(uNullDepth < MAX_PLY_PER_SEARCH * ONE_PLY);
 951
 952     if ((FALSE == pf->fAvoidNullmove) &&
 953         (pos->uNonPawnCount[pos->uToMove][0] > 2) &&
 954         (FALSE == pi->fInCheck) &&
 955         (iBeta != +INFINITY) &&
 956         (iBeta == iAlpha + 1)) // <--- TODO: test this one please...
 957     {
 958         if (uNullDepth <= 6 * ONE_PLY)
 959         {
 960             u = uNullDepth / ONE_PLY;
 961             ASSERT(u <= 6);
 962             if ((iRoughEval + _iDistAlphaSkipNull[u] <= iAlpha) ||
 963                 ((iRoughEval + _iDistAlphaSkipNull[u] / 2 <= iAlpha) &&
 964                  (ValueOfMaterialInTroubleAfterNull(pos, pos->uToMove))))
 965             {
 966                 return FALSE;
 967             }
 968         }
 969         return TRUE;
 970     }
 971     return FALSE;
 972 }
 973
 974
 975 FLAG
 976 TryNullmovePruning(SEARCHER_THREAD_CONTEXT *ctx,
 977                    FLAG *pfThreat,
 978                    SCORE iAlpha,
 979                    SCORE iBeta,
 980                    ULONG uNullDepth,
 981                    INT *piOrigExtend,
 982                    SCORE *piNullScore)
 983 {
 984     static INT _bm_by_piece[7] = {
 985         -1, -1, QUARTER_PLY, QUARTER_PLY, HALF_PLY, HALF_PLY, -1
 986     };
 987     POSITION *pos = &ctx->sPosition;
 988     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
 989     CUMULATIVE_SEARCH_FLAGS *pf = &ctx->sSearchFlags;
 990     SCORE iVerifyScore;
 991     MOVE mv;
 992     MOVE mvRef;
 993
 994     ASSERT(IS_VALID_SCORE(iAlpha) && IS_VALID_SCORE(iBeta));
 995     ASSERT(iAlpha < iBeta);
 996
 997     // TODO: more experiments with quick null
 998
 999     // Ok, do it.
1000     ASSERT(!InCheck(pos, pos->uToMove));
1001     VERIFY(MakeMove(ctx, NULLMOVE));
1002     ASSERT(pos->u64NonPawnSig != pi->sPosition.u64NonPawnSig);
1003     ASSERT(pos->uToMove != pi->sPosition.uToMove);
1004     INC(ctx->sCounters.tree.u64NullMoves);
1005
1006     // (Reduced depth) search under the nullmove; don't allow two
1007     // nullmoves in a row.
1008     ASSERT(pf->fAvoidNullmove == FALSE);
1009     pf->fAvoidNullmove = TRUE;
1010     *piNullScore = -Search(ctx, -iBeta, -iBeta + 1, uNullDepth);
1011     pf->fAvoidNullmove = FALSE;
1012
1013     // Check the results
1014     if (*piNullScore >= iBeta)
1015     {
1016         UnmakeMove(ctx, NULLMOVE);
1017         ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
1018
1019         // If there are very few pieces on the board, launch a
1020         // separate "verification search".
1021         if ((pos->uNonPawnCount[pos->uToMove][0] < 4) &&
1022             (pf->fVerifyNullmove == TRUE))
1023         {
1024             ASSERT(pf->fAvoidNullmove == FALSE);
1025             uNullDepth -= ONE_PLY;
1026             if (uNullDepth > MAX_DEPTH_PER_SEARCH) uNullDepth = 0;
1027             pf->fVerifyNullmove = FALSE;
1028             iVerifyScore = Search(ctx, iAlpha, iBeta, uNullDepth);
1029             pf->fVerifyNullmove = TRUE;
1030             if (iVerifyScore < iBeta)
1031             {
1032                 // The nullmove failed high but the verify search
1033                 // did not; we are in zug so extend.
1034                 *piOrigExtend += ONE_PLY;
1035                 INC(ctx->sCounters.extension.uZugzwang);
1036                 return FALSE;
1037             }
1038         }
1039
1040         // Nullmove succeeded and either no need to verify or verify
1041         // succeeded too.
1042         INC(ctx->sCounters.tree.u64NullMoveSuccess);
1043         if (*piNullScore > +NMATE) *piNullScore = +NMATE;
1044         return TRUE;
1045     }
1046
1047     // Nullmove failed...
1048     mv = (pi+1)->mvBest;
1049     if (mv.uMove)
1050     {
1051         // See what we can learn from the move that refuted our nullmove.
1052         ASSERT(SanityCheckMove(pos, mv));
1053         ASSERT(GET_COLOR(mv.pMoved) == pos->uToMove);
1054         ASSERT(ctx->uPly >= 2);
1055
1056         // If we make a nullmove that fails because we lose a
1057         // piece, remember that the piece in question is in danger.
1058         if ((mv.pCaptured) && !IS_PAWN(mv.pCaptured))
1059         {
1060             ASSERT(GET_COLOR(mv.pCaptured) == FLIP(pos->uToMove));
1061             ASSERT(mv.pCaptured == pos->rgSquare[mv.cTo].pPiece);
1062             StoreEnprisePiece(pos, mv.cTo);
1063             mvRef = ctx->mvNullmoveRefutations[ctx->uPly - 2];
1064             if ((mvRef.uMove) &&
1065                 (mvRef.pCaptured == mv.pCaptured) &&
1066                 (mvRef.pMoved == mv.pMoved) &&
1067                 (mvRef.cTo != mv.cTo))
1068             {
1069                 ASSERT(GET_COLOR(mvRef.pCaptured) == FLIP(pos->uToMove));
1070                 ASSERT(mvRef.pCaptured);
1071                 ASSERT(_bm_by_piece[PIECE_TYPE(mv.pCaptured)] > 0);
1072                 ASSERT(_bm_by_piece[PIECE_TYPE(mv.pCaptured)] <=
1073                        ONE_PLY);
1074                 *piOrigExtend += _bm_by_piece[PIECE_TYPE(mv.pCaptured)];
1075                 INC(ctx->sCounters.extension.uBotvinnikMarkoff);
1076             }
1077             ctx->mvNullmoveRefutations[ctx->uPly] = mv;
1078         }
1079
1080         // This is an idea from Tord Romstad on ccc: if we are below a
1081         // history reduced node and we try a nullmove and the nullmove
1082         // fails low and the move that refuted the nullmove involves
1083         // the same piece moved in the reduced move at ply-1 then bail
1084         // out of the reduced depth search now and research at full
1085         // depth.  The move that was reduced had some tactical
1086         // significance.
1087         ASSERT(IS_ON_BOARD(mv.cFrom));
1088         if ((mv.cFrom == (pi-1)->mv.cTo) && ((pi-1)->iExtensionAmount < 0))
1089         {
1090             ASSERT(GET_COLOR(mv.pMoved) == GET_COLOR((pi-1)->mv.pMoved));
1091             UnmakeMove(ctx, NULLMOVE);
1092             ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
1093             *piNullScore = iAlpha - 1;
1094             return TRUE;
1095         }
1096     }
1097
1098     // If we do nothing we are mated-in-n, therefore this is a
1099     // dangerous position so extend.  This is Bruce Moreland's idea
1100     // originally.
1101     if (*piNullScore <= -NMATE)
1102     {
1103         if (mv.uMove && !IS_CAPTURE_OR_PROMOTION(mv))
1104         {
1105             ASSERT(SanityCheckMove(pos, mv));
1106             ASSERT(GET_COLOR(mv.pMoved) == pos->uToMove);
1107             UpdateDynamicMoveOrdering(ctx,
1108                                       uNullDepth + TWO_PLY,
1109                                       mv,
1110                                       *piNullScore,
1111                                       0);
1112         }
1113         *pfThreat = TRUE;
1114     }
1115     UnmakeMove(ctx, NULLMOVE);
1116     ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
1117     return FALSE;
1118 }
1119
1120
1121 #ifdef DEBUG
1122 FLAG
1123 SanityCheckMoves(IN SEARCHER_THREAD_CONTEXT *ctx,
1124                  IN ULONG uCurrent,
1125                  IN ULONG uType)
1126 /**
1127
1128 Routine description:
1129
1130     Support routine to sanity check that:
1131
1132         1. The moves before uCurrent on the move stack were all marked
1133            as searched (or pruned)
1134         2. The moves after uCurrent on the move stack are all zero
1135            value moves and not checking moves.
1136
1137 Parameters:
1138
1139     SEARCHER_THREAD_CONTEXT *ctx,
1140     ULONG uCurrent,
1141     ULONG uType
1142
1143 Return value:
1144
1145     FLAG
1146
1147 **/
1148 {
1149     ULONG x;
1150
1151     if (WE_SHOULD_STOP_SEARCHING)
1152     {
1153         return(TRUE);
1154     }
1155
1156     //
1157     // Check moves yet to be searched
1158     //
1159     if (uType & VERIFY_AFTER)
1160     {
1161         for (x = uCurrent; x < ctx->sMoveStack.uEnd[ctx->uPly]; x++)
1162         {
1163             ASSERT(ctx->sMoveStack.mvf[x].iValue <= 0);
1164             ASSERT(!IS_CHECKING_MOVE(ctx->sMoveStack.mvf[x].mv));
1165         }
1166     }
1167
1168     //
1169     // Check moves already searched
1170     //
1171     if (uType & VERIFY_BEFORE)
1172     {
1173         for (x = uCurrent - 1;
1174              ((x >= ctx->sMoveStack.uBegin[ctx->uPly]) && (x != (ULONG)-1));
1175              x--)
1176         {
1177             ASSERT(ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED);
1178         }
1179     }
1180     return(TRUE);
1181 }
1182 #endif