3 Copyright (c) Scott Gasch
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.
21 $Id: root.c 351 2008-06-28 04:21:53Z scott $
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};
39 _SetMoveTimerForPonder(void)
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.
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;
67 SetMoveTimerToThinkForever(void)
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;
91 SetMoveTimerForSearch(FLAG fSwitchOver, ULONG uColor)
96 Set the move timer for a search operation.
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).
109 ULONG uMovesDone = GetMoveNumber(uColor);
110 double dClock = (double)g_Options.uMyClock;
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).
119 if (FALSE == fSwitchOver)
121 g_MoveTimer.dStartTime = SystemTimeStamp();
122 g_MoveTimer.bvFlags = 0;
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.
131 g_MoveTimer.uNodeCheckMask = 0x800 - 1;
133 if (WeAreRunningASuite())
135 g_MoveTimer.uNodeCheckMask = 0x20000 - 1;
137 else if (g_Options.u64MaxNodeCount)
139 g_MoveTimer.uNodeCheckMask = 0x1000 - 1;
145 g_MoveTimer.uNodeCheckMask = 0x400 - 1;
149 g_MoveTimer.uNodeCheckMask = 0x8000 - 1;
154 switch (g_Options.eClock)
157 // Fixed time per move. Think for g_uMyIncrement seconds exactly and
158 // no hard time limit.
161 dSec = (double)g_Options.uMyIncrement;
166 // N moves per time control or entire game in time control.
169 if (g_Options.uMovesPerTimePeriod != 0)
172 // N moves per time control.
174 ASSERT(g_Options.uMovesPerTimePeriod < 256);
176 (g_Options.uMovesPerTimePeriod -
177 ((uMovesDone - 1) % g_Options.uMovesPerTimePeriod));
179 Trace("SetMoveTimer: %u moves left to do this in %s sec.\n",
180 uMovesToDo, TimeToString(dClock));
182 ASSERT(uMovesToDo <= g_Options.uMovesPerTimePeriod);
183 dSec = (dClock / (double)uMovesToDo);
185 uMargin = (ULONG)(dSec * 2.2);
196 // Fixed time finish entire game.
199 Trace("SetMoveTimer: finish the game in %s sec.\n",
200 TimeToString(dClock));
203 uMargin = (ULONG)(dSec * 2.2);
208 // We get back a certain number of seconds with each move made.
210 case CLOCK_INCREMENT:
211 dSec = g_Options.uMyIncrement;
212 dSec += (dClock / 50);
213 uMargin = (int)(dSec * 2.2);
216 Trace("SetMoveTimer: finish the game in %s sec (+%u per move).\n",
217 TimeToString(dClock), g_Options.uMyIncrement);
221 // If we are running out of time, think for less than the
226 dSec -= g_Options.uMyIncrement;
234 Trace("SetMoveTimer: no time limit, think until interrupted.\n");
236 g_MoveTimer.dHardTimeLimit = -1;
237 g_MoveTimer.dSoftTimeLimit = -1;
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;
249 if (TRUE == g_Options.fShouldPost)
251 if (g_MoveTimer.dSoftTimeLimit > 0)
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)
262 Trace("SetMoveTimer: Already searched %s seconds.\n",
263 TimeToString(SystemTimeStamp() -
264 g_MoveTimer.dStartTime));
268 Trace("SetMoveTimer: Checking input and timer every %u nodes.\n",
269 g_MoveTimer.uNodeCheckMask);
276 ReInitializeSearcherContext(POSITION *pos,
277 SEARCHER_THREAD_CONTEXT *ctx)
282 Reinitializes a SEARCHER_THREAD_CONTEXT structure.
287 SEARCHER_THREAD_CONTEXT *ctx
297 memmove(&(ctx->sPosition), pos, sizeof(POSITION));
300 ctx->uPositional = 133;
301 memset(&(ctx->sCounters), 0, sizeof(COUNTERS));
306 InitializeSearcherContext(POSITION *pos,
307 SEARCHER_THREAD_CONTEXT *ctx)
312 Initialize a SEARCHER_THREAD_CONTEXT structure.
317 SEARCHER_THREAD_CONTEXT *ctx
327 memset(ctx, 0, sizeof(SEARCHER_THREAD_CONTEXT));
328 ReInitializeSearcherContext(pos, ctx);
329 ctx->sMoveStack.uUnblockedKeyValue[0] = 1;
331 u < MAX_PLY_PER_SEARCH;
334 ctx->sMoveStack.uUnblockedKeyValue[u] =
335 ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28;
341 InitializeLightweightSearcherContext(POSITION *pos,
342 LIGHTWEIGHT_SEARCHER_CONTEXT *ctx)
347 Initialize a LIGHTWEIGHT_SEARCHER_CONTEXT structure.
352 LIGHTWEIGHT_SEARCHER_CONTEXT *ctx
362 memset(ctx, 0, sizeof(LIGHTWEIGHT_SEARCHER_CONTEXT));
365 memmove(&(ctx->sPosition), pos, sizeof(POSITION));
368 ctx->uPositional = 133;
369 ctx->sMoveStack.uUnblockedKeyValue[0] = 1;
371 u < MAX_PLY_PER_SEARCH;
374 ctx->sMoveStack.uUnblockedKeyValue[u] =
375 ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28;
381 PostMoveSearchReport(SEARCHER_THREAD_CONTEXT *ctx)
386 Dump a report to stdout after every move.
390 SEARCHER_THREAD_CONTEXT *ctx,
403 d = (double)g_MoveTimer.dEndTime - (double)g_MoveTimer.dStartTime + 0.01;
405 Trace("---------------------------------------------\n"
406 "Searched for %5.1f seconds, saw %"
407 COMPILER_LONGLONG_UNSIGNED_FORMAT
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)
416 snprintf(buf, ARRAY_LENGTH(buf), "d%u, %s, %3.1fs, %6.0fknps, PV=%s",
417 ctx->uRootDepth / ONE_PLY,
418 ScoreToString(ctx->iRootScore),
420 ((double)ctx->sCounters.tree.u64TotalNodeCount / d / 1000),
422 Trace("tellothers %s\n", buf);
426 if (ctx->sCounters.parallel.uNumSplits > 0)
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));
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();
443 AnalyzeFullHashTable();
446 d = (double)(ctx->sCounters.hash.u64Probes) + 1;
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;
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;
458 Trace("Null move cutoff rate: %5.3f percent.\n",
461 n = (double)(ctx->sCounters.tree.u64EndgamePruningSuccess);
462 d = n + (double)(ctx->sCounters.tree.u64EndgamePruningFailures);
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",
470 ctx->sCounters.tree.u64EndgamePruningSuccess,
471 (ctx->sCounters.tree.u64EndgamePruningSuccess +
472 ctx->sCounters.tree.u64EndgamePruningFailures));
476 Trace("Never used endgame pruning heuristic.\n");
480 n = (double)(ctx->sCounters.tree.u64AvoidNullSuccess);
481 d = n + (double)(ctx->sCounters.tree.u64AvoidNullFailures);
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",
489 ctx->sCounters.tree.u64AvoidNullSuccess,
490 (ctx->sCounters.tree.u64AvoidNullSuccess +
491 ctx->sCounters.tree.u64AvoidNullFailures));
495 Trace("Never used the avoid null move heuristic.\n");
497 n = (double)(ctx->sCounters.tree.u64QuickNullSuccess);
498 n += (double)(ctx->sCounters.tree.u64QuickNullDeferredSuccess);
499 d = n + (double)(ctx->sCounters.tree.u64QuickNullFailures);
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",
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));
516 Trace("Never used the quick null move heuristic.\n");
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",
524 d = (double)ctx->sCounters.tree.u64LazyEvals;
525 d += (double)ctx->sCounters.tree.u64FullEvals;
526 d += (double)ctx->sCounters.tree.u64EvalHashHits;
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);
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);
549 n = (double)ctx->sCounters.tree.u64CyclesInEval;
550 Trace("Avg. cpu cycles in eval: %8.1f.\n", (n / d));
558 RootSearch(SEARCHER_THREAD_CONTEXT *ctx,
566 Search at the root of the whole tree.
570 SEARCHER_THREAD_CONTEXT *ctx,
581 PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
582 SCORE iBestScore = -INFINITY;
583 SCORE iInitialAlpha = iAlpha;
588 UINT64 u64StartingNodeCount;
589 ULONG uNumLegalMoves;
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));
600 ctx->sCounters.tree.u64TotalNodeCount++;
601 pi->PV[ctx->uPly] = NULLMOVE;
602 pi->mvBest = NULLMOVE;
603 g_MoveTimer.bvFlags |= TIMER_SEARCHING_FIRST_MOVE;
605 Trace("---- depth=%u, a=%d, b=%d ----\n", uDepth / ONE_PLY, iAlpha, iBeta);
609 for (x = ctx->sMoveStack.uBegin[ctx->uPly];
610 x < ctx->sMoveStack.uEnd[ctx->uPly];
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);
619 if (MakeMove(ctx, mv))
622 u64StartingNodeCount = ctx->sCounters.tree.u64TotalNodeCount;
625 // TODO: Fancy recap shit here?
628 uNextDepth = uDepth - ONE_PLY;
629 if (IS_CHECKING_MOVE(mv))
631 uNextDepth += HALF_PLY;
632 ctx->sPlyInfo[ctx->uPly].iExtensionAmount = HALF_PLY;
635 ctx->sSearchFlags.fVerifyNullmove = TRUE;
636 ctx->sSearchFlags.uQsearchDepth = 0;
637 if (uNumLegalMoves == 1)
640 // Move 1, full a..b window
642 iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
647 // Moves 2..N, minimal window search
650 ASSERT(uNumLegalMoves > 1);
651 iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uNextDepth);
652 if ((iAlpha < iScore) && (iScore < iBeta))
654 iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth);
657 ctx->sSearchFlags.fVerifyNullmove = FALSE;
659 if (WE_SHOULD_STOP_SEARCHING)
661 iBestScore = INVALID_SCORE;
665 Trace("%2u. %-8s => node=%" COMPILER_LONGLONG_UNSIGNED_FORMAT
666 ", predict=%d, actual=%d, ",
668 MoveToSan(mv, &ctx->sPosition),
669 u64StartingNodeCount,
670 ctx->sMoveStack.mvf[x].iValue,
672 ASSERT(PositionsAreEquivalent(&pi->sPosition, &ctx->sPosition));
675 // Keep track of how many moves are under each one we
676 // search and use this as the basis for root move ordering
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);
686 Trace("next_predict: %d\n", ctx->sMoveStack.mvf[x].iValue);
687 ASSERT(iBestScore <= iAlpha);
688 ASSERT(iAlpha < iBeta);
690 if (iScore > iBestScore)
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.
702 Trace("Best so far... root score=%d.\n", iScore);
704 ctx->mvRootMove = mv;
705 ctx->iRootScore = iScore;
706 ctx->uRootDepth = uDepth;
707 ctx->sMoveStack.mvf[x].iValue = MAX_INT;
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.
714 for (y = ctx->sMoveStack.uBegin[ctx->uPly];
718 if (ctx->sMoveStack.mvf[y].iValue == MAX_INT)
720 ctx->sMoveStack.mvf[y].iValue /= 2;
730 UpdateDynamicMoveOrdering(ctx,
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;
745 UtilPrintPV(ctx, iAlpha, iBeta, iScore, mv);
750 g_MoveTimer.bvFlags &= ~TIMER_SEARCHING_FIRST_MOVE;
754 if (iAlpha == iInitialAlpha)
759 ASSERT(iBestScore <= iAlpha);
760 ASSERT(PositionsAreEquivalent(pos, &pi->sPosition));
761 UtilPrintPV(ctx, iAlpha, iBeta, iBestScore, mv);
771 _DetectPreMoveTerminalStates(SEARCHER_THREAD_CONTEXT *ctx,
780 ret.eResult = RESULT_IN_PROGRESS;
781 ret.szDescription[0] = '\0';
784 for (u = ctx->sMoveStack.uBegin[ctx->uPly];
785 u < ctx->sMoveStack.uEnd[ctx->uPly];
787 mv = ctx->sMoveStack.mvf[u].mv;
788 if (MakeMove(ctx, mv)) {
798 if (uNumLegal == 1) {
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");
808 ret.eResult = RESULT_WHITE_WON;
809 strcpy(ret.szDescription, "white checkmated black");
812 ret.eResult = RESULT_DRAW;
813 strcpy(ret.szDescription, "stalemate");
821 _DetectPostMoveTerminalStates(SEARCHER_THREAD_CONTEXT *ctx)
826 This function is called by Iterate and MakeTheMove to declare
831 SEARCHER_THREAD_CONTEXT *ctx
840 FLAG fInCheck = InCheck(&ctx->sPosition, ctx->sPosition.uToMove);
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");
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");
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));
861 return _DetectPreMoveTerminalStates(ctx,
868 _IterateSetSearchGlobals(ULONG uDepth)
871 ULONG uDontSplitLessThan;
874 // Set some globals that will be used throughout this search.
876 g_uIterateDepth = uDepth;
877 ASSERT(g_uIterateDepth > 0);
878 ASSERT(g_uIterateDepth < MAX_PLY_PER_SEARCH);
881 // For use in scaling back extensions that are very far from
884 // Iterate g_Soft g_Hard
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...
890 g_uSoftExtendLimit = g_uIterateDepth * 2;
891 g_uHardExtendLimit = g_uIterateDepth * 4;
892 for (u = 0; u < MAX_PLY_PER_SEARCH; u++)
894 if (u < g_uSoftExtendLimit)
896 g_uExtensionReduction[u] = 0;
898 else if (u < (g_uSoftExtendLimit + g_uIterateDepth / 2))
900 g_uExtensionReduction[u] = QUARTER_PLY;
902 else if (u < (g_uSoftExtendLimit + g_uIterateDepth))
904 g_uExtensionReduction[u] = HALF_PLY;
906 else if (u < g_uHardExtendLimit)
908 g_uExtensionReduction[u] = THREE_QUARTERS_PLY;
912 g_uExtensionReduction[u] = 5 * ONE_PLY;
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).
920 uDontSplitLessThan = (ULONG)((double)(uDepth) * 0.30);
921 for (v = 0; v < MAX_PLY_PER_SEARCH; v++)
923 g_fCanSplit[v] = ((v + 1) >= uDontSplitLessThan);
925 g_fCanSplit[0] = FALSE;
929 #define SKIP_GRADUAL_OPENING 600
930 #define INITIAL_HALF_WINDOW 75
931 #define FIRST_FAIL_STEP 150
932 #define SECOND_FAIL_STEP 375
935 _IterateWidenWindow(ULONG uColor,
941 SCORE iRoughScore = g_iRootScore[uColor];
942 static SCORE _Steps[] =
949 // Trace("State = %u.\n", *puState);
950 // Trace("Bound from %d to ", *piBound);
951 if ((abs(iRoughScore - iScore) > SKIP_GRADUAL_OPENING) ||
954 *piBound = iDir * INFINITY;
959 ASSERT(*puState < 2);
961 *piBound += iDir * _Steps[*puState];
964 // Trace("%d.\n", *piBound);
965 // Trace("State = %u\n", *puState);
969 GAME_RESULT Iterate(SEARCHER_THREAD_CONTEXT *ctx)
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
981 SEARCHER_THREAD_CONTEXT *ctx
985 FLAG : is the game over?
989 ULONG uNumRootFailLows = 0;
991 ULONG uFailState = 0;
994 SCORE iAlpha = -INFINITY;
995 SCORE iBeta = +INFINITY;
997 FLAG fInCheck = InCheck(&(ctx->sPosition), ctx->sPosition.uToMove);
1002 memcpy(&board, &(ctx->sPosition), sizeof(POSITION));
1003 VerifyPositionConsistency(&board, FALSE);
1006 uColor = ctx->sPosition.uToMove;
1007 g_iRootScore[uColor] = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE);
1008 g_iRootScore[FLIP(uColor)] = -g_iRootScore[uColor];
1011 // Generate moves here so that RootSearch doesn't have to.
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);
1020 // See if we are sitting at a checkmate or stalemate position; no
1021 // sense searching if so.
1023 ret = _DetectPreMoveTerminalStates(ctx,
1026 if (ret.eResult != RESULT_IN_PROGRESS) {
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;
1043 Trace("ONLY PONDER --> move immediately if prediction correct.\n");
1044 g_MoveTimer.bvFlags |= TIMER_MOVE_IMMEDIATELY;
1045 g_MoveTimer.bvFlags |= TIMER_CURRENT_OBVIOUS;
1051 uDepth <= g_Options.uMaxDepth;
1055 // Re-rank the moves based on nodecounts and mark all moves as
1056 // not yet searched at this depth.
1058 for (u = ctx->sMoveStack.uBegin[ctx->uPly];
1059 u < ctx->sMoveStack.uEnd[ctx->uPly];
1062 ctx->sMoveStack.mvf[u].bvFlags &= ~MVF_MOVE_SEARCHED;
1066 // Make sure a..b window makes sense and set some other per-depth
1067 // globals used by the search.
1069 _IterateSetSearchGlobals(uDepth);
1072 // Try to get a PV for this depth before we're out of time...
1076 if (iBeta > INFINITY) iBeta = +INFINITY;
1077 if (iAlpha < -INFINITY) iAlpha = -INFINITY;
1078 if (iAlpha >= iBeta) iAlpha = iBeta - 1;
1079 iScore = RootSearch(ctx,
1082 uDepth * ONE_PLY + HALF_PLY);
1083 if (g_MoveTimer.bvFlags & TIMER_STOPPING) break;
1084 mv = ctx->mvRootMove;
1087 // Got a PV, we're done with this depth.
1089 if ((iAlpha < iScore) && (iScore < iBeta))
1091 ASSERT(iScore == ctx->iRootScore);
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;
1101 (void)CheckTestSuiteMove(mv, iScore, uDepth);
1106 // Root fail low? We'll have to research with a wider
1109 else if (iScore <= iAlpha)
1111 ASSERT(ctx->mvRootMove.uMove);
1112 g_MoveTimer.bvFlags |= TIMER_RESOLVING_ROOT_FL;
1114 if (uNumRootFailLows > 3)
1116 g_MoveTimer.bvFlags |= TIMER_MANY_ROOT_FLS;
1118 _IterateWidenWindow(uColor, iScore, &iAlpha, &uFailState, -1);
1121 // Consider all moves again with wider window...
1123 for (u = ctx->sMoveStack.uBegin[ctx->uPly];
1124 u < ctx->sMoveStack.uEnd[ctx->uPly];
1127 ctx->sMoveStack.mvf[u].bvFlags &= ~MVF_MOVE_SEARCHED;
1132 // Must be a root fail high.
1136 ASSERT(iScore >= iBeta);
1138 ASSERT(SanityCheckMove(&ctx->sPosition, mv));
1139 g_MoveTimer.bvFlags |= TIMER_RESOLVING_ROOT_FH;
1140 _IterateWidenWindow(uColor, iScore, &iBeta, &uFailState, +1);
1143 while(1); // repeat until we run out of time or fall inside a..b
1146 // We are here because either:
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.
1155 // TODO: Scale back history between iterative depths?
1159 // Mate-in-n when we have searched n? Stop searching.
1161 if (IS_VALID_SCORE(iScore) &&
1162 (ULONG)abs(iScore) >= (INFINITY - uDepth))
1164 Trace("FORCED MATE --> stop searching now\n");
1165 g_MoveTimer.bvFlags |= TIMER_STOPPING;
1169 // Have we reached user's maxdepth option? Stop searching.
1171 if (uDepth >= g_Options.uMaxDepth)
1173 Trace("DEPTH LIMIT --> stop searching now\n");
1174 g_MoveTimer.bvFlags |= TIMER_STOPPING;
1178 // Did the move timer expire? Stop searching.
1180 if (g_MoveTimer.bvFlags & TIMER_STOPPING) break;
1182 g_Options.u64NodesSearched = ctx->sCounters.tree.u64TotalNodeCount;
1183 g_MoveTimer.dEndTime = SystemTimeStamp();
1186 // Here we are at the end of a search. If we were:
1188 // ...Searching then: ...Pondering then:
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)
1200 ASSERT(ctx->mvRootMove.uMove);
1201 ASSERT(SanityCheckMove(&board, ctx->mvRootMove));
1202 if (g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FL)
1204 ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly] = ctx->mvRootMove;
1205 ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly+1] = NULLMOVE;
1207 ret.eResult = RESULT_IN_PROGRESS;
1208 ret.szDescription[0] = '\0';
1214 MakeTheMove(SEARCHER_THREAD_CONTEXT *ctx)
1217 Routine description:
1219 Make the move that search selected in the official game list.
1223 SEARCHER_THREAD_CONTEXT *ctx
1231 MOVE mv = ctx->mvRootMove;
1234 if (TRUE == g_Options.fThinking)
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.
1242 // Was this a search that converted from a ponder?
1244 if (TRUE == g_Options.fSuccessfulPonder)
1246 if (FALSE == OfficiallyMakeMove(g_Options.mvPonder, 0, FALSE))
1248 UtilPanic(CANNOT_OFFICIALLY_MAKE_MOVE,
1250 (void *)g_Options.mvPonder.uMove,
1256 g_Options.fSuccessfulPonder = FALSE;
1260 // Tell the server about our move and actually play it on the
1263 Trace("move %s\n", MoveToSan(mv, &ctx->sPosition));
1264 if (FALSE == OfficiallyMakeMove(mv, g_iScore, FALSE))
1266 UtilPanic(CANNOT_OFFICIALLY_MAKE_MOVE,
1274 if (g_Options.fVerbosePosting)
1276 PostMoveSearchReport(ctx);
1277 PostMoveTestSuiteReport(ctx);
1280 g_Options.fPondering = g_Options.fThinking = FALSE;
1285 Ponder(POSITION *pos)
1288 Routine description:
1302 static SEARCHER_THREAD_CONTEXT ctx;
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';
1313 // When do we not want to ponder
1315 if ((g_Options.ePlayMode == FORCE_MODE) || (g_Options.uMyClock < 10))
1317 g_Options.fPondering = FALSE;
1322 // What should we ponder?
1324 g_Options.mvPonder = GetPonderMove(pos);
1325 if (g_Options.mvPonder.uMove == 0)
1327 g_Options.fPondering = FALSE;
1330 ASSERT(SanityCheckMove(pos, g_Options.mvPonder));
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.
1337 MaintainDynamicMoveOrdering();
1341 // Make the move ponder move.
1343 if (FALSE == MakeMove(&ctx, g_Options.mvPonder))
1346 g_Options.fPondering = FALSE;
1351 // TODO: probe the book
1354 _SetMoveTimerForPonder();
1357 // TODO: Any preEval?
1361 // TODO: Set draw value
1365 #if (PERF_COUNTERS && MP)
1366 ClearHelperThreadIdleness();
1368 ASSERT(ctx.uPly == 1);
1369 ret = Iterate(&ctx);
1370 ASSERT(ctx.uPly == 1);
1371 if (ret.eResult == RESULT_IN_PROGRESS) {
1373 return _DetectPostMoveTerminalStates(&ctx);
1380 GAME_RESULT Think(POSITION *pos)
1383 Routine description:
1397 static SEARCHER_THREAD_CONTEXT ctx;
1401 InitializeSearcherContext(pos, &ctx);
1402 g_MoveTimer.bvFlags = 0;
1403 g_Options.fPondering = FALSE;
1404 g_Options.fThinking = TRUE;
1405 g_Options.fSuccessfulPonder = FALSE;
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.
1412 if (NULL != (p = PositionToFen(&(ctx.sPosition))))
1414 Trace("The root position is: %s\n", p);
1415 SystemFreeMemory(p);
1417 MaintainDynamicMoveOrdering();
1421 // Check the opening book, maybe it has a move for us.
1423 if ((g_uBookProbeFailures < 3) && (!WeAreRunningASuite()))
1425 mvBook = BookMove(pos, BOOKMOVE_SELECT_MOVE);
1426 if (mvBook.uMove == 0)
1428 g_uBookProbeFailures++;
1432 g_uBookProbeFailures = 0;
1433 ASSERT(SanityCheckMove(pos, mvBook));
1434 ctx.mvRootMove = mvBook;
1436 return _DetectPostMoveTerminalStates(&ctx);
1441 // TODO: Any preEval?
1445 // Set time limit for move
1447 SetMoveTimerForSearch(FALSE, pos->uToMove);
1450 // TODO: Set draw value
1452 #if (PERF_COUNTERS && MP)
1453 ClearHelperThreadIdleness();
1455 GAME_RESULT ret = Iterate(&ctx);
1456 if (ret.eResult == RESULT_IN_PROGRESS) {
1458 return _DetectPostMoveTerminalStates(&ctx);