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