diff options
Diffstat (limited to 'src/changes/root.c')
| -rwxr-xr-x | src/changes/root.c | 1462 |
1 files changed, 1462 insertions, 0 deletions
diff --git a/src/changes/root.c b/src/changes/root.c new file mode 100755 index 0000000..d38f8c0 --- /dev/null +++ b/src/changes/root.c @@ -0,0 +1,1462 @@ +/** + +Copyright (c) Scott Gasch + +Module Name: + + root.c + +Abstract: + + Routines dealing with the root of the search tree. Specifically + move ordering at the root node, searching, search support, pondering, + pondering support, and the main iterative deepening loop. + +Author: + + Scott Gasch ([email protected]) 21 May 2004 + +Revision History: + + $Id: root.c 351 2008-06-28 04:21:53Z scott $ + +**/ + +#include "chess.h" + +volatile MOVE_TIMER g_MoveTimer; +ULONG g_uIterateDepth; +ULONG g_uSoftExtendLimit; +ULONG g_uHardExtendLimit; +ULONG g_uExtensionReduction[MAX_PLY_PER_SEARCH]; +FLAG g_fCanSplit[MAX_PLY_PER_SEARCH]; +extern FILE *g_pfLogfile; +SCORE g_iRootScore[2] = {0, 0}; +SCORE g_iScore; + + +static void +_SetMoveTimerForPonder(void) +/** + +Routine description: + + Set the move timer before a ponder operation. A time limit of -1 + means search forever... so the only way out of the ponder is for + new user input to interrupt it. + +Parameters: + + void + +Return value: + + static void + +**/ +{ + g_MoveTimer.dStartTime = SystemTimeStamp(); + g_MoveTimer.dSoftTimeLimit = -1; + g_MoveTimer.dHardTimeLimit = -1; + g_MoveTimer.uNodeCheckMask = 0x200 - 1; + g_MoveTimer.bvFlags = 0; +} + + +void +SetMoveTimerToThinkForever(void) +/** + +Routine description: + +Parameters: + + void + +Return value: + + void + +**/ +{ + g_MoveTimer.dStartTime = SystemTimeStamp(); + g_MoveTimer.dSoftTimeLimit = -1; + g_MoveTimer.dHardTimeLimit = -1; + g_MoveTimer.uNodeCheckMask = 0x1000000 - 1; + g_MoveTimer.bvFlags = 0; +} + + +void +SetMoveTimerForSearch(FLAG fSwitchOver, ULONG uColor) +/** + +Routine description: + + Set the move timer for a search operation. + +Parameters: + + FLAG fSwitchOver : if TRUE then this search is a converted ponder + (i.e. they made the ponder move and now we are searching). + +Return value: + + void + +**/ +{ + ULONG uMovesDone = GetMoveNumber(uColor); + double dClock = (double)g_Options.uMyClock; + double dSec = 0; + ULONG uMargin = 0; + ULONG uMovesToDo; + + // + // If switching over from a ponder search leave the start time and + // move flags alone (i.e. N seconds in the past already). + // + if (FALSE == fSwitchOver) + { + g_MoveTimer.dStartTime = SystemTimeStamp(); + g_MoveTimer.bvFlags = 0; + } + + // + // Check the clock more often in search if there is little time + // left on the clock -- we can't afford an oversearch when the + // bullet game is down to the wire. + // +#ifdef DEBUG + g_MoveTimer.uNodeCheckMask = 0x800 - 1; +#else + if (WeAreRunningASuite()) + { + g_MoveTimer.uNodeCheckMask = 0x20000 - 1; + } + else if (g_Options.u64MaxNodeCount) + { + g_MoveTimer.uNodeCheckMask = 0x1000 - 1; + } + else + { + if (dClock < 10.0) + { + g_MoveTimer.uNodeCheckMask = 0x400 - 1; + } + else + { + g_MoveTimer.uNodeCheckMask = 0x8000 - 1; + } + } +#endif + + switch (g_Options.eClock) + { + // + // Fixed time per move. Think for g_uMyIncrement seconds exactly and + // no hard time limit. + // + case CLOCK_FIXED: + dSec = (double)g_Options.uMyIncrement; + uMargin = 0; + break; + + // + // N moves per time control or entire game in time control. + // + case CLOCK_NORMAL: + if (g_Options.uMovesPerTimePeriod != 0) + { + // + // N moves per time control. + // + ASSERT(g_Options.uMovesPerTimePeriod < 256); + uMovesToDo = + (g_Options.uMovesPerTimePeriod - + ((uMovesDone - 1) % g_Options.uMovesPerTimePeriod)); +#ifdef DEBUG + Trace("SetMoveTimer: %u moves left to do this in %s sec.\n", + uMovesToDo, TimeToString(dClock)); +#endif + ASSERT(uMovesToDo <= g_Options.uMovesPerTimePeriod); + dSec = (dClock / (double)uMovesToDo); + dSec *= 0.95; + uMargin = (ULONG)(dSec * 2.2); + if (uMovesToDo <= 5) + { + dSec *= 0.75; + uMargin /= 2; + } + break; + } + else + { + // + // Fixed time finish entire game. + // +#ifdef DEBUG + Trace("SetMoveTimer: finish the game in %s sec.\n", + TimeToString(dClock)); +#endif + dSec = dClock / 60; + uMargin = (ULONG)(dSec * 2.2); + } + break; + + // + // We get back a certain number of seconds with each move made. + // + case CLOCK_INCREMENT: + dSec = g_Options.uMyIncrement; + dSec += (dClock / 50); + uMargin = (int)(dSec * 2.2); + +#ifdef DEBUG + Trace("SetMoveTimer: finish the game in %s sec (+%u per move).\n", + TimeToString(dClock), g_Options.uMyIncrement); +#endif + + // + // If we are running out of time, think for less than the + // increment. + // + if (dClock < 20.0) + { + dSec -= g_Options.uMyIncrement; + uMargin = 0; + } + ASSERT(dSec > 0); + break; + + case CLOCK_NONE: +#ifdef DEBUG + Trace("SetMoveTimer: no time limit, think until interrupted.\n"); +#endif + g_MoveTimer.dHardTimeLimit = -1; + g_MoveTimer.dSoftTimeLimit = -1; + goto post; + + default: + ASSERT(FALSE); + break; + } + if ((dSec + uMargin) >= (dClock * 7 / 8)) uMargin = 0; + g_MoveTimer.dSoftTimeLimit = g_MoveTimer.dStartTime + dSec; + g_MoveTimer.dHardTimeLimit = g_MoveTimer.dStartTime + dSec + uMargin; + + post: + if (TRUE == g_Options.fShouldPost) + { + if (g_MoveTimer.dSoftTimeLimit > 0) + { + Trace("SetMoveTimer: Soft time limit %s seconds.\n", + TimeToString(g_MoveTimer.dSoftTimeLimit - + g_MoveTimer.dStartTime)); + ASSERT(g_MoveTimer.dHardTimeLimit > 0); + Trace("SetMoveTimer: Hard time limit %s seconds.\n", + TimeToString(g_MoveTimer.dHardTimeLimit - + g_MoveTimer.dStartTime)); + if (TRUE == fSwitchOver) + { + Trace("SetMoveTimer: Already searched %s seconds.\n", + TimeToString(SystemTimeStamp() - + g_MoveTimer.dStartTime)); + } + } +#ifdef DEBUG + Trace("SetMoveTimer: Checking input and timer every %u nodes.\n", + g_MoveTimer.uNodeCheckMask); +#endif + } +} + + +void +ReInitializeSearcherContext(POSITION *pos, + SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + Reinitializes a SEARCHER_THREAD_CONTEXT structure. + +Parameters: + + POSITION *pos, + SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + void + +**/ +{ + if (NULL != pos) + { + memmove(&(ctx->sPosition), pos, sizeof(POSITION)); + } + ctx->uPly = 0; + ctx->uPositional = 133; + memset(&(ctx->sCounters), 0, sizeof(COUNTERS)); +} + + +void +InitializeSearcherContext(POSITION *pos, + SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + Initialize a SEARCHER_THREAD_CONTEXT structure. + +Parameters: + + POSITION *pos, + SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + void + +**/ +{ + ULONG u; + + memset(ctx, 0, sizeof(SEARCHER_THREAD_CONTEXT)); + ReInitializeSearcherContext(pos, ctx); + ctx->sMoveStack.uUnblockedKeyValue[0] = 1; + for (u = 1; + u < MAX_PLY_PER_SEARCH; + u++) + { + ctx->sMoveStack.uUnblockedKeyValue[u] = + ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28; + } +} + + +void +InitializeLightweightSearcherContext(POSITION *pos, + LIGHTWEIGHT_SEARCHER_CONTEXT *ctx) +/** + +Routine description: + + Initialize a LIGHTWEIGHT_SEARCHER_CONTEXT structure. + +Parameters: + + POSITION *pos, + LIGHTWEIGHT_SEARCHER_CONTEXT *ctx + +Return value: + + void + +**/ +{ + ULONG u; + + memset(ctx, 0, sizeof(LIGHTWEIGHT_SEARCHER_CONTEXT)); + if (NULL != pos) + { + memmove(&(ctx->sPosition), pos, sizeof(POSITION)); + } + ctx->uPly = 0; + ctx->uPositional = 133; + ctx->sMoveStack.uUnblockedKeyValue[0] = 1; + for (u = 1; + u < MAX_PLY_PER_SEARCH; + u++) + { + ctx->sMoveStack.uUnblockedKeyValue[u] = + ctx->sMoveStack.uUnblockedKeyValue[u-1] + 0x28F5C28; + } +} + + +void +PostMoveSearchReport(SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + Dump a report to stdout after every move. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + +Return value: + + void + +**/ +{ + double d; + char buf[256]; +#ifdef PERF_COUNTERS + double n; +#endif + d = (double)g_MoveTimer.dEndTime - (double)g_MoveTimer.dStartTime + 0.01; + ASSERT(d); + Trace("---------------------------------------------\n" + "Searched for %5.1f seconds, saw %" + COMPILER_LONGLONG_UNSIGNED_FORMAT + " nodes (%" + COMPILER_LONGLONG_UNSIGNED_FORMAT + " qnodes) (%6.0f nps).\n", + d, ctx->sCounters.tree.u64TotalNodeCount, + ctx->sCounters.tree.u64QNodeCount, + ((double)ctx->sCounters.tree.u64TotalNodeCount / d)); + if (g_Options.fThinking) + { + snprintf(buf, ARRAY_LENGTH(buf), "d%u, %s, %3.1fs, %6.0fknps, PV=%s", + ctx->uRootDepth / ONE_PLY, + ScoreToString(ctx->iRootScore), + d, + ((double)ctx->sCounters.tree.u64TotalNodeCount / d / 1000), + ctx->szLastPV); + Trace("tellothers %s\n", buf); + } +#ifdef MP +#ifdef PERF_COUNTERS + if (ctx->sCounters.parallel.uNumSplits > 0) + { + n = (double)ctx->sCounters.parallel.uNumSplits; + Trace("Split %u times total ", + ctx->sCounters.parallel.uNumSplits); + Trace("(~%7.2fx/sec).\n", (n / d)); + d = n + 1; + ASSERT(d); + n = (double)ctx->sCounters.parallel.uNumSplitsTerminated; + Trace(" ...%u (%5.2f percent) terminated early.\n", + ctx->sCounters.parallel.uNumSplitsTerminated, ((n/d) * 100.0)); + DumpHelperIdlenessReport(); + } +#endif +#endif + +#ifdef TEST + AnalyzeFullHashTable(); +#endif +#ifdef PERF_COUNTERS + d = (double)(ctx->sCounters.hash.u64Probes) + 1; + ASSERT(d); + Trace("Hashing percentages: (%5.3f total, %5.3f useful)\n", + ((double)(ctx->sCounters.hash.u64OverallHits) / d) * 100.0, + ((double)(ctx->sCounters.hash.u64UsefulHits) / d) * 100.0); + d = (double)(ctx->sCounters.pawnhash.u64Probes) + 1; + ASSERT(d); + n = (double)(ctx->sCounters.pawnhash.u64Hits); + Trace("Pawn hash hitrate: %5.3f percent.\n", (n/d) * 100.0); + n = (double)(ctx->sCounters.tree.u64NullMoveSuccess); + d = (double)(ctx->sCounters.tree.u64NullMoves) + 1; + ASSERT(d); + Trace("Null move cutoff rate: %5.3f percent.\n", + ((n / d) * 100.0)); +#ifdef TEST_ENDGAME + n = (double)(ctx->sCounters.tree.u64EndgamePruningSuccess); + d = n + (double)(ctx->sCounters.tree.u64EndgamePruningFailures); + if (d != 0.0) + { + Trace("Endgame pruning heuristic success rate was %5.3f percent.\n" + "Endgame pruning heuristic was " + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT " / " + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ".\n", + ((n / d) * 100.0), + ctx->sCounters.tree.u64EndgamePruningSuccess, + (ctx->sCounters.tree.u64EndgamePruningSuccess + + ctx->sCounters.tree.u64EndgamePruningFailures)); + } + else + { + Trace("Never used endgame pruning heuristic.\n"); + } +#endif +#ifdef TEST_NULL + n = (double)(ctx->sCounters.tree.u64AvoidNullSuccess); + d = n + (double)(ctx->sCounters.tree.u64AvoidNullFailures); + if (d != 0.0) + { + Trace("Avoid null move heuristic rate was %5.3f percent.\n" + "Avoid null move heuristic was " + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT " / " + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ".\n", + ((n / d) * 100.0), + ctx->sCounters.tree.u64AvoidNullSuccess, + (ctx->sCounters.tree.u64AvoidNullSuccess + + ctx->sCounters.tree.u64AvoidNullFailures)); + } + else + { + Trace("Never used the avoid null move heuristic.\n"); + } + n = (double)(ctx->sCounters.tree.u64QuickNullSuccess); + n += (double)(ctx->sCounters.tree.u64QuickNullDeferredSuccess); + d = n + (double)(ctx->sCounters.tree.u64QuickNullFailures); + if (d != 0.0) + { + Trace("Quick null move heuristic rate was %5.3f percent.\n" + "Quick null move heuristic rate was " + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT " (" + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ") / " + "%"COMPILER_LONGLONG_UNSIGNED_FORMAT ".\n", + ((n / d) * 100.0), + ctx->sCounters.tree.u64QuickNullSuccess, + ctx->sCounters.tree.u64QuickNullDeferredSuccess, + (ctx->sCounters.tree.u64QuickNullSuccess + + ctx->sCounters.tree.u64QuickNullDeferredSuccess + + ctx->sCounters.tree.u64QuickNullFailures)); + } + else + { + Trace("Never used the quick null move heuristic.\n"); + } +#endif + n = (double)ctx->sCounters.tree.u64BetaCutoffsOnFirstMove; + d = (double)ctx->sCounters.tree.u64BetaCutoffs + 1; + Trace("First move beta cutoff rate was %5.3f percent.\n", + ((n / d) * 100.0)); +#ifdef LAZY_EVAL + d = (double)ctx->sCounters.tree.u64LazyEvals; + d += (double)ctx->sCounters.tree.u64FullEvals; + d += (double)ctx->sCounters.tree.u64EvalHashHits; + d += 1; + ASSERT(d); + Trace("Eval percentages: (%5.2f hash, %5.2f lazy, %5.2f full)\n", + ((double)ctx->sCounters.tree.u64EvalHashHits / d) * 100.0, + ((double)ctx->sCounters.tree.u64LazyEvals / d) * 100.0, + ((double)ctx->sCounters.tree.u64FullEvals / d) * 100.0); +#endif + Trace("Extensions: (%u +, %u q+, %u 1mv, %u !kmvs, %u mult+, %u pawn\n" + " %u threat, %u zug, %u sing, %u endg, %u bm, %u recap)\n", + ctx->sCounters.extension.uCheck, + ctx->sCounters.extension.uQExtend, + ctx->sCounters.extension.uOneLegalMove, + ctx->sCounters.extension.uNoLegalKingMoves, + ctx->sCounters.extension.uMultiCheck, + ctx->sCounters.extension.uPawnPush, + ctx->sCounters.extension.uMateThreat, + ctx->sCounters.extension.uZugzwang, + ctx->sCounters.extension.uSingularReplyToCheck, + ctx->sCounters.extension.uEndgame, + ctx->sCounters.extension.uBotvinnikMarkoff, + ctx->sCounters.extension.uRecapture); +#ifdef EVAL_TIME + n = (double)ctx->sCounters.tree.u64CyclesInEval; + Trace("Avg. cpu cycles in eval: %8.1f.\n", (n / d)); +#endif +#endif + fflush(g_pfLogfile); +} + + +SCORE +RootSearch(SEARCHER_THREAD_CONTEXT *ctx, + SCORE iAlpha, + SCORE iBeta, + ULONG uDepth) +/** + +Routine description: + + Search at the root of the whole tree. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx, + SCORE iAlpha, + SCORE iBeta, + ULONG uDepth, + +Return value: + + SCORE + +**/ +{ + PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly]; + SCORE iBestScore = -INFINITY; + SCORE iInitialAlpha = iAlpha; + MOVE mv; + ULONG x, y; + SCORE iScore; + ULONG uNextDepth; + UINT64 u64StartingNodeCount; + ULONG uNumLegalMoves; + +#ifdef DEBUG + POSITION *pos = &ctx->sPosition; + ASSERT(IS_VALID_SCORE(iAlpha)); + ASSERT(IS_VALID_SCORE(iBeta)); + ASSERT(iAlpha < iBeta); + ASSERT((ctx->uPly == 0) || (ctx->uPly == 1)); // 1 is for under a ponder + memcpy(&pi->sPosition, pos, sizeof(POSITION)); +#endif + + ctx->sCounters.tree.u64TotalNodeCount++; + pi->PV[ctx->uPly] = NULLMOVE; + pi->mvBest = NULLMOVE; + g_MoveTimer.bvFlags |= TIMER_SEARCHING_FIRST_MOVE; +#ifdef DEBUG + Trace("---- depth=%u, a=%d, b=%d ----\n", uDepth / ONE_PLY, iAlpha, iBeta); +#endif + + uNumLegalMoves = 0; + for (x = ctx->sMoveStack.uBegin[ctx->uPly]; + x < ctx->sMoveStack.uEnd[ctx->uPly]; + x++) + { + SelectMoveAtRoot(ctx, x); + if (ctx->sMoveStack.mvf[x].bvFlags & MVF_MOVE_SEARCHED) break; + ctx->sMoveStack.mvf[x].bvFlags |= MVF_MOVE_SEARCHED; + mv = ctx->sMoveStack.mvf[x].mv; + mv.bvFlags |= WouldGiveCheck(ctx, mv); + + if (MakeMove(ctx, mv)) + { + uNumLegalMoves++; + u64StartingNodeCount = ctx->sCounters.tree.u64TotalNodeCount; + + // + // TODO: Fancy recap shit here? + // + + uNextDepth = uDepth - ONE_PLY; + if (IS_CHECKING_MOVE(mv)) + { + uNextDepth += HALF_PLY; + ctx->sPlyInfo[ctx->uPly].iExtensionAmount = HALF_PLY; + } + + ctx->sSearchFlags.fVerifyNullmove = TRUE; + ctx->sSearchFlags.uQsearchDepth = 0; + if (uNumLegalMoves == 1) + { + // + // Move 1, full a..b window + // + iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); + } + else + { + // + // Moves 2..N, minimal window search + // + ASSERT(x > 0); + ASSERT(uNumLegalMoves > 1); + iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uNextDepth); + if ((iAlpha < iScore) && (iScore < iBeta)) + { + iScore = -Search(ctx, -iBeta, -iAlpha, uNextDepth); + } + } + ctx->sSearchFlags.fVerifyNullmove = FALSE; + UnmakeMove(ctx, mv); + if (WE_SHOULD_STOP_SEARCHING) + { + iBestScore = INVALID_SCORE; + goto end; + } +#ifdef DEBUG + Trace("%2u. %-8s => node=%" COMPILER_LONGLONG_UNSIGNED_FORMAT + ", predict=%d, actual=%d, ", + x + 1, + MoveToSan(mv, &ctx->sPosition), + u64StartingNodeCount, + ctx->sMoveStack.mvf[x].iValue, + iScore); + ASSERT(PositionsAreEquivalent(&pi->sPosition, &ctx->sPosition)); +#endif + // + // Keep track of how many moves are under each one we + // search and use this as the basis for root move ordering + // next iteration. + // + u64StartingNodeCount = (ctx->sCounters.tree.u64TotalNodeCount - + u64StartingNodeCount); + u64StartingNodeCount >>= 9; + u64StartingNodeCount &= (MAX_INT / 4); + ctx->sMoveStack.mvf[x].iValue = + (SCORE)(u64StartingNodeCount + iScore); +#ifdef DEBUG + Trace("next_predict: %d\n", ctx->sMoveStack.mvf[x].iValue); + ASSERT(iBestScore <= iAlpha); + ASSERT(iAlpha < iBeta); +#endif + if (iScore > iBestScore) + { + iBestScore = iScore; + pi->mvBest = mv; + if (iScore > iAlpha) + { + // + // We have a best move so far. As of now it is + // the one we'll be playing. Also make sure to + // search it first at the next depth. + // +#ifdef DEBUG + Trace("Best so far... root score=%d.\n", iScore); +#endif + ctx->mvRootMove = mv; + ctx->iRootScore = iScore; + ctx->uRootDepth = uDepth; + ctx->sMoveStack.mvf[x].iValue = MAX_INT; + + // + // If there was a previous PV move then knock its + // score down so that it will be considered second + // on the next depth. + // + for (y = ctx->sMoveStack.uBegin[ctx->uPly]; + y < x; + y++) + { + if (ctx->sMoveStack.mvf[y].iValue == MAX_INT) + { + ctx->sMoveStack.mvf[y].iValue /= 2; + } + } + + UpdatePV(ctx, mv); + if (iScore >= iBeta) + { + // + // Root fail high... + // + UpdateDynamicMoveOrdering(ctx, + uDepth, + mv, + iScore, + x + 1); + UtilPrintPV(ctx, iAlpha, iBeta, iScore, mv); + KEEP_TRACK_OF_FIRST_MOVE_FHs(iBestScore == -INFINITY); + ctx->sMoveStack.mvf[x].bvFlags &= ~MVF_MOVE_SEARCHED; + goto end; + } + else + { + // + // Root PV change... + // + UtilPrintPV(ctx, iAlpha, iBeta, iScore, mv); + iAlpha = iScore; + } + } + } + g_MoveTimer.bvFlags &= ~TIMER_SEARCHING_FIRST_MOVE; + } + } + + if (iAlpha == iInitialAlpha) + { + // + // Root fail low... + // + ASSERT(iBestScore <= iAlpha); + ASSERT(PositionsAreEquivalent(pos, &pi->sPosition)); + UtilPrintPV(ctx, iAlpha, iBeta, iBestScore, mv); + } + + end: + return(iBestScore); +} + + + +static GAME_RESULT +_DetectPreMoveTerminalStates(SEARCHER_THREAD_CONTEXT *ctx, + FLAG fInCheck, + MOVE *pmv) { + ULONG u; + MOVE mv; + MOVE mvLegal; + ULONG uNumLegal = 0; + GAME_RESULT ret; + + ret.eResult = RESULT_IN_PROGRESS; + ret.szDescription[0] = '\0'; + pmv->uMove = 0; + + for (u = ctx->sMoveStack.uBegin[ctx->uPly]; + u < ctx->sMoveStack.uEnd[ctx->uPly]; + u++) { + mv = ctx->sMoveStack.mvf[u].mv; + if (MakeMove(ctx, mv)) { + mvLegal = mv; + uNumLegal += 1; + UnmakeMove(ctx, mv); + if (uNumLegal > 1) { + return ret; + } + } + } + + if (uNumLegal == 1) { + *pmv = mvLegal; + } + if (uNumLegal == 0) { + if (TRUE == fInCheck) { + if (ctx->sPosition.uToMove == WHITE) { + ret.eResult = RESULT_BLACK_WON; + strcpy(ret.szDescription, "black checkmated white"); + return ret; + } + ret.eResult = RESULT_WHITE_WON; + strcpy(ret.szDescription, "white checkmated black"); + return ret; + } + ret.eResult = RESULT_DRAW; + strcpy(ret.szDescription, "stalemate"); + } + return ret; +} + + + +static GAME_RESULT +_DetectPostMoveTerminalStates(SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + This function is called by Iterate and MakeTheMove to declare + wins/losses/draws. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + FLAG + +**/ +{ + GAME_RESULT ret; + FLAG fInCheck = InCheck(&ctx->sPosition, ctx->sPosition.uToMove); + + // Did we just make the 50th+ move without progress? + if (ctx->sPosition.uFifty >= 100) { + ret.eResult = RESULT_DRAW; + strcpy(ret.szDescription, "fifty moves without progress"); + return ret; + } + + // Did we just repeat a position for the 3rd time? + if (IsLegalDrawByRepetition()) { + ret.eResult = RESULT_DRAW; + strcpy(ret.szDescription, "third repetition of position"); + return ret; + } + + // Did we just checkmate or stalemate our opponent? The conditions + // here are the same as PreMove... so call that code. + GenerateMoves(ctx, NULLMOVE, (fInCheck ? GENERATE_ESCAPES : + GENERATE_ALL_MOVES)); + MOVE mvUnused; + return _DetectPreMoveTerminalStates(ctx, + fInCheck, + &mvUnused); +} + + +static void +_IterateSetSearchGlobals(ULONG uDepth) +{ + ULONG u, v; + ULONG uDontSplitLessThan; + + // + // Set some globals that will be used throughout this search. + // + g_uIterateDepth = uDepth; + ASSERT(g_uIterateDepth > 0); + ASSERT(g_uIterateDepth < MAX_PLY_PER_SEARCH); + + // + // For use in scaling back extensions that are very far from + // the root. + // + // Iterate g_Soft g_Hard + // | | | | | | | | | + // 0 1 2 2.5 3 3.5 4 (x Iterate) + // |-------------------|----|----|---------|----... + // |full full full full|-1/4|-1/2|-3/4 -3/4|none... + // + g_uSoftExtendLimit = g_uIterateDepth * 2; + g_uHardExtendLimit = g_uIterateDepth * 4; + for (u = 0; u < MAX_PLY_PER_SEARCH; u++) + { + if (u < g_uSoftExtendLimit) + { + g_uExtensionReduction[u] = 0; + } + else if (u < (g_uSoftExtendLimit + g_uIterateDepth / 2)) + { + g_uExtensionReduction[u] = QUARTER_PLY; + } + else if (u < (g_uSoftExtendLimit + g_uIterateDepth)) + { + g_uExtensionReduction[u] = HALF_PLY; + } + else if (u < g_uHardExtendLimit) + { + g_uExtensionReduction[u] = THREE_QUARTERS_PLY; + } + else + { + g_uExtensionReduction[u] = 5 * ONE_PLY; + } + } + + // + // Determine how much depth we need below a point in the tree in + // order to split the search (which is based on iteration depth). + // + uDontSplitLessThan = (ULONG)((double)(uDepth) * 0.30); + for (v = 0; v < MAX_PLY_PER_SEARCH; v++) + { + g_fCanSplit[v] = ((v + 1) >= uDontSplitLessThan); + } + g_fCanSplit[0] = FALSE; +} + + +#define SKIP_GRADUAL_OPENING 600 +#define INITIAL_HALF_WINDOW 75 +#define FIRST_FAIL_STEP 150 +#define SECOND_FAIL_STEP 375 + +void +_IterateWidenWindow(ULONG uColor, + SCORE iScore, + SCORE *piBound, + ULONG *puState, + int iDir) +{ + SCORE iRoughScore = g_iRootScore[uColor]; + static SCORE _Steps[] = + { + FIRST_FAIL_STEP, + SECOND_FAIL_STEP, + INFINITY + }; + +// Trace("State = %u.\n", *puState); +// Trace("Bound from %d to ", *piBound); + if ((abs(iRoughScore - iScore) > SKIP_GRADUAL_OPENING) || + (*puState == 2)) + { + *piBound = iDir * INFINITY; + *puState = 2; + } + else + { + ASSERT(*puState < 2); + *piBound = iScore; + *piBound += iDir * _Steps[*puState]; + *puState += 1; + } +// Trace("%d.\n", *piBound); +// Trace("State = %u\n", *puState); +} + + +GAME_RESULT Iterate(SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + Main iterative deepening loop for both thinking and pondering. + Call RootSearch with progressively deeper depths while there is + remaining time, we haven't found a forced mate, and there's no + user interruption. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + FLAG : is the game over? + +**/ +{ + ULONG uNumRootFailLows = 0; + ULONG uDepth; + ULONG uFailState = 0; + ULONG uColor; + ULONG u; + SCORE iAlpha = -INFINITY; + SCORE iBeta = +INFINITY; + SCORE iScore; + FLAG fInCheck = InCheck(&(ctx->sPosition), ctx->sPosition.uToMove); + MOVE mv; + GAME_RESULT ret; +#ifdef DEBUG + POSITION board; + memcpy(&board, &(ctx->sPosition), sizeof(POSITION)); + VerifyPositionConsistency(&board, FALSE); +#endif + + uColor = ctx->sPosition.uToMove; + g_iRootScore[uColor] = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE); + g_iRootScore[FLIP(uColor)] = -g_iRootScore[uColor]; + + // + // Generate moves here so that RootSearch doesn't have to. + // + ASSERT((ctx->uPly == 0) || (ctx->uPly == 1)); // 1 is under a ponder + ctx->sPlyInfo[ctx->uPly].fInCheck = fInCheck; + GenerateMoves(ctx, NULLMOVE, (fInCheck ? GENERATE_ESCAPES : + GENERATE_ALL_MOVES)); + ASSERT(ctx->sMoveStack.uBegin[0] == 0); + + // + // See if we are sitting at a checkmate or stalemate position; no + // sense searching if so. + // + ret = _DetectPreMoveTerminalStates(ctx, + fInCheck, + &mv); + if (ret.eResult != RESULT_IN_PROGRESS) { + goto end; + } + + // One legal move available? + if (mv.uMove != 0) { + ctx->mvRootMove = mv; + ctx->iRootScore = 0; + ctx->uRootDepth = 0; + ctx->sPlyInfo[0].PV[0] = mv; + ctx->sPlyInfo[0].PV[1] = NULLMOVE; + strcpy(ctx->szLastPV, "only"); + if (!g_Options.fPondering) { + Trace("ONLY MOVE --> stop searching now\n"); + g_MoveTimer.bvFlags |= TIMER_STOPPING; + g_MoveTimer.bvFlags |= TIMER_CURRENT_OBVIOUS; + } else { + Trace("ONLY PONDER --> move immediately if prediction correct.\n"); + g_MoveTimer.bvFlags |= TIMER_MOVE_IMMEDIATELY; + g_MoveTimer.bvFlags |= TIMER_CURRENT_OBVIOUS; + } + goto end; + } + + for (uDepth = 1; + uDepth <= g_Options.uMaxDepth; + uDepth++) + { + // + // Re-rank the moves based on nodecounts and mark all moves as + // not yet searched at this depth. + // + for (u = ctx->sMoveStack.uBegin[ctx->uPly]; + u < ctx->sMoveStack.uEnd[ctx->uPly]; + u++) + { + ctx->sMoveStack.mvf[u].bvFlags &= ~MVF_MOVE_SEARCHED; + } + + // + // Make sure a..b window makes sense and set some other per-depth + // globals used by the search. + // + _IterateSetSearchGlobals(uDepth); + + // + // Try to get a PV for this depth before we're out of time... + // + do + { + if (iBeta > INFINITY) iBeta = +INFINITY; + if (iAlpha < -INFINITY) iAlpha = -INFINITY; + if (iAlpha >= iBeta) iAlpha = iBeta - 1; + iScore = RootSearch(ctx, + iAlpha, + iBeta, + uDepth * ONE_PLY + HALF_PLY); + if (g_MoveTimer.bvFlags & TIMER_STOPPING) break; + mv = ctx->mvRootMove; + + // + // Got a PV, we're done with this depth. + // + if ((iAlpha < iScore) && (iScore < iBeta)) + { + ASSERT(iScore == ctx->iRootScore); + ASSERT(mv.uMove); + ASSERT(SanityCheckMove(&ctx->sPosition, mv)); + iAlpha = iScore - INITIAL_HALF_WINDOW; + iBeta = iScore + INITIAL_HALF_WINDOW; + g_iRootScore[uColor] = iScore; + g_iRootScore[FLIP(uColor)] = -iScore; + g_MoveTimer.bvFlags &= ~TIMER_RESOLVING_ROOT_FH; + g_MoveTimer.bvFlags &= ~TIMER_RESOLVING_ROOT_FL; + uFailState = 0; + (void)CheckTestSuiteMove(mv, iScore, uDepth); + break; + } + + // + // Root fail low? We'll have to research with a wider + // window. + // + else if (iScore <= iAlpha) + { + ASSERT(ctx->mvRootMove.uMove); + g_MoveTimer.bvFlags |= TIMER_RESOLVING_ROOT_FL; + uNumRootFailLows++; + if (uNumRootFailLows > 3) + { + g_MoveTimer.bvFlags |= TIMER_MANY_ROOT_FLS; + } + _IterateWidenWindow(uColor, iScore, &iAlpha, &uFailState, -1); + + // + // Consider all moves again with wider window... + // + for (u = ctx->sMoveStack.uBegin[ctx->uPly]; + u < ctx->sMoveStack.uEnd[ctx->uPly]; + u++) + { + ctx->sMoveStack.mvf[u].bvFlags &= ~MVF_MOVE_SEARCHED; + } + } + + // + // Must be a root fail high. + // + else + { + ASSERT(iScore >= iBeta); + ASSERT(mv.uMove); + ASSERT(SanityCheckMove(&ctx->sPosition, mv)); + g_MoveTimer.bvFlags |= TIMER_RESOLVING_ROOT_FH; + _IterateWidenWindow(uColor, iScore, &iBeta, &uFailState, +1); + } + } + while(1); // repeat until we run out of time or fall inside a..b + + // + // We are here because either: + // + // 1. we completed a search depth, + // or 2. we ran out of time, + // or 3. there is one legal move and we want to make it immediately, + // or 4. there was user input and we unrolled the search. + // + + // + // TODO: Scale back history between iterative depths? + // + + // + // Mate-in-n when we have searched n? Stop searching. + // + if (IS_VALID_SCORE(iScore) && + (ULONG)abs(iScore) >= (INFINITY - uDepth)) + { + Trace("FORCED MATE --> stop searching now\n"); + g_MoveTimer.bvFlags |= TIMER_STOPPING; + } + + // + // Have we reached user's maxdepth option? Stop searching. + // + if (uDepth >= g_Options.uMaxDepth) + { + Trace("DEPTH LIMIT --> stop searching now\n"); + g_MoveTimer.bvFlags |= TIMER_STOPPING; + } + + // + // Did the move timer expire? Stop searching. + // + if (g_MoveTimer.bvFlags & TIMER_STOPPING) break; + } + g_Options.u64NodesSearched = ctx->sCounters.tree.u64TotalNodeCount; + g_MoveTimer.dEndTime = SystemTimeStamp(); + + // + // Here we are at the end of a search. If we were: + // + // ...Searching then: ...Pondering then: + // + // 1. we ran out of time 1. they made a different move than + // the predicted move and we aborted + // 2. we ran out of depth + // 2. we ran out of depth + // 3. we found a mate-in-n + // 3. we found a mate-in-n + // TODO: node count limit? + // (4. if they made the predicted move + // then we converted to a search) + // + ASSERT(ctx->mvRootMove.uMove); + ASSERT(SanityCheckMove(&board, ctx->mvRootMove)); + if (g_MoveTimer.bvFlags & TIMER_RESOLVING_ROOT_FL) + { + ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly] = ctx->mvRootMove; + ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly+1] = NULLMOVE; + } + ret.eResult = RESULT_IN_PROGRESS; + ret.szDescription[0] = '\0'; + end: + return ret; +} + +void +MakeTheMove(SEARCHER_THREAD_CONTEXT *ctx) +/** + +Routine description: + + Make the move that search selected in the official game list. + +Parameters: + + SEARCHER_THREAD_CONTEXT *ctx + +Return value: + + FLAG + +**/ +{ + MOVE mv = ctx->mvRootMove; + ASSERT(mv.uMove); + + if (TRUE == g_Options.fThinking) + { + // + // TODO: keep track of how many moves in a row we are at or + // below a draw score and use this to respond to draw offers. + // + + // + // Was this a search that converted from a ponder? + // + if (TRUE == g_Options.fSuccessfulPonder) + { + if (FALSE == OfficiallyMakeMove(g_Options.mvPonder, 0, FALSE)) + { + UtilPanic(CANNOT_OFFICIALLY_MAKE_MOVE, + GetRootPosition(), + (void *)g_Options.mvPonder.uMove, + NULL, + NULL, + __FILE__, + __LINE__); + } + g_Options.fSuccessfulPonder = FALSE; + } + + // + // Tell the server about our move and actually play it on the + // root board. + // + Trace("move %s\n", MoveToSan(mv, &ctx->sPosition)); + if (FALSE == OfficiallyMakeMove(mv, g_iScore, FALSE)) + { + UtilPanic(CANNOT_OFFICIALLY_MAKE_MOVE, + GetRootPosition(), + (void *)mv.uMove, + NULL, + NULL, + __FILE__, + __LINE__); + } + if (g_Options.fVerbosePosting) + { + PostMoveSearchReport(ctx); + PostMoveTestSuiteReport(ctx); + } + } + g_Options.fPondering = g_Options.fThinking = FALSE; +} + + +GAME_RESULT +Ponder(POSITION *pos) +/** + +Routine description: + + Prepare to ponder. + +Parameters: + + POSITION *pos + +Return value: + + FLAG + +**/ +{ + static SEARCHER_THREAD_CONTEXT ctx; + GAME_RESULT ret; + + InitializeSearcherContext(pos, &ctx); + g_Options.fPondering = TRUE; + g_Options.fThinking = FALSE; + g_Options.fSuccessfulPonder = FALSE; + ret.eResult = RESULT_IN_PROGRESS; + ret.szDescription[0] = '\0'; + + // + // When do we not want to ponder + // + if ((g_Options.ePlayMode == FORCE_MODE) || (g_Options.uMyClock < 10)) + { + g_Options.fPondering = FALSE; + return ret; + } + + // + // What should we ponder? + // + g_Options.mvPonder = GetPonderMove(pos); + if (g_Options.mvPonder.uMove == 0) + { + g_Options.fPondering = FALSE; + return ret; + } + ASSERT(SanityCheckMove(pos, g_Options.mvPonder)); + + // + // Prepare to ponder by doing some maintenance on the dynamic move + // ordering scheme counters, changing the dirty tag in the hash + // code, and clearing the root nodes-per-move hash. + // + MaintainDynamicMoveOrdering(); + DirtyHashTable(); + + // + // Make the move ponder move. + // + if (FALSE == MakeMove(&ctx, g_Options.mvPonder)) + { + ASSERT(FALSE); + g_Options.fPondering = FALSE; + return ret; + } + + // + // TODO: probe the book + // + + _SetMoveTimerForPonder(); + + // + // TODO: Any preEval? + // + + // + // TODO: Set draw value + // + + MakeStatusLine(); +#if (PERF_COUNTERS && MP) + ClearHelperThreadIdleness(); +#endif + ASSERT(ctx.uPly == 1); + ret = Iterate(&ctx); + ASSERT(ctx.uPly == 1); + if (ret.eResult == RESULT_IN_PROGRESS) { + MakeTheMove(&ctx); + return _DetectPostMoveTerminalStates(&ctx); + } else { + return ret; + } +} + + +GAME_RESULT Think(POSITION *pos) +/** + +Routine description: + + Prepare to think. + +Parameters: + + POSITION *pos + +Return value: + + FLAG + +**/ +{ + static SEARCHER_THREAD_CONTEXT ctx; + MOVE mvBook; + CHAR *p; + + InitializeSearcherContext(pos, &ctx); + g_MoveTimer.bvFlags = 0; + g_Options.fPondering = FALSE; + g_Options.fThinking = TRUE; + g_Options.fSuccessfulPonder = FALSE; + + // + // Prepare to think by doing some maintenance on the dynamic move + // ordering scheme counters, changing the dirty tag in the hash + // code, and clearing the root nodes-per-move hash. + // + if (NULL != (p = PositionToFen(&(ctx.sPosition)))) + { + Trace("The root position is: %s\n", p); + SystemFreeMemory(p); + } + MaintainDynamicMoveOrdering(); + DirtyHashTable(); + + // + // Check the opening book, maybe it has a move for us. + // + if ((g_uBookProbeFailures < 3) && (!WeAreRunningASuite())) + { + mvBook = BookMove(pos, BOOKMOVE_SELECT_MOVE); + if (mvBook.uMove == 0) + { + g_uBookProbeFailures++; + } + else + { + g_uBookProbeFailures = 0; + ASSERT(SanityCheckMove(pos, mvBook)); + ctx.mvRootMove = mvBook; + MakeTheMove(&ctx); + return _DetectPostMoveTerminalStates(&ctx); + } + } + + // + // TODO: Any preEval? + // + + // + // Set time limit for move + // + SetMoveTimerForSearch(FALSE, pos->uToMove); + + // + // TODO: Set draw value + // +#if (PERF_COUNTERS && MP) + ClearHelperThreadIdleness(); +#endif + GAME_RESULT ret = Iterate(&ctx); + if (ret.eResult == RESULT_IN_PROGRESS) { + MakeTheMove(&ctx); + return _DetectPostMoveTerminalStates(&ctx); + } else { + return ret; + } +} |