src/root.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     root.c
   8
   9 Abstract:
  10
  11     Routines dealing with the root of the search tree.  Specifically
  12     move ordering at the root node, searching, search support, pondering,
  13     pondering support, and the main iterative deepening loop.
  14
  15 Author:
  16
  17     Scott Gasch ([email protected]) 21 May 2004
  18
  19 Revision History:
  20
  21     $Id: root.c 356 2008-07-02 16:18:12Z scott $
  22
  23 **/
  24
  25 #include "chess.h"
  26
  27 volatile MOVE_TIMER g_MoveTimer;
  28 ULONG g_uIterateDepth;
  29 ULONG g_uSoftExtendLimit;
  30 ULONG g_uHardExtendLimit;
  31 ULONG g_uExtensionReduction[MAX_PLY_PER_SEARCH];
  32 FLAG g_fCanSplit[MAX_PLY_PER_SEARCH];
  33 SCORE g_iRootScore[2] = {0, 0};
  34 SCORE g_iScore;
  35
  36
  37 static void
  38 _SetMoveTimerForPonder(void)
  39 /**
  40
  41 Routine description:
  42
  43     Set the move timer before a ponder operation.  A time limit of -1
  44     means search forever... so the only way out of the ponder is for
  45     new user input to interrupt it.
  46
  47 Parameters:
  48
  49     void
  50
  51 Return value:
  52
  53     static void
  54
  55 **/
  56 {
  57     g_MoveTimer.dStartTime = SystemTimeStamp();
  58     g_MoveTimer.dSoftTimeLimit = -1;
  59     g_MoveTimer.dHardTimeLimit = -1;
  60     g_MoveTimer.uNodeCheckMask = 0x200 - 1;
  61     g_MoveTimer.bvFlags = 0;
  62 }
  63
  64
  65 void
  66 SetMoveTimerToThinkForever(void)
  67 /**
  68
  69 Routine description:
  70
  71 Parameters:
  72
  73     void
  74
  75 Return value:
  76
  77     void
  78
  79 **/
  80 {
  81     g_MoveTimer.dStartTime = SystemTimeStamp();
  82     g_MoveTimer.dSoftTimeLimit = -1;
  83     g_MoveTimer.dHardTimeLimit = -1;
  84     g_MoveTimer.uNodeCheckMask = 0x1000000 - 1;
  85     g_MoveTimer.bvFlags = 0;
  86 }
  87
  88
  89 void
  90 SetMoveTimerForSearch(FLAG fSwitchOver, ULONG uColor)
  91 /**
  92
  93 Routine description:
  94
  95     Set the move timer for a search operation.
  96
  97 Parameters:
  98
  99     FLAG fSwitchOver : if TRUE then this search is a converted ponder
 100     (i.e. they made the ponder move and now we are searching).
 101
 102 Return value:
 103
 104     void
 105
 106 **/
 107 {
 108     ULONG uMovesDone = GetMoveNumber(uColor);
 109     double dClock = (double)g_Options.uMyClock;
 110     double dSec = 0;
 111     ULONG uMargin = 0;
 112     ULONG uMovesToDo;
 113
 114     //
 115     // If switching over from a ponder search leave the start time and
 116     // move flags alone (i.e. N seconds in the past already).
 117     //
 118     if (FALSE == fSwitchOver)
 119     {
 120         g_MoveTimer.dStartTime = SystemTimeStamp();
 121         g_MoveTimer.bvFlags = 0;
 122     }
 123
 124     //
 125     // Check the clock more often in search if there is little time
 126     // left on the clock -- we can't afford an oversearch when the
 127     // bullet game is down to the wire.
 128     //
 129 #ifdef DEBUG
 130     g_MoveTimer.uNodeCheckMask = 0x800 - 1;
 131 #else
 132     if (WeAreRunningASuite())
 133     {
 134         g_MoveTimer.uNodeCheckMask = 0x20000 - 1;
 135     }
 136     else if (g_Options.u64MaxNodeCount)
 137     {
 138         g_MoveTimer.uNodeCheckMask = 0x1000 - 1;
 139     }
 140     else
 141     {
 142         if (dClock < 10.0)
 143         {
 144             g_MoveTimer.uNodeCheckMask = 0x400 - 1;
 145         }
 146         else
 147         {
 148             g_MoveTimer.uNodeCheckMask = 0x8000 - 1;
 149         }
 150     }
 151 #endif
 152
 153     switch (g_Options.eClock)
 154     {
 155         //
 156         // Fixed time per move.  Think for g_uMyIncrement seconds exactly and
 157         // no hard time limit.
 158         //
 159         case CLOCK_FIXED:
 160             dSec = (double)g_Options.uMyIncrement;
 161             uMargin = 0;
 162             break;
 163
 164         //
 165         // N moves per time control or entire game in time control.
 166         //
 167         case CLOCK_NORMAL:
 168             if (g_Options.uMovesPerTimePeriod != 0)
 169             {
 170                 //
 171                 // N moves per time control.
 172                 //
 173                 ASSERT(g_Options.uMovesPerTimePeriod < 256);
 174                 uMovesToDo =
 175                     (g_Options.uMovesPerTimePeriod -
 176                      ((uMovesDone - 1) % g_Options.uMovesPerTimePeriod));
 177 #ifdef DEBUG
 178                 Trace("SetMoveTimer: %u moves left to do this in %s sec.\n",
 179                       uMovesToDo, TimeToString(dClock));
 180 #endif
 181                 ASSERT(uMovesToDo <= g_Options.uMovesPerTimePeriod);
 182                 dSec = (dClock / (double)uMovesToDo);
 183                 dSec *= 0.95;
 184                 uMargin = (ULONG)(dSec * 2.2);
 185                 if (uMovesToDo <= 5)
 186                 {
 187                     dSec *= 0.75;
 188                     uMargin /= 2;
 189                 }
 190                 break;
 191             }
 192             else
 193             {
 194                 //
 195                 // Fixed time finish entire game.
 196                 //
 197 #ifdef DEBUG
 198                 Trace("SetMoveTimer: finish the game in %s sec.\n",
 199                       TimeToString(dClock));
 200 #endif
 201                 dSec = dClock / 60;
 202                 uMargin = (ULONG)(dSec * 2.2);
 203             }
 204             break;
 205
 206         //
 207         // We get back a certain number of seconds with each move made.
 208         //
 209         case CLOCK_INCREMENT:
 210             dSec = g_Options.uMyIncrement;
 211             dSec += (dClock / 50);
 212             uMargin = (int)(dSec * 2.2);
 213
 214 #ifdef DEBUG
 215             Trace("SetMoveTimer: finish the game in %s sec (+%u per move).\n",
 216                   TimeToString(dClock), g_Options.uMyIncrement);
 217 #endif
 218
 219             //
 220             // If we are running out of time, think for less than the
 221             // increment.
 222             //
 223             if (dClock < 20.0)
 224             {
 225                 dSec -= g_Options.uMyIncrement;
 226                 uMargin = 0;
 227             }
 228             ASSERT(dSec > 0);
 229             break;
 230
 231         case CLOCK_NONE:
 232 #ifdef DEBUG
 233             Trace("SetMoveTimer: no time limit, think until interrupted.\n");
 234 #endif
 235             g_MoveTimer.dHardTimeLimit = -1;
 236             g_MoveTimer.dSoftTimeLimit = -1;
 237             goto post;
 238
 239         default:
 240             ASSERT(FALSE);
 241             break;
 242     }
 243     if ((dSec + uMargin) >= (dClock * 7 / 8)) uMargin = 0;
 244     g_MoveTimer.dSoftTimeLimit = g_MoveTimer.dStartTime + dSec;
 245     g_MoveTimer.dHardTimeLimit = g_MoveTimer.dStartTime + dSec + uMargin;
 246
 247  post:
 248     if (TRUE == g_Options.fShouldPost)
 249     {
 250         if (g_MoveTimer.dSoftTimeLimit > 0)
 251         {
 252             Trace("SetMoveTimer: Soft time limit %s seconds.\n",
 253                   TimeToString(g_MoveTimer.dSoftTimeLimit -
 254                                g_MoveTimer.dStartTime));
 255             ASSERT(g_MoveTimer.dHardTimeLimit > 0);
 256             Trace("SetMoveTimer: Hard time limit %s seconds.\n",
 257                   TimeToString(g_MoveTimer.dHardTimeLimit -
 258                                g_MoveTimer.dStartTime));
 259             if (TRUE == fSwitchOver)
 260             {
 261                 Trace("SetMoveTimer: Already searched %s seconds.\n",
 262                       TimeToString(SystemTimeStamp() -
 263                                    g_MoveTimer.dStartTime));
 264             }
 265         }
 266 #ifdef DEBUG
 267         Trace("SetMoveTimer: Checking input and timer every %u nodes.\n",
 268               g_MoveTimer.uNodeCheckMask);
 269 #endif
 270     }
 271 }
 272
 273
 274 void
 275 ReInitializeSearcherContext(POSITION *pos,
 276                             SEARCHER_THREAD_CONTEXT *ctx)
 277 /**
 278
 279 Routine description:
 280
 281     Reinitializes a SEARCHER_THREAD_CONTEXT structure.
 282
 283 Parameters:
 284
 285     POSITION *pos,
 286     SEARCHER_THREAD_CONTEXT *ctx
 287
 288 Return value:
 289
 290     void
 291
 292 **/
 293 {
 294     if (NULL != pos)
 295     {
 296         memmove(&(ctx->sPosition), pos, sizeof(POSITION));
 297     }
 298     ctx->uPly = 0;
 299     ctx->uPositional = 133;
 300     memset(&(ctx->sCounters), 0, sizeof(COUNTERS));
 301 }
 302
 303
 304 void
 305 InitializeSearcherContext(POSITION *pos,
 306                           SEARCHER_THREAD_CONTEXT *ctx)
 307 /**
 308
 309 Routine description:
 310
 311     Initialize a SEARCHER_THREAD_CONTEXT structure.
 312
 313 Parameters:
 314
 315     POSITION *pos,
 316     SEARCHER_THREAD_CONTEXT *ctx
 317
 318 Return value:
 319
 320     void
 321
 322 **/
 323 {
 324     ULONG u;
 325
 326     memset(ctx, 0, sizeof(SEARCHER_THREAD_CONTEXT));
 327     ReInitializeSearcherContext(pos, ctx);
 328     ctx->sMoveStack.uUnblockedKeyValue[0] = 1;
 329     for (u = 1;
 330          u < MAX_PLY_PER_SEARCH;
 331          u++)
 332     {
 333         ctx->sMoveStack.uUnblockedKeyValue[u] =
 334             ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28;
 335     }
 336 }
 337
 338
 339 void
 340 InitializeLightweightSearcherContext(POSITION *pos,
 341                                      LIGHTWEIGHT_SEARCHER_CONTEXT *ctx)
 342 /**
 343
 344 Routine description:
 345
 346     Initialize a LIGHTWEIGHT_SEARCHER_CONTEXT structure.
 347
 348 Parameters:
 349
 350     POSITION *pos,
 351     LIGHTWEIGHT_SEARCHER_CONTEXT *ctx
 352
 353 Return value:
 354
 355     void
 356
 357 **/
 358 {
 359     ULONG u;
 360
 361     memset(ctx, 0, sizeof(LIGHTWEIGHT_SEARCHER_CONTEXT));
 362     if (NULL != pos)
 363     {
 364         memmove(&(ctx->sPosition), pos, sizeof(POSITION));
 365     }
 366     ctx->uPly = 0;
 367     ctx->uPositional = 133;
 368     ctx->sMoveStack.uUnblockedKeyValue[0] = 1;
 369     for (u = 1;
 370          u < MAX_PLY_PER_SEARCH;
 371          u++)
 372     {
 373         ctx->sMoveStack.uUnblockedKeyValue[u] =
 374             ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28;
 375     }
 376 }
 377
 378
 379 void
 380 PostMoveSearchReport(SEARCHER_THREAD_CONTEXT *ctx)
 381 /**
 382
 383 Routine description:
 384
 385     Dump a report to stdout after every move.
 386
 387 Parameters:
 388
 389     SEARCHER_THREAD_CONTEXT *ctx,
 390
 391 Return value:
 392
 393     void
 394
 395 **/
 396 {
 397     double d;
 398     char buf[256];
 399 #ifdef PERF_COUNTERS
 400     double n;
 401 #endif
 402     d = (double)g_MoveTimer.dEndTime - (double)g_MoveTimer.dStartTime + 0.01;
 403     ASSERT(d);
 404     Trace("---------------------------------------------\n"
 405           "Searched for %5.1f seconds, saw %"
 406           COMPILER_LONGLONG_UNSIGNED_FORMAT
 407           " nodes (%"
 408           COMPILER_LONGLONG_UNSIGNED_FORMAT
 409           " qnodes) (%6.0f nps).\n",
 410           d, ctx->sCounters.tree.u64TotalNodeCount,
 411           ctx->sCounters.tree.u64QNodeCount,
 412           ((double)ctx->sCounters.tree.u64TotalNodeCount / d));
 413     if (g_Options.fThinking)
 414     {
 415         snprintf(buf, ARRAY_LENGTH(buf), "d%u, %s, %3.1fs, %6.0fknps, PV=%s",
 416                  ctx->uRootDepth / ONE_PLY,
 417                  ScoreToString(ctx->iRootScore),
 418                  d,
 419                  ((double)ctx->sCounters.tree.u64TotalNodeCount / d / 1000),
 420                  ctx->szLastPV);
 421         Trace("tellothers %s\n", buf);
 422     }
 423 #ifdef MP
 424 #ifdef PERF_COUNTERS
 425     if (ctx->sCounters.parallel.uNumSplits > 0)
 426     {
 427         n = (double)ctx->sCounters.parallel.uNumSplits;
 428         Trace("Split %u times total ",
 429               ctx->sCounters.parallel.uNumSplits);
 430         Trace("(~%7.2fx/sec).\n", (n / d));
 431         d = n + 1;
 432         ASSERT(d);
 433         n = (double)ctx->sCounters.parallel.uNumSplitsTerminated;
 434         Trace("  ...%u (%5.2f percent) terminated early.\n",
 435               ctx->sCounters.parallel.uNumSplitsTerminated, ((n/d) * 100.0));
 436         DumpHelperIdlenessReport();
 437     }
 438 #endif
 439 #endif
 440
 441 #ifdef TEST
 442     AnalyzeFullHashTable();
 443 #endif
 444 #ifdef PERF_COUNTERS
 445     d = (double)(ctx->sCounters.hash.u64Probes) + 1;
 446     ASSERT(d);
 447     Trace("Hashing percentages: (%5.3f total, %5.3f useful)\n",
 448           ((double)(ctx->sCounters.hash.u64OverallHits) / d) * 100.0,
 449           ((double)(ctx->sCounters.hash.u64UsefulHits) / d) * 100.0);
 450     d = (double)(ctx->sCounters.pawnhash.u64Probes) + 1;
 451     ASSERT(d);
 452     n = (double)(ctx->sCounters.pawnhash.u64Hits);
 453     Trace("Pawn hash hitrate: %5.3f percent.\n", (n/d) * 100.0);
 454     n = (double)(ctx->sCounters.tree.u64NullMoveSuccess);
 455     d = (double)(ctx->sCounters.tree.u64NullMoves) + 1;
 456     ASSERT(d);
 457     Trace("Null move cutoff rate: %5.3f percent.\n",
 458           ((n / d) * 100.0));
 459 #ifdef TEST_ENDGAME
 460     n = (double)(ctx->sCounters.tree.u64EndgamePruningSuccess);
 461     d = n + (double)(ctx->sCounters.tree.u64EndgamePruningFailures);
 462     if (d != 0.0)
 463     {
 464         Trace("Endgame pruning heuristic success rate was %5.3f percent.\n"
 465               "Endgame pruning heuristic was "
 466               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT " / "
 467               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ".\n",
 468               ((n / d) * 100.0),
 469               ctx->sCounters.tree.u64EndgamePruningSuccess,
 470               (ctx->sCounters.tree.u64EndgamePruningSuccess +
 471                ctx->sCounters.tree.u64EndgamePruningFailures));
 472     }
 473     else
 474     {
 475         Trace("Never used endgame pruning heuristic.\n");
 476     }
 477 #endif
 478 #ifdef TEST_NULL
 479     n = (double)(ctx->sCounters.tree.u64AvoidNullSuccess);
 480     d = n + (double)(ctx->sCounters.tree.u64AvoidNullFailures);
 481     if (d != 0.0)
 482     {
 483         Trace("Avoid null move heuristic rate was %5.3f percent.\n"
 484               "Avoid null move heuristic was "
 485               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT " / "
 486               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ".\n",
 487               ((n / d) * 100.0),
 488               ctx->sCounters.tree.u64AvoidNullSuccess,
 489               (ctx->sCounters.tree.u64AvoidNullSuccess +
 490                ctx->sCounters.tree.u64AvoidNullFailures));
 491     }
 492     else
 493     {
 494         Trace("Never used the avoid null move heuristic.\n");
 495     }
 496     n = (double)(ctx->sCounters.tree.u64QuickNullSuccess);
 497     n += (double)(ctx->sCounters.tree.u64QuickNullDeferredSuccess);
 498     d = n + (double)(ctx->sCounters.tree.u64QuickNullFailures);
 499     if (d != 0.0)
 500     {
 501         Trace("Quick null move heuristic rate was %5.3f percent.\n"
 502               "Quick null move heuristic rate was "
 503               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT " ("
 504               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ") / "
 505               "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ".\n",
 506               ((n / d) * 100.0),
 507               ctx->sCounters.tree.u64QuickNullSuccess,
 508               ctx->sCounters.tree.u64QuickNullDeferredSuccess,
 509               (ctx->sCounters.tree.u64QuickNullSuccess +
 510                ctx->sCounters.tree.u64QuickNullDeferredSuccess +
 511                ctx->sCounters.tree.u64QuickNullFailures));
 512     }
 513     else
 514     {
 515         Trace("Never used the quick null move heuristic.\n");
 516     }
 517 #endif
 518     n = (double)ctx->sCounters.tree.u64BetaCutoffsOnFirstMove;
 519     d = (double)ctx->sCounters.tree.u64BetaCutoffs + 1;
 520     Trace("First move beta cutoff rate was %5.3f percent.\n",
 521           ((n / d) * 100.0));
 522 #ifdef LAZY_EVAL
 523     d = (double)ctx->sCounters.tree.u64LazyEvals;
 524     d += (double)ctx->sCounters.tree.u64FullEvals;
 525     d += (double)ctx->sCounters.tree.u64EvalHashHits;
 526     d += 1;
 527     ASSERT(d);
 528     Trace("Eval percentages: (%5.2f hash, %5.2f lazy, %5.2f full)\n",
 529           ((double)ctx->sCounters.tree.u64EvalHashHits / d) * 100.0,
 530           ((double)ctx->sCounters.tree.u64LazyEvals / d) * 100.0,
 531           ((double)ctx->sCounters.tree.u64FullEvals / d) * 100.0);
 532 #endif
 533     Trace("Extensions: (%u +, %u q+, %u 1mv, %u !kmvs, %u mult+, %u pawn\n"
 534           "             %u threat, %u zug, %u sing, %u endg, %u bm, %u recap)\n",
 535           ctx->sCounters.extension.uCheck,
 536           ctx->sCounters.extension.uQExtend,
 537           ctx->sCounters.extension.uOneLegalMove,
 538           ctx->sCounters.extension.uNoLegalKingMoves,
 539           ctx->sCounters.extension.uMultiCheck,
 540           ctx->sCounters.extension.uPawnPush,
 541           ctx->sCounters.extension.uMateThreat,
 542           ctx->sCounters.extension.uZugzwang,
 543           ctx->sCounters.extension.uSingularReplyToCheck,
 544           ctx->sCounters.extension.uEndgame,
 545           ctx->sCounters.extension.uBotvinnikMarkoff,
 546           ctx->sCounters.extension.uRecapture);
 547 #ifdef EVAL_TIME
 548     n = (double)ctx->sCounters.tree.u64CyclesInEval;
 549     Trace("Avg. cpu cycles in eval: %8.1f.\n", (n / d));
 550 #endif
 551 #endif
 552 }
 553
 554
 555 SCORE
 556 RootSearch(SEARCHER_THREAD_CONTEXT *ctx,
 557            SCORE iAlpha,
 558            SCORE iBeta,
 559            ULONG uDepth)
 560 /**
 561
 562 Routine description:
 563
 564     Search at the root of the whole tree.
 565
 566 Parameters:
 567
 568     SEARCHER_THREAD_CONTEXT *ctx,
 569     SCORE iAlpha,
 570     SCORE iBeta,
 571     ULONG uDepth,
 572
 573 Return value:
 574
 575     SCORE
 576
 577 **/
 578 {
 579     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
 580     SCORE iBestScore = -INFINITY;
 581     SCORE iInitialAlpha = iAlpha;
 582     MOVE mv;
 583     ULONG x, y;
 584     SCORE iScore;
 585     ULONG uNextDepth;
 586     UINT64 u64StartingNodeCount;
 587     ULONG uNumLegalMoves;
 588
 589 #ifdef DEBUG
 590         POSITION *pos = &ctx->sPosition;
 591     ASSERT(IS_VALID_SCORE(iAlpha));
 592     ASSERT(IS_VALID_SCORE(iBeta));
 593     ASSERT(iAlpha < iBeta);
 594     ASSERT((ctx->uPly == 0) || (ctx->uPly == 1)); // 1 is for under a ponder
 595     memcpy(&pi->sPosition, pos, sizeof(POSITION));
 596 #endif
 597
 598     ctx->sCounters.tree.u64TotalNodeCount++;
 599     pi->PV[ctx->uPly] = NULLMOVE;
 600     pi->mvBest = NULLMOVE;
 601     g_MoveTimer.bvFlags |= TIMER_SEARCHING_FIRST_MOVE;
 602 #ifdef DEBUG
 603     Trace("---- depth=%u, a=%d, b=%d ----\n", uDepth / ONE_PLY, iAlpha, iBeta);
 604 #endif
 605
 606     uNumLegalMoves = 0;
 607     for (x = ctx->sMoveStack.uBegin[ctx->uPly];
 608          x < ctx->sMoveStack.uEnd[ctx->uPly];
 609          x++)
 610     {
 611         SelectMoveAtRoot(ctx, x);
 612         if (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED) break;
 613         ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED;
 614         mv = ctx->sMoveStack.mvf[x].mv;
 615         mv.bvFlags |= WouldGiveCheck(ctx, mv);
 616
 617         if (MakeMove(ctx, mv))
 618         {
 619             uNumLegalMoves++;
 620             u64StartingNodeCount = ctx->sCounters.tree.u64TotalNodeCount;
 621
 622             //
 623             // TODO: Fancy recap shit here?
 624             //
 625
 626             uNextDepth = uDepth - ONE_PLY;
 627             if (IS_CHECKING_MOVE(mv))
 628             {
 629                 uNextDepth += HALF_PLY;
 630                 ctx->sPlyInfo[ctx->uPly].iExtensionAmount = HALF_PLY;
 631             }
 632
 633             ctx->sSearchFlags.fVerifyNullmove = TRUE;
 634             ctx->sSearchFlags.uQsearchDepth = 0;
 635             if (uNumLegalMoves == 1)
 636             {
 637                 //
 638                 // Move 1, full a..b window
 639                 //
 640                 iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
 641             }
 642             else
 643             {
 644                 //
 645                 // Moves 2..N, minimal window search
 646                 //
 647                 ASSERT(x > 0);
 648                 ASSERT(uNumLegalMoves > 1);
 649                 iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uNextDepth);
 650                 if ((iAlpha < iScore) && (iScore < iBeta))
 651                 {
 652                     iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
 653                 }
 654             }
 655             ctx->sSearchFlags.fVerifyNullmove = FALSE;
 656             UnmakeMove(ctx, mv);
 657             if (WE_SHOULD_STOP_SEARCHING)
 658             {
 659                 iBestScore = INVALID_SCORE;
 660                 goto end;
 661             }
 662 #ifdef DEBUG
 663             Trace("%2u. %-8s => node=%" COMPILER_LONGLONG_UNSIGNED_FORMAT
 664                   ", predict=%d, actual=%d, ",
 665                   x + 1,
 666                   MoveToSan(mv, &ctx->sPosition),
 667                   u64StartingNodeCount,
 668                   ctx->sMoveStack.mvf[x].iValue,
 669                   iScore);
 670             ASSERT(PositionsAreEquivalent(&pi->sPosition, &ctx->sPosition));
 671 #endif
 672             //
 673             // Keep track of how many moves are under each one we
 674             // search and use this as the basis for root move ordering
 675             // next iteration.
 676             //
 677             u64StartingNodeCount = (ctx->sCounters.tree.u64TotalNodeCount -
 678                                     u64StartingNodeCount);
 679             u64StartingNodeCount >>= 9;
 680             u64StartingNodeCount &= (MAX_INT / 4);
 681             ctx->sMoveStack.mvf[x].iValue =
 682                 (SCORE)(u64StartingNodeCount + iScore);
 683 #ifdef DEBUG
 684             Trace("next_predict: %d\n", ctx->sMoveStack.mvf[x].iValue);
 685             ASSERT(iBestScore <= iAlpha);
 686             ASSERT(iAlpha < iBeta);
 687 #endif
 688             if (iScore > iBestScore)
 689             {
 690                 iBestScore = iScore;
 691                 pi->mvBest = mv;
 692                 if (iScore > iAlpha)
 693                 {
 694                     //
 695                     // We have a best move so far.  As of now it is
 696                     // the one we'll be playing.  Also make sure to
 697                     // search it first at the next depth.
 698                     //
 699 #ifdef DEBUG
 700                     Trace("Best so far... root score=%d.\n", iScore);
 701 #endif
 702                     ctx->mvRootMove = mv;
 703                     ctx->iRootScore = iScore;
 704                     ctx->uRootDepth = uDepth;
 705                     ctx->sMoveStack.mvf[x].iValue = MAX_INT;
 706
 707                     //
 708                     // If there was a previous PV move then knock its
 709                     // score down so that it will be considered second
 710                     // on the next depth.
 711                     //
 712                     for (y = ctx->sMoveStack.uBegin[ctx->uPly];
 713                          y < x;
 714                          y++)
 715                     {
 716                         if (ctx->sMoveStack.mvf[y].iValue == MAX_INT)
 717                         {
 718                             ctx->sMoveStack.mvf[y].iValue /= 2;
 719                         }
 720                     }
 721
 722                     UpdatePV(ctx, mv);
 723                     if (iScore >= iBeta)
 724                     {
 725                         //
 726                         // Root fail high...
 727                         //
 728                         UpdateDynamicMoveOrdering(ctx,
 729                                                   uDepth,
 730                                                   mv,
 731                                                   iScore,
 732                                                   x + 1);
 733                         UtilPrintPV(ctx, iAlpha, iBeta, iScore, mv);
 734                         KEEP_TRACK_OF_FIRST_MOVE_FHs(iBestScore == -INFINITY);
 735                         ctx->sMoveStack.mvf[x].bvFlags &= ~MVF_MOVE_SEARCHED;
 736                         goto end;
 737                     }
 738                     else
 739                     {
 740                         //
 741                         // Root PV change...
 742                         //
 743                         UtilPrintPV(ctx, iAlpha, iBeta, iScore, mv);
 744                         iAlpha = iScore;
 745                     }
 746                                 }
 747             }
 748             g_MoveTimer.bvFlags &= ~TIMER_SEARCHING_FIRST_MOVE;
 749         }
 750     }
 751
 752     if (iAlpha == iInitialAlpha)
 753     {
 754         //
 755         // Root fail low...
 756         //
 757         ASSERT(iBestScore <= iAlpha);
 758         ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
 759         UtilPrintPV(ctx, iAlpha, iBeta, iBestScore, mv);
 760     }
 761
 762  end:
 763     return(iBestScore);
 764 }
 765
 766
 767
 768 static GAME_RESULT
 769 _DetectPreMoveTerminalStates(SEARCHER_THREAD_CONTEXT *ctx,
 770                              FLAG fInCheck,
 771                              MOVE *pmv) {
 772     ULONG u;
 773     MOVE mv;
 774     MOVE mvLegal;
 775     ULONG uNumLegal = 0;
 776     GAME_RESULT ret;
 777     POSITION *pos = &ctx->sPosition;
 778     ULONG uMajors[2], uMinors[2], uWhiteBishops[2], uBlackBishops[2];
 779
 780     ret.eResult = RESULT_IN_PROGRESS;
 781     ret.szDescription[0] = '\0';
 782     pmv->uMove = 0;
 783
 784     // Look for insufficient material.
 785     FOREACH_COLOR(u) {
 786         uMajors[u] = (pos->uNonPawnCount[u][ROOK] +
 787                       pos->uNonPawnCount[u][QUEEN]);
 788         uMinors[u] = (pos->uNonPawnCount[u][KNIGHT] +
 789                       pos->uNonPawnCount[u][BISHOP]);
 790         uWhiteBishops[u] = pos->uWhiteSqBishopCount[u];
 791         uBlackBishops[u] = pos->uNonPawnCount[u][BISHOP] - uWhiteBishops[u];
 792     }
 793     FOREACH_COLOR(u) {
 794         if ((pos->uPawnCount[u] != 0) ||
 795             (pos->uPawnCount[FLIP(u)] != 0)) {
 796               continue;
 797         }
 798         if (pos->uNonPawnCount[u][0] == 1) {
 799             if (uMajors[FLIP(u)] == 0 &&
 800                 uMinors[FLIP(u)] == 1) {
 801                 ret.eResult = RESULT_DRAW;
 802                 strcpy(ret.szDescription, "insufficient material");
 803                 return ret;
 804             } else if (uMajors[FLIP(u)] == 0 &&
 805                        (uMinors[FLIP(u)] == uWhiteBishops[FLIP(u)] ||
 806                         uMinors[FLIP(u)] == uBlackBishops[FLIP(u)])) {
 807                 ret.eResult = RESULT_DRAW;
 808                 strcpy(ret.szDescription, "insufficient material");
 809                 return ret;
 810             }
 811         } else if ((pos->uNonPawnCount[u][0] == 1 + uWhiteBishops[u] &&
 812                    pos->uNonPawnCount[FLIP(u)][0] ==
 813                    1 + uWhiteBishops[FLIP(u)]) ||
 814                    (pos->uNonPawnCount[u][0] == 1 + uBlackBishops[u] &&
 815                     pos->uNonPawnCount[FLIP(u)][0] ==
 816                     1 + uBlackBishops[FLIP(u)])) {
 817             ret.eResult = RESULT_DRAW;
 818             strcpy(ret.szDescription, "insufficient material");
 819             return ret;
 820         }
 821     }
 822
 823     // Count the number of legal moves the side on move has in this position.
 824     for (u = ctx->sMoveStack.uBegin[ctx->uPly];
 825          u < ctx->sMoveStack.uEnd[ctx->uPly];
 826          u++) {
 827         mv = ctx->sMoveStack.mvf[u].mv;
 828         if (MakeMove(ctx, mv)) {
 829             mvLegal = mv;
 830             uNumLegal += 1;
 831             UnmakeMove(ctx, mv);
 832             if (uNumLegal > 1) {
 833                 return ret;
 834             }
 835         }
 836     }
 837
 838     // If there's only one legal move then tell the caller what it is.
 839     if (uNumLegal == 1) {
 840         *pmv = mvLegal;
 841         return ret;
 842     }
 843
 844     // There are no legal moves so its checkmate or stalemate.
 845     ASSERT(uNumLegal == 0);
 846     if (TRUE == fInCheck) {
 847       if (ctx->sPosition.uToMove == WHITE) {
 848         ret.eResult = RESULT_BLACK_WON;
 849         strcpy(ret.szDescription, "black checkmated white");
 850         return ret;
 851       }
 852       ret.eResult = RESULT_WHITE_WON;
 853       strcpy(ret.szDescription, "white checkmated black");
 854       return ret;
 855     }
 856     ret.eResult = RESULT_DRAW;
 857     sprintf(ret.szDescription, "%s stalemated %s",
 858             (ctx->sPosition.uToMove == WHITE) ? "black" : "white",
 859             (ctx->sPosition.uToMove == WHITE) ? "while" : "black");
 860     return ret;
 861 }
 862
 863
 864
 865 static GAME_RESULT
 866 _DetectPostMoveTerminalStates(SEARCHER_THREAD_CONTEXT *ctx)
 867 /**
 868
 869 Routine description:
 870
 871     This function is called by Iterate and MakeTheMove to declare
 872     wins/losses/draws.
 873
 874 Parameters:
 875
 876     SEARCHER_THREAD_CONTEXT *ctx
 877
 878 Return value:
 879
 880     FLAG
 881
 882 **/
 883 {
 884     GAME_RESULT ret;
 885     FLAG fInCheck = InCheck(&ctx->sPosition, ctx->sPosition.uToMove);
 886
 887     // Did we just make the 50th+ move without progress?
 888     if (ctx->sPosition.uFifty >= 100) {
 889         ret.eResult = RESULT_DRAW;
 890         strcpy(ret.szDescription, "fifty moves without progress");
 891         return ret;
 892     }
 893     GenerateMoves(ctx, NULLMOVE, (fInCheck ? GENERATE_ESCAPES :
 894                                              GENERATE_ALL_MOVES));
 895
 896     // Did we just repeat a position for the 3rd time?
 897     if (IsLegalDrawByRepetition()) {
 898         ret.eResult = RESULT_DRAW;
 899         strcpy(ret.szDescription, "third repetition of position");
 900         return ret;
 901     }
 902
 903     // Otherwise look for checkmates, stalemates and insufficient material.
 904     MOVE mvUnused;
 905     return _DetectPreMoveTerminalStates(ctx,
 906                                         fInCheck,
 907                                         &mvUnused);
 908 }
 909
 910
 911 static void
 912 _IterateSetSearchGlobals(ULONG uDepth)
 913 {
 914     ULONG u, v;
 915     ULONG uDontSplitLessThan;
 916
 917     //
 918     // Set some globals that will be used throughout this search.
 919     //
 920     g_uIterateDepth = uDepth;
 921     ASSERT(g_uIterateDepth > 0);
 922     ASSERT(g_uIterateDepth < MAX_PLY_PER_SEARCH);
 923
 924     //
 925     // For use in scaling back extensions that are very far from
 926     // the root.
 927     //
 928     //          Iterate   g_Soft              g_Hard
 929     //   |    |    |    |    |    |    |    |    |
 930     //   0         1         2   2.5   3   3.5   4       (x Iterate)
 931     //   |-------------------|----|----|---------|----...
 932     //   |full full full full|-1/4|-1/2|-3/4 -3/4|none...
 933     //
 934     g_uSoftExtendLimit = g_uIterateDepth * 2;
 935     g_uHardExtendLimit = g_uIterateDepth * 4;
 936     for (u = 0; u < MAX_PLY_PER_SEARCH; u++)
 937     {
 938         if (u < g_uSoftExtendLimit)
 939         {
 940             g_uExtensionReduction[u] = 0;
 941         }
 942         else if (u < (g_uSoftExtendLimit + g_uIterateDepth / 2))
 943         {
 944             g_uExtensionReduction[u] = QUARTER_PLY;
 945         }
 946         else if (u < (g_uSoftExtendLimit + g_uIterateDepth))
 947         {
 948             g_uExtensionReduction[u] = HALF_PLY;
 949         }
 950         else if (u < g_uHardExtendLimit)
 951         {
 952             g_uExtensionReduction[u] = THREE_QUARTERS_PLY;
 953         }
 954         else
 955         {
 956             g_uExtensionReduction[u] = 5 * ONE_PLY;
 957         }
 958     }
 959
 960     //
 961     // Determine how much depth we need below a point in the tree in
 962     // order to split the search (which is based on iteration depth).
 963     //
 964     uDontSplitLessThan = (ULONG)((double)(uDepth) * 0.30);
 965     for (v = 0; v < MAX_PLY_PER_SEARCH; v++)
 966     {
 967         g_fCanSplit[v] = ((v + 1) >= uDontSplitLessThan);
 968     }
 969         g_fCanSplit[0] = FALSE;
 970 }
 971
 972
 973 #define SKIP_GRADUAL_OPENING 600
 974 #define INITIAL_HALF_WINDOW  75
 975 #define FIRST_FAIL_STEP      150
 976 #define SECOND_FAIL_STEP     375
 977
 978 void
 979 _IterateWidenWindow(ULONG uColor,
 980                     SCORE iScore,
 981                     SCORE *piBound,
 982                     ULONG *puState,
 983                     int iDir)
 984 {
 985     SCORE iRoughScore = g_iRootScore[uColor];
 986     static SCORE _Steps[] =
 987     {
 988         FIRST_FAIL_STEP,
 989         SECOND_FAIL_STEP,
 990         INFINITY
 991     };
 992
 993 //    Trace("State = %u.\n", *puState);
 994 //    Trace("Bound from %d to ", *piBound);
 995     if ((abs(iRoughScore - iScore) > SKIP_GRADUAL_OPENING) ||
 996         (*puState == 2))
 997     {
 998         *piBound = iDir * INFINITY;
 999         *puState = 2;
1000     }
1001     else
1002     {
1003         ASSERT(*puState < 2);
1004         *piBound = iScore;
1005         *piBound += iDir * _Steps[*puState];
1006         *puState += 1;
1007     }
1008 //    Trace("%d.\n", *piBound);
1009 //    Trace("State = %u\n", *puState);
1010 }
1011
1012
1013 GAME_RESULT Iterate(SEARCHER_THREAD_CONTEXT *ctx)
1014 /**
1015
1016 Routine description:
1017
1018     Main iterative deepening loop for both thinking and pondering.
1019     Call RootSearch with progressively deeper depths while there is
1020     remaining time, we haven't found a forced mate, and there's no
1021     user interruption.
1022
1023 Parameters:
1024
1025     SEARCHER_THREAD_CONTEXT *ctx
1026
1027 Return value:
1028
1029     FLAG : is the game over?
1030
1031 **/
1032 {
1033     ULONG uNumRootFailLows = 0;
1034     ULONG uDepth;
1035     ULONG uFailState = 0;
1036     ULONG uColor;
1037     ULONG u;
1038     SCORE iAlpha = -INFINITY;
1039     SCORE iBeta = +INFINITY;
1040     SCORE iScore;
1041     FLAG fInCheck = InCheck(&(ctx->sPosition), ctx->sPosition.uToMove);
1042     MOVE mv;
1043     GAME_RESULT ret;
1044 #ifdef DEBUG
1045     POSITION board;
1046     memcpy(&board, &(ctx->sPosition), sizeof(POSITION));
1047     VerifyPositionConsistency(&board, FALSE);
1048 #endif
1049
1050     uColor = ctx->sPosition.uToMove;
1051     g_iRootScore[uColor] = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE);
1052     g_iRootScore[FLIP(uColor)] = -g_iRootScore[uColor];
1053
1054     //
1055     // Generate moves here so that RootSearch doesn't have to.
1056     //
1057     ASSERT((ctx->uPly == 0) || (ctx->uPly == 1)); // 1 is under a ponder
1058     ctx->sPlyInfo[ctx->uPly].fInCheck = fInCheck;
1059     GenerateMoves(ctx, NULLMOVE, (fInCheck ? GENERATE_ESCAPES :
1060                                              GENERATE_ALL_MOVES));
1061     ASSERT(ctx->sMoveStack.uBegin[0] == 0);
1062
1063     //
1064     // See if we are sitting at a checkmate or stalemate position; no
1065     // sense searching if so.
1066     //
1067     ret = _DetectPreMoveTerminalStates(ctx,
1068                                        fInCheck,
1069                                        &mv);
1070     if (ret.eResult != RESULT_IN_PROGRESS) {
1071         goto end;
1072     }
1073
1074     // Game still in progress but only one legal move available?
1075     if (mv.uMove != 0) {
1076         ctx->mvRootMove = mv;
1077         ctx->iRootScore = 0;
1078         ctx->uRootDepth = 0;
1079         ctx->sPlyInfo[0].PV[0] = mv;
1080         ctx->sPlyInfo[0].PV[1] = NULLMOVE;
1081         strcpy(ctx->szLastPV, "only");
1082         if (!g_Options.fPondering) {
1083             Trace("ONLY MOVE --> stop searching now\n");
1084             g_MoveTimer.bvFlags |= TIMER_STOPPING;
1085             g_MoveTimer.bvFlags |= TIMER_CURRENT_OBVIOUS;
1086         } else {
1087             Trace("ONLY PONDER --> move immediately if prediction correct.\n");
1088             g_MoveTimer.bvFlags |= TIMER_MOVE_IMMEDIATELY;
1089             g_MoveTimer.bvFlags |= TIMER_CURRENT_OBVIOUS;
1090         }
1091         goto end;
1092     }
1093
1094     for (uDepth = 1;
1095          uDepth <= g_Options.uMaxDepth;
1096          uDepth++)
1097     {
1098         //
1099         // Re-rank the moves based on nodecounts and mark all moves as
1100         // not yet searched at this depth.
1101         //
1102         for (u = ctx->sMoveStack.uBegin[ctx->uPly];
1103              u < ctx->sMoveStack.uEnd[ctx->uPly];
1104              u++)
1105         {
1106             ctx->sMoveStack.mvf[u].bvFlags &= ~MVF_MOVE_SEARCHED;
1107         }
1108
1109         //
1110         // Make sure a..b window makes sense and set some other per-depth
1111         // globals used by the search.
1112         //
1113         _IterateSetSearchGlobals(uDepth);
1114
1115         //
1116         // Try to get a PV for this depth before we're out of time...
1117         //
1118         do
1119         {
1120             if (iBeta > INFINITY) iBeta = +INFINITY;
1121             if (iAlpha < -INFINITY) iAlpha = -INFINITY;
1122             if (iAlpha >= iBeta) iAlpha = iBeta - 1;
1123             iScore = RootSearch(ctx,
1124                                 iAlpha,
1125                                 iBeta,
1126                                 uDepth * ONE_PLY + HALF_PLY);
1127             if (g_MoveTimer.bvFlags & TIMER_STOPPING) break;
1128             mv = ctx->mvRootMove;
1129
1130             //
1131             // Got a PV, we're done with this depth.
1132             //
1133             if ((iAlpha < iScore) && (iScore < iBeta))
1134             {
1135                 ASSERT(iScore == ctx->iRootScore);
1136                 ASSERT(mv.uMove);
1137                 ASSERT(SanityCheckMove(&ctx->sPosition, mv));
1138                 iAlpha = iScore - INITIAL_HALF_WINDOW;
1139                 iBeta = iScore + INITIAL_HALF_WINDOW;
1140                 g_iRootScore[uColor] = iScore;
1141                 g_iRootScore[FLIP(uColor)] = -iScore;
1142                 g_MoveTimer.bvFlags &= ~TIMER_RESOLVING_ROOT_FH;
1143                 g_MoveTimer.bvFlags &= ~TIMER_RESOLVING_ROOT_FL;
1144                 uFailState = 0;
1145                 (void)CheckTestSuiteMove(mv, iScore, uDepth);
1146                 break;
1147             }
1148
1149             //
1150             // Root fail low?  We'll have to research with a wider
1151             // window.
1152             //
1153             else if (iScore <= iAlpha)
1154             {
1155                 ASSERT(ctx->mvRootMove.uMove);
1156                 g_MoveTimer.bvFlags |= TIMER_RESOLVING_ROOT_FL;
1157                 uNumRootFailLows++;
1158                 if (uNumRootFailLows > 3)
1159                 {
1160                     g_MoveTimer.bvFlags |= TIMER_MANY_ROOT_FLS;
1161                 }
1162                 _IterateWidenWindow(uColor, iScore, &iAlpha, &uFailState, -1);
1163
1164                 //
1165                 // Consider all moves again with wider window...
1166                 //
1167                 for (u = ctx->sMoveStack.uBegin[ctx->uPly];
1168                      u < ctx->sMoveStack.uEnd[ctx->uPly];
1169                      u++)
1170                 {
1171                     ctx->sMoveStack.mvf[u].bvFlags &= ~MVF_MOVE_SEARCHED;
1172                 }
1173             }
1174
1175             //
1176             // Must be a root fail high.
1177             //
1178             else
1179             {
1180                 ASSERT(iScore >= iBeta);
1181                 ASSERT(mv.uMove);
1182                 ASSERT(SanityCheckMove(&ctx->sPosition, mv));
1183                 g_MoveTimer.bvFlags |= TIMER_RESOLVING_ROOT_FH;
1184                 _IterateWidenWindow(uColor, iScore, &iBeta, &uFailState, +1);
1185             }
1186         }
1187         while(1); // repeat until we run out of time or fall inside a..b
1188
1189         //
1190         // We are here because either:
1191         //
1192         //    1. we completed a search depth,
1193         // or 2. we ran out of time,
1194         // or 3. there is one legal move and we want to make it immediately,
1195         // or 4. there was user input and we unrolled the search.
1196         //
1197
1198         //
1199         // TODO: Scale back history between iterative depths?
1200         //
1201
1202         //
1203         // Mate-in-n when we have searched n?  Stop searching.
1204         //
1205         if (IS_VALID_SCORE(iScore) &&
1206             (ULONG)abs(iScore) >= (INFINITY - uDepth))
1207         {
1208             Trace("FORCED MATE --> stop searching now\n");
1209             g_MoveTimer.bvFlags |= TIMER_STOPPING;
1210         }
1211
1212         //
1213         // Have we reached user's maxdepth option?  Stop searching.
1214         //
1215         if (uDepth >= g_Options.uMaxDepth)
1216         {
1217             Trace("DEPTH LIMIT --> stop searching now\n");
1218             g_MoveTimer.bvFlags |= TIMER_STOPPING;
1219         }
1220
1221         //
1222         // Did the move timer expire?  Stop searching.
1223         //
1224         if (g_MoveTimer.bvFlags & TIMER_STOPPING) break;
1225     }
1226     g_Options.u64NodesSearched = ctx->sCounters.tree.u64TotalNodeCount;
1227     g_MoveTimer.dEndTime = SystemTimeStamp();
1228
1229     //
1230     // Here we are at the end of a search.  If we were:
1231     //
1232     // ...Searching then:               ...Pondering then:
1233     //
1234     // 1. we ran out of time            1. they made a different move than
1235     //                                     the predicted move and we aborted
1236     // 2. we ran out of depth
1237     //                                  2. we ran out of depth
1238     // 3. we found a mate-in-n
1239     //                                  3. we found a mate-in-n
1240     // TODO: node count limit?
1241     //                                 (4. if they made the predicted move
1242     //                                     then we converted to a search)
1243     //
1244     ASSERT(ctx->mvRootMove.uMove);
1245     ASSERT(SanityCheckMove(&board, ctx->mvRootMove));
1246     if (g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FL)
1247     {
1248         ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly] = ctx->mvRootMove;
1249         ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly+1] = NULLMOVE;
1250     }
1251     ret.eResult = RESULT_IN_PROGRESS;
1252     ret.szDescription[0] = '\0';
1253  end:
1254     return ret;
1255 }
1256
1257 void
1258 MakeTheMove(SEARCHER_THREAD_CONTEXT *ctx)
1259 /**
1260
1261 Routine description:
1262
1263     Make the move that search selected in the official game list.
1264
1265 Parameters:
1266
1267     SEARCHER_THREAD_CONTEXT *ctx
1268
1269 Return value:
1270
1271     FLAG
1272
1273 **/
1274 {
1275     MOVE mv = ctx->mvRootMove;
1276     ASSERT(mv.uMove);
1277
1278     if (TRUE == g_Options.fThinking)
1279     {
1280         //
1281         // TODO: keep track of how many moves in a row we are at or
1282         // below a draw score and use this to respond to draw offers.
1283         //
1284
1285         //
1286         // Was this a search that converted from a ponder?
1287         //
1288         if (TRUE == g_Options.fSuccessfulPonder)
1289         {
1290             if (FALSE == OfficiallyMakeMove(g_Options.mvPonder, 0, FALSE))
1291             {
1292                 UtilPanic(CANNOT_OFFICIALLY_MAKE_MOVE,
1293                           GetRootPosition(),
1294                           (void *)g_Options.mvPonder.uMove,
1295                           NULL,
1296                           NULL,
1297                           __FILE__,
1298                           __LINE__);
1299             }
1300             g_Options.fSuccessfulPonder = FALSE;
1301         }
1302
1303         // Only do d2d4 stuff if we're under xboard -- it's the standard.
1304         if (g_Options.fRunningUnderXboard) {
1305             Trace("move %s\n", MoveToIcs(mv));
1306         } else {
1307             Trace("move %s\n", MoveToSan(mv, &ctx->sPosition));
1308         }
1309
1310         if (FALSE == OfficiallyMakeMove(mv, g_iScore, FALSE))
1311         {
1312             UtilPanic(CANNOT_OFFICIALLY_MAKE_MOVE,
1313                       GetRootPosition(),
1314                       (void *)mv.uMove,
1315                       NULL,
1316                       NULL,
1317                       __FILE__,
1318                       __LINE__);
1319         }
1320         if (g_Options.fVerbosePosting)
1321         {
1322             PostMoveSearchReport(ctx);
1323             PostMoveTestSuiteReport(ctx);
1324         }
1325     }
1326     g_Options.fPondering = g_Options.fThinking = FALSE;
1327 }
1328
1329
1330 GAME_RESULT
1331 Ponder(POSITION *pos)
1332 /**
1333
1334 Routine description:
1335
1336     Prepare to ponder.
1337
1338 Parameters:
1339
1340     POSITION *pos
1341
1342 Return value:
1343
1344     FLAG
1345
1346 **/
1347 {
1348     static SEARCHER_THREAD_CONTEXT ctx;
1349     GAME_RESULT ret;
1350
1351     InitializeSearcherContext(pos, &ctx);
1352     g_Options.fPondering = TRUE;
1353     g_Options.fThinking = FALSE;
1354     g_Options.fSuccessfulPonder = FALSE;
1355     ret.eResult = RESULT_IN_PROGRESS;
1356     ret.szDescription[0] = '\0';
1357
1358     //
1359     // When do we not want to ponder
1360     //
1361     if ((g_Options.ePlayMode == FORCE_MODE) || (g_Options.uMyClock < 10))
1362     {
1363         g_Options.fPondering = FALSE;
1364         return ret;
1365     }
1366
1367     //
1368     // What should we ponder?
1369     //
1370     g_Options.mvPonder = GetPonderMove(pos);
1371     if (g_Options.mvPonder.uMove == 0)
1372     {
1373         g_Options.fPondering = FALSE;
1374         return ret;
1375     }
1376     ASSERT(SanityCheckMove(pos, g_Options.mvPonder));
1377
1378     //
1379     // Prepare to ponder by doing some maintenance on the dynamic move
1380     // ordering scheme counters, changing the dirty tag in the hash
1381     // code, and clearing the root nodes-per-move hash.
1382     //
1383     MaintainDynamicMoveOrdering();
1384     DirtyHashTable();
1385
1386     //
1387     // Make the move ponder move.
1388     //
1389     if (FALSE == MakeMove(&ctx, g_Options.mvPonder))
1390     {
1391         ASSERT(FALSE);
1392         g_Options.fPondering = FALSE;
1393         return ret;
1394     }
1395
1396     //
1397     // TODO: probe the book
1398     //
1399
1400     _SetMoveTimerForPonder();
1401
1402     //
1403     // TODO: Any preEval?
1404     //
1405
1406     //
1407     // TODO: Set draw value
1408     //
1409
1410     MakeStatusLine();
1411 #if (PERF_COUNTERS && MP)
1412     ClearHelperThreadIdleness();
1413 #endif
1414     ASSERT(ctx.uPly == 1);
1415     ret = Iterate(&ctx);
1416     ASSERT(ctx.uPly == 1);
1417     if (ret.eResult == RESULT_IN_PROGRESS) {
1418         MakeTheMove(&ctx);
1419         return _DetectPostMoveTerminalStates(&ctx);
1420     } else {
1421         return ret;
1422     }
1423 }
1424
1425
1426 GAME_RESULT Think(POSITION *pos)
1427 /**
1428
1429 Routine description:
1430
1431     Prepare to think.
1432
1433 Parameters:
1434
1435     POSITION *pos
1436
1437 Return value:
1438
1439     FLAG
1440
1441 **/
1442 {
1443     static SEARCHER_THREAD_CONTEXT ctx;
1444     static ULONG _resign_count = 0;
1445     MOVE mvBook;
1446           CHAR *p;
1447
1448     InitializeSearcherContext(pos, &ctx);
1449     g_MoveTimer.bvFlags = 0;
1450     g_Options.fPondering = FALSE;
1451     g_Options.fThinking = TRUE;
1452     g_Options.fSuccessfulPonder = FALSE;
1453
1454     //
1455     // Prepare to think by doing some maintenance on the dynamic move
1456     // ordering scheme counters, changing the dirty tag in the hash
1457     // code, and clearing the root nodes-per-move hash.
1458     //
1459     if (NULL != (p = PositionToFen(&(ctx.sPosition))))
1460     {
1461         Trace("The root position is: %s\n", p);
1462         SystemFreeMemory(p);
1463     }
1464     MaintainDynamicMoveOrdering();
1465     DirtyHashTable();
1466
1467     //
1468     // Check the opening book, maybe it has a move for us.
1469     //
1470     if (g_uBookProbeFailures < 3 &&
1471         !WeAreRunningASuite() &&
1472         g_Options.szBookName[0] != '\0') {
1473         mvBook = BookMove(pos, BOOKMOVE_SELECT_MOVE);
1474         if (mvBook.uMove == 0)
1475         {
1476             g_uBookProbeFailures++;
1477         }
1478         else
1479         {
1480             g_uBookProbeFailures = 0;
1481             ASSERT(SanityCheckMove(pos, mvBook));
1482             ctx.mvRootMove = mvBook;
1483             MakeTheMove(&ctx);
1484             return _DetectPostMoveTerminalStates(&ctx);
1485         }
1486     }
1487
1488     //
1489     // TODO: Any preEval?
1490     //
1491
1492     //
1493     // Set time limit for move
1494     //
1495     SetMoveTimerForSearch(FALSE, pos->uToMove);
1496
1497     //
1498     // TODO: Set draw value
1499     //
1500 #if (PERF_COUNTERS && MP)
1501     ClearHelperThreadIdleness();
1502 #endif
1503     GAME_RESULT ret = Iterate(&ctx);
1504     if (ret.eResult == RESULT_IN_PROGRESS) {
1505         if (g_Options.iResignThreshold != 0 &&
1506             g_iRootScore[ctx.sPosition.uToMove] < g_Options.iResignThreshold) {
1507             _resign_count++;
1508             if (_resign_count > 2) {
1509                 if (ctx.sPosition.uToMove == WHITE) {
1510                     ret.eResult = RESULT_BLACK_WON;
1511                     strcpy(ret.szDescription, "white resigned");
1512                 } else {
1513                     ret.eResult = RESULT_WHITE_WON;
1514                     strcpy(ret.szDescription, "black resigned");                                }
1515                 Trace("tellics resign\n");
1516             }
1517             return ret;
1518         } else {
1519             _resign_count = 0;
1520         }
1521         MakeTheMove(&ctx);
1522         return _DetectPostMoveTerminalStates(&ctx);
1523     } else {
1524         return ret;
1525     }
1526 }