/** Copyright (c) Scott Gasch Module Name: split.c Abstract: This code is the glue needed to run a parallel search. Let me encourage other chess programmers to read this code carefully. Implementing a parallel search is pretty easy and I procrastinated doing it for WAY too long because I was afraid to sink multiple months into coding it up. It's not as hard as you think. If you have a good handle on multi-threaded programming then you can do something that works pretty well in a week. Here's my system (which is not original -- I believe this is the same idea that Bruce Moreland used for Ferret and I've been told it's simiar to what Bob Hyatt does in Crafty). You want to split the search on all-nodes. There is some overhead involved in splitting the tree and, after you paid the price, you do not want one of the moves failing high... because then you have to abort the split and return a fail high. Once my search has one of these nodes, it calls in here to split the tree. What's involved with splitting the tree is: 1. populating a "split node" with data about the position we are splitting in. 2. grabbing zero or more idle "worker threads" to come help with the split. 3. all threads searching under the split grab a move from the move list and search that move's subtree in parallel. 4. when a subtree is evaluated... all threads update the split node with new information (i.e. raise alpha or, in the undesirable case that a thread failed high, toggles a flag in the split node to inform the rest of the searchers). 5. before grabbing the next move, each thread updates its local alpha to pick up window-narrowing information encountered by other threads. 6. goto step 3, stop when there are no more moves or thread finds a fail high. ------------------------------------------------------------------ This is a quote from some win32 blog about the x86 memory model which I found helpful to read while I was thinking about multithreaded code in this module: "The most familiar model is X86. It's a relatively strong model. Stores are never reordered with respect to other stores. But, in the absence of data dependence, loads can be reordered with respect to other loads and stores. Many X86 developers don't realize that this reordering is possible, though it can lead to some nasty failures under stress on big MP machines. In terms of the above, the memory model for X86 can be described as: 1. All stores are actually store.release (upward memory fence). This means that normal loads can be moved above the store.release but nothing can be moved below it. 2. All loads are normal loads. 3. Any use of the LOCK prefix (e.g. LOCK CMPXCHG or LOCK INC) creates a full memory fence." Author: Scott Gasch (scott.gasch@gmail.com) 25 Jun 2004 Revision History: $Id: split.c 345 2007-12-02 22:56:42Z scott $ **/ #ifdef MP #include "chess.h" extern ULONG g_uIterateDepth; ULONG g_uNumHelperThreads = 0; // Sized for up to 64 threads (--cpus' documented max, main.c) each // holding a handful of nested split pointers (NUM_SPLIT_PTRS_IN_CONTEXT, // chess.h) at once -- exhausting this pool just degrades gracefully // (StartParallelSearch falls back to serial search), but a ceiling // tuned for a handful of threads bites harder the more of them are // actually configured, and each SPLIT_INFO is only a few KB. #define MAX_SPLITS (64) #define IDLE ((ULONG)-1) void HelpSearch(SEARCHER_THREAD_CONTEXT *ctx, ULONG u); // // A struct that holds information about helper threads. // typedef struct _HELPER_THREAD { ULONG uHandle; volatile ULONG uAssignment; SEARCHER_THREAD_CONTEXT ctx; #ifdef PERF_COUNTERS UINT64 u64IdleCycles; UINT64 u64BusyCycles; #endif } HELPER_THREAD; // // An array of these structs that is alloced dynamically so that N // cpus is not a hardcoded thing, the engine can scale N based on // where it is running. // static HELPER_THREAD *g_HelperThreads = NULL; // // An array of structs that hold information about where we have split // the search tree. // static SPLIT_INFO g_SplitInfo[MAX_SPLITS]; // // In addition to this main split database lock each split entry has // its own private lock. This way contention between searcher threads // operating on different split nodes is eliminated. // volatile static ULONG g_uSplitLock = 0; #define SPLITS_LOCKED (g_uSplitLock != 0) #define LOCK_SPLITS \ AcquireSpinLock(&g_uSplitLock); \ ASSERT(SPLITS_LOCKED); #define UNLOCK_SPLITS \ ASSERT(SPLITS_LOCKED); \ ReleaseSpinLock(&g_uSplitLock); static ULONG g_uNumSplitsAvailable; volatile ULONG g_uNumHelpersAvailable; ULONG HelperThreadIdleLoop(IN ULONG uMyId) /** Routine description: The entry point of a helper thread. It will spin in the idle loop here until another thread splits the search tree, sees that it is idle, and notifies it to come help by changing the assignment field in its struct. Parameters: ULONG uMyId : this thread's index in g_HelperThreads Return value: ULONG **/ { SEARCHER_THREAD_CONTEXT *ctx = &(g_HelperThreads[uMyId].ctx); ULONG u, v; MOVE mv; #ifdef PERF_COUNTERS ULONG uIdleLoops = 0; UINT64 u64Then; UINT64 u64Now; #endif #ifdef DEBUG POSITION board; #endif InitializeSearcherContext(NULL, ctx); ctx->uThreadNumber = uMyId + 1; do { #ifdef PERF_COUNTERS if (uIdleLoops == 0) u64Then = SystemReadTimeStampCounter(); #endif // // Did someone tell us to come help? // if ((u = g_HelperThreads[uMyId].uAssignment) != IDLE) { // // By now the split info is populated. // #ifdef PERF_COUNTERS uIdleLoops = 0; #endif ReInitializeSearcherContext(&(g_SplitInfo[u].sRootPosition), ctx); ctx->pSplitInfo[0] = &(g_SplitInfo[u]); // // Note: the main thread could have already exhausted the // split and decremented it from 3->2. When we leave it // will fall to 1 and allow the main thread to continue. // ASSERT(g_SplitInfo[u].uNumThreadsHelping >= 2); // // Get from the root of the search to the split position. // We do this instead of just initializing the searcher // context at the split node so that historic things like // draw detection still work in the helper threads. // v = 0; do { ASSERT(v < MAX_PLY_PER_SEARCH); mv.uMove = g_SplitInfo[u].mvPathToHere[v].uMove; if (ILLEGALMOVE == mv.uMove) break; #ifdef DEBUG if (mv.uMove) { ASSERT(SanityCheckMove(&ctx->sPosition, mv)); } #endif if (FALSE == MakeMove(ctx, mv)) { UtilPanic(CANNOT_INITIALIZE_SPLIT, &ctx->sPosition, (void *)(size_t)mv.uMove, &g_SplitInfo[u], (void *)(size_t)v, __FILE__, __LINE__); } v++; } while(1); #ifdef DEBUG ASSERT(g_SplitInfo[u].uSplitPly == ctx->uPly); ASSERT(v > 0); ASSERT(IS_SAME_MOVE(g_SplitInfo[u].mvPathToHere[v-1], g_SplitInfo[u].mvLast)); ASSERT(PositionsAreEquivalent(&(ctx->sPosition), &(g_SplitInfo[u].sSplitPosition))); VerifyPositionConsistency(&(ctx->sPosition), FALSE); memcpy(&board, &(ctx->sPosition), sizeof(POSITION)); #endif // // Populate the move stack of this helper context to make // it look like it generated to moves at the split. The // reason I do this is so that ComputeMoveExtension (which // looks at the move stack) will work at a split node even // if the context it gets is a helper thread's. // ctx->sMoveStack.uBegin[ctx->uPly] = 0; ctx->sMoveStack.uBegin[ctx->uPly + 1] = ctx->sMoveStack.uEnd[ctx->uPly] = g_SplitInfo[u].uNumMoves; for (v = 0; v < g_SplitInfo[u].uNumMoves; v++) { ctx->sMoveStack.mvf[v] = g_SplitInfo[u].mvf[v]; ASSERT(SanityCheckMove(&ctx->sPosition, g_SplitInfo[u].mvf[v].mv)); } // // Go help with the search // HelpSearch(ctx, u); ASSERT(PositionsAreEquivalent(&board, &(ctx->sPosition))); // // Done with this assignment, wrap up and go back to idle state // LOCK_SPLITS; g_HelperThreads[uMyId].uAssignment = IDLE; g_uNumHelpersAvailable++; UNLOCK_SPLITS; #ifdef PERF_COUNTERS u64Now = SystemReadTimeStampCounter(); g_HelperThreads[uMyId].u64BusyCycles += (u64Now - u64Then); #endif } #if PERF_COUNTERS // // There was nothing for us to do, if that happens often // enough remember the idle cycles. // else { uIdleLoops++; if (uIdleLoops > 1000) { u64Now = SystemReadTimeStampCounter(); LOCK_SPLITS; g_HelperThreads[uMyId].u64IdleCycles += (u64Now - u64Then); UNLOCK_SPLITS; uIdleLoops = 0; #ifdef DEBUG SystemDeferExecution(1); #endif } } #endif } while(FALSE == g_fExitProgram); Trace("HELPER THREAD: thread terminating.\n"); return(0); // ExitThread } FLAG InitializeParallelSearch(void) /** Routine description: This routine must be called before any thread can split the search tree because it sets up the parallel search system. Parameters: void Return value: FLAG **/ { ULONG u; if (g_Options.uNumProcessors < 2) return(FALSE); // // Initialize split entries // g_uSplitLock = 0; for (u = 0; u < MAX_SPLITS; u++) { memset(&(g_SplitInfo[u]), 0, sizeof(g_SplitInfo[u])); } g_uNumSplitsAvailable = MAX_SPLITS; ASSERT(NUM_SPLIT_PTRS_IN_CONTEXT <= MAX_SPLITS); // // Create and initialize helper threads // g_uNumHelperThreads = g_Options.uNumProcessors - 1; ASSERT(g_uNumHelperThreads >= 1); g_HelperThreads = SystemAllocateMemory(sizeof(HELPER_THREAD) * g_uNumHelperThreads); ASSERT(g_HelperThreads != NULL); for (u = 0; u < g_uNumHelperThreads; u++) { memset(&(g_HelperThreads[u]), 0, sizeof(g_HelperThreads[u])); g_HelperThreads[u].uAssignment = IDLE; if (FALSE == SystemCreateThread(HelperThreadIdleLoop, u, &(g_HelperThreads[u].uHandle))) { UtilPanic(UNEXPECTED_SYSTEM_CALL_FAILURE, NULL, "creating a thread", 0, NULL, __FILE__, __LINE__); } } g_uNumHelpersAvailable = g_uNumHelperThreads; return(TRUE); } #ifdef PERF_COUNTERS void ClearHelperThreadIdleness(void) /** Routine description: Called at the start of a search, if PERF_COUNTERS is defined... this function's job is to reset the idleness counter for all helper threads. Parameters: void Return value: void **/ { ULONG u; LOCK_SPLITS; for (u = 0; u < g_uNumHelperThreads; u++) { g_HelperThreads[u].u64BusyCycles = g_HelperThreads[u].u64IdleCycles = 0ULL; } UNLOCK_SPLITS; } void DumpHelperIdlenessReport(void) /** Routine description: Called at the end of a search, this function's job is to print out a report of how busy/idle each helper threads was. Parameters: void Return value: void **/ { ULONG u; double n, d; for (u = 0; u < g_uNumHelperThreads; u++) { n = (double)g_HelperThreads[u].u64BusyCycles; d = (double)g_HelperThreads[u].u64IdleCycles; d += n; Trace("Helper thread %u: %5.2f percent busy.\n", u, (n / d) * 100.0); } } #endif FLAG CleanupParallelSearch(void) /** Routine description: Cleanup parallel search system before program shutdown. Parameters: void Return value: FLAG **/ { if (g_HelperThreads != NULL ) { SystemFreeMemory(g_HelperThreads); } g_uNumHelperThreads = 0; return(TRUE); } SCORE StartParallelSearch(IN SEARCHER_THREAD_CONTEXT *ctx, IN OUT SCORE *piAlpha, IN SCORE iBeta, IN SCORE iImprovement, IN OUT SCORE *piBestScore, IN OUT MOVE *pmvBest, IN ULONG uMoveNum, IN INT iPositionExtend, IN ULONG uDepth, IN FLAG fThreat, IN BITBOARD bbMinorAttacksSnapshot[2], IN BITBOARD bbRookAttacksSnapshot[2]) { /** Routine description: This routine is called from the main Search (not RootSearch or QSearch) when: 1. it thinks the current search tree node looks like it could be searched in parallel -and- 2. it's likely that there are idle helper thread(s) to help. It job is to find a free split node, populate it, find idle helper threads, assign them to help, and search this node in parallel. It _must_ be called after generating moves at this node. Parameters: SEARCHER_THREAD_CONTEXT *ctx : context of thread requesting split SCORE *piAlpha : in/out alpha of split node SCORE iBeta : in only (beta doesn't change) beta of split node SCORE *piBestScore : in/out best score seen so far at split node MOVE *pmvBest : in/out best move seen so far at split node ULONG uMoveNum : in next move number in ctx->sMoveStack INT iPositionExtend : in position based extensions for split node ULONG uDepth : in the depth we need to search to FLAG fThreat : in whether a node-wide threat extension is in play at the split point -- stashed into g_SplitInfo so a future HelpSearch() can call CanWeReduceOrPruneMove's real gate instead of its own hand-rolled approximation BITBOARD bbMinorAttacksSnapshot[2] : in the originating thread's own attack-table snapshots (see search.c's fParentAttackTablesAreFresh) -- stashed into g_SplitInfo for the same reason as fThreat; helper threads have no other way to get a non-zero snapshot BITBOARD bbRookAttacksSnapshot[2] : in, same as bbMinorAttacksSnapshot Return value: SCORE : the score of this split subtree, along with out params above **/ SCORE iScore; ULONG u, v; ULONG uSplitNum; ULONG uOldStart; #ifdef DEBUG POSITION board; ASSERT(IS_VALID_SCORE(*piAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(IS_VALID_SCORE(*piBestScore)); ASSERT(*piBestScore > -INFINITY_SCORE); ASSERT(pmvBest->uMove); ASSERT(*piAlpha < iBeta); memcpy(&board, &(ctx->sPosition), sizeof(POSITION)); VerifyPositionConsistency(&board, FALSE); #endif // // Note: This is a lazy lock construction: search.c has peeked at // g_uNumHelperThreads before calling us and only calls when it // thinks there's a helper available. (1) We could find that // there is no helper available now because of the race condition. // (2) On IA64 memory model this type of construct is // _not_supported_ (my understanding is that this is supported on // X86 and AMD64, though). // LOCK_SPLITS; for (u = 0; u < MAX_SPLITS; u++) { // // Try to find a vacant split // if (g_SplitInfo[u].uNumThreadsHelping == 0) { // // Found one, populate it. // ASSERT(g_uNumSplitsAvailable > 0); g_uNumSplitsAvailable--; // // We initialize this to two to double-reference this // split node. This guarantees we are the last ones // holding a reference to it (since we want to be the last // one out of this split node) // g_SplitInfo[u].uNumThreadsHelping = 2; // // Store the path from the root to the split node and the // root position to start at. This is done so that // ponders that convert into searches don't crash us and // so that helper threads can detect repeated positions // before the split point. // ASSERT(ctx->uPly >= 1); ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH); for (v = 0; v < ctx->uPly; v++) { g_SplitInfo[u].mvPathToHere[v] = ctx->sPlyInfo[v].mv; } g_SplitInfo[u].mvPathToHere[v].uMove = ILLEGALMOVE; ASSERT(v >= 1); g_SplitInfo[u].mvLast = g_SplitInfo[u].mvPathToHere[v-1]; memcpy(&(g_SplitInfo[u].sRootPosition), GetRootPosition(), sizeof(POSITION)); g_SplitInfo[u].iEval = ctx->sPlyInfo[ctx->uPly].iEval; g_SplitInfo[u].iImprovement = iImprovement; g_SplitInfo[u].fThreat = fThreat; g_SplitInfo[u].bbMinorAttacksSnapshot[WHITE] = bbMinorAttacksSnapshot[WHITE]; g_SplitInfo[u].bbMinorAttacksSnapshot[BLACK] = bbMinorAttacksSnapshot[BLACK]; g_SplitInfo[u].bbRookAttacksSnapshot[WHITE] = bbRookAttacksSnapshot[WHITE]; g_SplitInfo[u].bbRookAttacksSnapshot[BLACK] = bbRookAttacksSnapshot[BLACK]; g_SplitInfo[u].eNodeType = ctx->sPlyInfo[ctx->uPly].eNodeType; #if DEBUG g_SplitInfo[u].uSplitPly = ctx->uPly; memcpy(&(g_SplitInfo[u].sSplitPosition), &(ctx->sPosition), sizeof(POSITION)); #endif // // What has happened here is that another thread has // triggered the "stop searching" bit in the move timer. // This also means that the root position may have changed // and therefore the split we just populated can be // useless. Before we grab any helper threads, see if we // need to bail out of this split. // if (g_MoveTimer.bvFlags & TIMER_STOPPING) { g_uNumSplitsAvailable++; g_SplitInfo[u].uNumThreadsHelping = 0; UNLOCK_SPLITS; return(INVALID_SCORE); } // // More split node initialization // g_SplitInfo[u].uLock = 0; g_SplitInfo[u].fTerminate = FALSE; g_SplitInfo[u].uDepth = uDepth; g_SplitInfo[u].iPositionExtend = iPositionExtend; g_SplitInfo[u].iAlpha = *piAlpha; g_SplitInfo[u].iBeta = iBeta; g_SplitInfo[u].sSearchFlags = ctx->sSearchFlags; ASSERT(FALSE == ctx->sSearchFlags.fAvoidNullmove); g_SplitInfo[u].mvBest = *pmvBest; g_SplitInfo[u].iBestScore = *piBestScore; ASSERT(g_SplitInfo[u].iBestScore <= g_SplitInfo[u].iAlpha); g_SplitInfo[u].sCounters.tree.u64TotalNodeCount = 0; g_SplitInfo[u].sCounters.tree.u64BetaCutoffs = 0; g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove = 0; g_SplitInfo[u].sCounters.tree.u64LeftoverTries = 0; g_SplitInfo[u].sCounters.tree.u64LeftoverAlpha = 0; g_SplitInfo[u].sCounters.tree.u64LeftoverFH = 0; g_SplitInfo[u].PV[0] = NULLMOVE; // // Copy the remaining moves to be searched from the // searcher context that called us into the split node. // Note: this thread must have already called // GenerateMoves at the split node! // uOldStart = ctx->sMoveStack.uBegin[ctx->uPly]; g_SplitInfo[u].uAlreadyDone = uMoveNum - uOldStart + 1; ASSERT(g_SplitInfo[u].uAlreadyDone >= 1); ctx->sMoveStack.uBegin[ctx->uPly] = uMoveNum; for (v = uMoveNum, g_SplitInfo[u].uRemainingMoves = 0; (v < ctx->sMoveStack.uEnd[ctx->uPly]); v++, g_SplitInfo[u].uRemainingMoves++) { ASSERT(g_SplitInfo[u].uRemainingMoves >= 0); ASSERT(g_SplitInfo[u].uRemainingMoves < MAX_MOVES_PER_PLY); // // If we fail high at this node we have done a lot of // work for naught. We also want to know as soon as // possible so that we can vacate this split point, // free up a worker thread and get back to the main // search. So sort the whole list of moves from // best..worst (search.c's main loop does the same // unconditionally now too -- see its retired // NumLeftoverMovesToSelect budget comment). // // Recompute WouldGiveCheck unconditionally, even for // v == uMoveNum (whose check bit Search()'s own loop // already set moments ago, before deciding to split). // g_HistoryCounters/g_ContinuationHistory -- which // SelectBestWithHistory's scan above just read to rank // candidates -- are process-global and written by // every other searcher thread with no lock. Between // that earlier selection and this one, another thread // can mutate them enough to change which move wins // the [uMoveNum, uEnd) scan, swapping a DIFFERENT move // into slot uMoveNum than the one Search() originally // selected -- one whose check bit was never computed. // The stale/garbage bit that move inherited from // whatever slot it came from was then handed to a // helper thread via g_SplitInfo[u].mvf[], tripping // HelpSearch's own IS_CHECKING_MOVE/InCheck ASSERT (or, // in a release build, corrupting move generation // further down the line) -- confirmed nondeterministic // across runs and reproducible pre-dating this fix, at // --cpus 4 only (needs real concurrent writers to the // history tables). The extra WouldGiveCheck call this // costs is now just part of split overhead, not a // per-node cost -- this loop only ever runs once per // split, not once per move tried. SelectBestWithHistory(ctx, v); ctx->sMoveStack.mvf[v].mv.bvFlags |= WouldGiveCheck(ctx, ctx->sMoveStack.mvf[v].mv); ASSERT(!(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED)); g_SplitInfo[u].mvf[g_SplitInfo[u].uRemainingMoves] = ctx->sMoveStack.mvf[v]; #ifdef DEBUG ctx->sMoveStack.mvf[v].bvFlags |= MVF_MOVE_SEARCHED; #endif } g_SplitInfo[u].uOnDeckMove = 0; g_SplitInfo[u].uNumMoves = g_SplitInfo[u].uRemainingMoves; #ifdef DEBUG for (v = uMoveNum; v < ctx->sMoveStack.uEnd[ctx->uPly]; v++) { ASSERT(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED); ASSERT(SanityCheckMove(&ctx->sPosition, ctx->sMoveStack.mvf[v].mv)); } #endif // // See if we can get some help here or we have to go it // alone. Note: past this point the split we are using // may have threads under it -- be careful. // for (v = 0; v < g_uNumHelperThreads; v++) { if (g_HelperThreads[v].uAssignment == IDLE) { // // Note: there could already be a thread searching // this split; we must obtain its lock now to mess // with the helper count. // AcquireSpinLock(&(g_SplitInfo[u].uLock)); g_SplitInfo[u].uNumThreadsHelping += 1; ReleaseSpinLock(&(g_SplitInfo[u].uLock)); ASSERT(g_SplitInfo[u].uNumThreadsHelping > 2); ASSERT(g_uNumHelpersAvailable > 0); g_uNumHelpersAvailable -= 1; ASSERT(g_uNumHelpersAvailable >= 0); ASSERT(g_uNumHelpersAvailable < g_uNumHelperThreads); g_HelperThreads[v].uAssignment = u; } } UNLOCK_SPLITS; // // Update the context of the thread that is initiating the // split with a pointer to the split info node we are using. // for (uSplitNum = 0; uSplitNum < NUM_SPLIT_PTRS_IN_CONTEXT; uSplitNum++) { if (ctx->pSplitInfo[uSplitNum] == NULL) { ctx->pSplitInfo[uSplitNum] = &(g_SplitInfo[u]); break; } } if (uSplitNum >= NUM_SPLIT_PTRS_IN_CONTEXT) { ASSERT(FALSE); return(INVALID_SCORE); } ASSERT(ctx->pSplitInfo[uSplitNum] == &(g_SplitInfo[u])); // // Go search it // INC(ctx->sCounters.parallel.uNumSplits); HelpSearch(ctx, u); // // We are done searching under this node... make sure all // helpers are done too. When everyone is finished the // refcount on this split node will be one because every // thread decremented it once and we double referenced // it initially. // while(g_SplitInfo[u].uNumThreadsHelping != 1) { ASSERT(g_SplitInfo[u].uNumThreadsHelping != 0); if (g_fExitProgram) break; } // // Note: past this point we are the only ones using the // split until we return it to the pool by making its // refcount zero again. // #ifdef DEBUG ASSERT((g_SplitInfo[u].uNumThreadsHelping == 1) || (g_fExitProgram)); SystemDeferExecution(rand() % 2); ASSERT((g_SplitInfo[u].uNumThreadsHelping == 1) || (g_fExitProgram)); // "fail-low implies every candidate at this split was // actually searched" no longer universally holds now that // HelpSearch() calls SearchOneMove: a helper thread can // legitimately stop pulling moves from THIS split's pool // on MOVE_KERNEL_ABORTED even while this split itself is // failing low on its own terms, because // WE_SHOULD_STOP_SEARCHING's MP definition (chess.h) also // covers ThreadUnderTerminatingSplit(ctx) -- an ANCESTOR // split further up this thread's call stack can terminate // (its own fail-high) independent of how this split is // doing, and that's a global-enough signal to stop // grinding through a doomed split's remaining moves rather // than a bug. WE_SHOULD_STOP_SEARCHING is otherwise sticky // for the remainder of this search, so checking it here // (after every helper thread has already returned) still // correctly distinguishes "we exhausted the pool normally" // from "we bailed early for a legitimate reason." if ((g_SplitInfo[u].iBestScore < g_SplitInfo[u].iBeta) && (!WE_SHOULD_STOP_SEARCHING)) { for (v = 0; v < g_SplitInfo[u].uRemainingMoves; v++) { ASSERT(g_SplitInfo[u].mvf[v].mv.uMove); ASSERT(g_SplitInfo[u].mvf[v].bvFlags & MVF_MOVE_SEARCHED); } } #endif #ifdef PERF_COUNTERS // // Grab counters. Technically we should do with under a // lock b/c we want to ensure that any pending memory // operations from other cpus are flushed. But I don't // really care too much about these counters and am trying // to reduce lock contention. // if (TRUE == g_SplitInfo[u].fTerminate) { ASSERT(g_SplitInfo[u].iBestScore >= g_SplitInfo[u].iBeta); INC(ctx->sCounters.parallel.uNumSplitsTerminated); } ctx->sCounters.tree.u64BetaCutoffs = g_SplitInfo[u].sCounters.tree.u64BetaCutoffs; ctx->sCounters.tree.u64BetaCutoffsOnFirstMove = g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove; ctx->sCounters.tree.u64LeftoverTries = g_SplitInfo[u].sCounters.tree.u64LeftoverTries; ctx->sCounters.tree.u64LeftoverAlpha = g_SplitInfo[u].sCounters.tree.u64LeftoverAlpha; ctx->sCounters.tree.u64LeftoverFH = g_SplitInfo[u].sCounters.tree.u64LeftoverFH; #endif // // Pop off the split info ptr from the stack in the thread's // context. // ASSERT(ctx->pSplitInfo[uSplitNum] == &(g_SplitInfo[u])); ctx->pSplitInfo[uSplitNum] = NULL; // // Grab alpha, bestscore, bestmove, PV etc... The lock // needs to be here to flush any pending memory writes // from other processors. // LOCK_SPLITS; ctx->sCounters.tree.u64TotalNodeCount = g_SplitInfo[u].sCounters.tree.u64TotalNodeCount; iScore = *piBestScore = g_SplitInfo[u].iBestScore; *pmvBest = g_SplitInfo[u].mvBest; if ((*piAlpha < iScore) && (iScore < iBeta)) { ASSERT(IS_SAME_MOVE(*pmvBest, g_SplitInfo[u].PV[0])); ASSERT((*pmvBest).uMove != 0); v = 0; do { ASSERT((ctx->uPly + v) < MAX_PLY_PER_SEARCH); ASSERT(v < MAX_PLY_PER_SEARCH); ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly+v] = g_SplitInfo[u].PV[v]; if (0 == g_SplitInfo[u].PV[v].uMove) break; v++; } while(1); } *piAlpha = g_SplitInfo[u].iAlpha; ASSERT(iBeta == g_SplitInfo[u].iBeta); g_uNumSplitsAvailable++; g_SplitInfo[u].uNumThreadsHelping = 0; UNLOCK_SPLITS; ctx->sMoveStack.uBegin[ctx->uPly] = uOldStart; #ifdef DEBUG ASSERT(PositionsAreEquivalent(&board, &ctx->sPosition)); VerifyPositionConsistency(&ctx->sPosition, FALSE); ASSERT(IS_VALID_SCORE(iScore) || WE_SHOULD_STOP_SEARCHING); #endif return(iScore); } } // // There was no split available for us; unlock and continue in // search. // UNLOCK_SPLITS; return(INVALID_SCORE); } static void _UpdateSplitInfo(IN SEARCHER_THREAD_CONTEXT *ctx, IN MOVE mv, IN SCORE iScore, IN ULONG u) /** Routine description: We think we have some information learned from search to store in the split node. Take the lock and see if we really do. Parameters: SEARCHER_THREAD_CONTEXT *ctx : context of thread updating split MOVE mv : move it just searched SCORE iScore : score of the move's subtree ULONG u : split node number Return value: static void **/ { ULONG v; AcquireSpinLock(&(g_SplitInfo[u].uLock)); // // See if this split is shutting down // if (TRUE == g_SplitInfo[u].fTerminate) { ReleaseSpinLock(&(g_SplitInfo[u].uLock)); return; } if (iScore > g_SplitInfo[u].iBestScore) { // // We found a move better than the best so far, so we want to // update the split node and possibly raise alpha. // g_SplitInfo[u].iBestScore = iScore; g_SplitInfo[u].mvBest = mv; if (iScore > g_SplitInfo[u].iAlpha) { if (iScore >= g_SplitInfo[u].iBeta) { // // We failed high so we want to update the split node. // Do NOT touch g_SplitInfo[u].iAlpha here -- the caller // (StartParallelSearch's caller in search.c) asserts // iAlpha stays < iBeta after a split returns, and // detects fail-high purely via iBestScore/iScore, not // via alpha having moved. (See search.c's handling of // this return for the other half of this fix: it must // special-case iBestScore >= iBeta itself rather than // falling into the generic no_more_moves classifier, // which infers "exact score" vs. "fail-high" purely // from whether alpha moved.) // g_SplitInfo[u].fTerminate = TRUE; g_SplitInfo[u].PV[0] = NULLMOVE; ReleaseSpinLock(&(g_SplitInfo[u].uLock)); return; } // // Normal PV move, update the split's PV. // g_SplitInfo[u].iAlpha = iScore; UpdatePV(ctx, mv); ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH); ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove); for (v = 0; v < MAX_PLY_PER_SEARCH; v++) { ASSERT((ctx->uPly + v) < MAX_PLY_PER_SEARCH); mv = ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly + v]; g_SplitInfo[u].PV[v] = mv; if (0 == mv.uMove) break; } } } ReleaseSpinLock(&(g_SplitInfo[u].uLock)); } static void _SetFinalStats(IN SEARCHER_THREAD_CONTEXT *ctx, IN ULONG u) /** Routine description: We are exiting the split node (because it ran out of moves or because someone failed high). Update some stats on the way out. Parameters: SEARCHER_THREAD_CONTEXT *ctx, ULONG u Return value: static void **/ { // // Before we stop searching this node, update some stuff. // AcquireSpinLock(&(g_SplitInfo[u].uLock)); // // Counters to persist in the main counter struct via the split. // g_SplitInfo[u].sCounters.tree.u64TotalNodeCount += ctx->sCounters.tree.u64TotalNodeCount; g_SplitInfo[u].sCounters.tree.u64BetaCutoffs += ctx->sCounters.tree.u64BetaCutoffs; g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove += ctx->sCounters.tree.u64BetaCutoffsOnFirstMove; g_SplitInfo[u].sCounters.tree.u64LeftoverTries += ctx->sCounters.tree.u64LeftoverTries; g_SplitInfo[u].sCounters.tree.u64LeftoverAlpha += ctx->sCounters.tree.u64LeftoverAlpha; g_SplitInfo[u].sCounters.tree.u64LeftoverFH += ctx->sCounters.tree.u64LeftoverFH; // // TODO: Any other counters we care about? // // // IDEA: Save the killers from this context to bring back to main // // // Decrement threadcount in this split. Note: the main thread // incremented it by two. // ASSERT((g_SplitInfo[u].uNumThreadsHelping > 1) || (g_fExitProgram)); g_SplitInfo[u].uNumThreadsHelping -= 1; ASSERT((g_SplitInfo[u].uNumThreadsHelping >= 1) || (g_fExitProgram)); ReleaseSpinLock(&(g_SplitInfo[u].uLock)); } static MOVE _GetNextParallelMove(OUT SCORE *piAlpha, OUT SCORE *piBestScore, OUT ULONG *puMoveNumber, IN ULONG u) /** Routine description: Retrieve the next parallel move to search at the split node. Also update alpha and bestscore. Parameters: SCORE *piAlpha : current alpha SCORE *piBestScore : current bestscore ULONG u : split number Return value: static MOVE **/ { MOVE mv = {0}; AcquireSpinLock(&(g_SplitInfo[u].uLock)); if (g_SplitInfo[u].fTerminate) { ReleaseSpinLock(&(g_SplitInfo[u].uLock)); return(mv); } if (g_SplitInfo[u].uRemainingMoves != 0) { // // There is another move to search, get it. // mv = g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].mv; #ifdef DEBUG ASSERT(!(g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags & MVF_MOVE_SEARCHED)); g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags |= MVF_MOVE_SEARCHED; ASSERT(mv.uMove); ASSERT(SanityCheckMove(&g_SplitInfo[u].sSplitPosition, mv)); #endif g_SplitInfo[u].uRemainingMoves--; *puMoveNumber = g_SplitInfo[u].uOnDeckMove; g_SplitInfo[u].uOnDeckMove++; } *piAlpha = g_SplitInfo[u].iAlpha; *piBestScore = g_SplitInfo[u].iBestScore; ReleaseSpinLock(&(g_SplitInfo[u].uLock)); ASSERT(*piBestScore <= *piAlpha); return(mv); } void HelpSearch(IN OUT SEARCHER_THREAD_CONTEXT *ctx, IN ULONG u) /** Routine description: Help search the split position. Parameters: SEARCHER_THREAD_CONTEXT *ctx : thread context ULONG u : the split index to help search Return value: void **/ { SCORE iScore; SCORE iAlpha = 0; SCORE iBeta; SCORE iBestScore = 0; ULONG uOrigDepth; ULONG uDepth; ULONG uMoveNum = 0; INT iOrigExtend; MOVE mv; ULONG uRawDepthB; ULONG uRawImproveB; MOVE_KERNEL_RESULT eMoveKernelResult; #ifdef DEBUG POSITION board; memcpy(&board, &ctx->sPosition, sizeof(POSITION)); ASSERT(PositionsAreEquivalent(&board, &g_SplitInfo[u].sSplitPosition)); // SearchOneMove's own post-UnmakeMove sanity ASSERT compares against // ctx->sPlyInfo[ctx->uPly].sPosition (pi->sPosition), the same DEBUG- // only field Search() populates once at node entry (search.c's own // opening memcpy). A helper thread never calls Search()/ // CommonSearchInit for the split-point ply itself -- see eNodeType's // own comment in SPLIT_INFO (chess.h) for why -- so that slot in // THIS thread's own persistent ctx is otherwise stale leftover data // from whatever unrelated node it last helped with. Populate it // here, once, before the move loop (ctx->uPly doesn't change across // iterations -- each one returns here via MakeMove/UnmakeMove before // the next _GetNextParallelMove call), matching Search()'s own // convention so the kernel's ASSERT means the same thing for both // callers. memcpy(&ctx->sPlyInfo[ctx->uPly].sPosition, &ctx->sPosition, sizeof(POSITION)); #endif iOrigExtend = g_SplitInfo[u].iPositionExtend; iBeta = g_SplitInfo[u].iBeta; uOrigDepth = g_SplitInfo[u].uDepth; ctx->sSearchFlags = g_SplitInfo[u].sSearchFlags; SCORE iEval = g_SplitInfo[u].iEval; // Node-level hoists -- node-constant for the life of this split // (same convention search.c's own move loop uses: compute once, // not once per move). g_SplitInfo[u].iImprovement is real input // here (unlike the GetLMRReduction parameter removed 2026-10-04 -- // see this field's own chess.h comment), feeding the joint-table // lookup SearchOneMove now does internally via CanWeReduceOrPruneMove/ // ShouldLatePrune, which this call site never had before. uRawDepthB = DepthBucket(uOrigDepth / ONE_PLY); uRawImproveB = ImproveBucket(g_SplitInfo[u].iImprovement); do { ULONG uLegalMoves; ULONG x; #ifdef PERF_COUNTERS FLAG fMoveIsPruneReduceEligibleUnused; ULONG uThisMoveHangBucketUnused; ULONG uThisMoveGapBucketUnused; ULONG uThisMoveNumBucketUnused; ULONG uThisMoveDepthBucketUnused; #endif #ifdef TEST_NULL UINT64 uNullCalibFirstMoveNodeCostUnused; #endif #ifdef FH_REGRESSION_COLLECTION // The MP split path is deliberately uninstrumented (collection // runs at --cpus 1, see docs/REGRESSION.md) -- this sink // exists only so this call site's argument list matches // SearchOneMove's prototype. SCORE iFhCollectMoveValueUnused; #endif uDepth = uOrigDepth; ASSERT(ctx->uPly == g_SplitInfo[u].uSplitPly); mv = _GetNextParallelMove(&iAlpha, &iBestScore, &uMoveNum, u); if (mv.uMove == 0) break; // Split is terminating ASSERT(IS_VALID_SCORE(iBestScore)); ASSERT(uMoveNum < MAX_MOVES_PER_PLY); ASSERT( IS_SAME_MOVE(mv, ctx->sMoveStack.mvf[ctx->sMoveStack.uBegin[ctx->uPly]+uMoveNum].mv ) ); ASSERT(uDepth <= MAX_DEPTH_PER_SEARCH); ASSERT(IS_VALID_SCORE(iAlpha)); ASSERT(IS_VALID_SCORE(iBeta)); ASSERT(iAlpha < iBeta); // x such that (x - 1) is mv's own absolute index in // ctx->sMoveStack -- same convention search.c's move loop // uses (there, x is already one past the move being tried; // here, uBegin[ctx->uPly] + uMoveNum IS that move's absolute // index, computed pre-MakeMove while ctx->uPly is still the // split ply, so + 1 reproduces the same "(x - 1) == absolute // index" relationship SearchOneMove's other callers rely on). x = ctx->sMoveStack.uBegin[ctx->uPly] + uMoveNum + 1; // Pre-increment count: SearchOneMove itself does // (*puLegalMoves)++ right after MakeMove succeeds, so passing // the already-"+1" uAlreadyDone + uMoveNum + 1 here would // double-count. uAlreadyDone + uMoveNum is this move's own // 0-based ordinal among every move tried at this split node so // far (across every helper thread); the kernel's own // increment turns it into the right 1-based count. uLegalMoves = g_SplitInfo[u].uAlreadyDone + uMoveNum; // fFullWindow is always FALSE here, never ASSERT-worthy of // being TRUE: a helper thread's first move off the shared pool // is never this node's actual first move -- search.c's own // move loop (uLegalMoves==1, full a..b window) already // searched the real first move before any split could launch // (uAlreadyDone >= 1 always). See SearchOneMove's own // fFullWindow parameter comment (chess.h) for why this can't // be inferred from a sentinel the way the old inline code did. // // fIsGeneratedMoveStage is always TRUE: HelpSearch only ever // pulls from the generated-move pool handed off at split-launch // time, never a hash move. // // fIsLeftoverMove is always TRUE: search.c only ever starts a // split when the move it was about to try was itself already // classified as a leftover move -- every move HelpSearch pulls // from the shared pool for that split is drawn from that same // leftover range. // // g_SplitInfo[u].fThreat/bbMinorAttacksSnapshot/ // bbRookAttacksSnapshot are the real values from the // originating thread (chess.h/split.c split-launch plumbing), // not the zeroed snapshots and missing fThreat this call site // used to have -- this is the actual unification: CanWeReduceOrPruneMove's // real 9-check+2-exemption gate and ShouldLatePrune's LMP now // run here for the first time, instead of the hand-rolled // 7-condition approximation (missing the SEE-negative-capture // carve-out, the mate-magnitude-alpha check, fThreat, and both // move-identity exemptions) this function used before. // // MOVE_ORDERING_EVIDENCE_COLLECTION/TEST_NULL instrumentation // is deliberately never exercised from a helper thread -- both // are single-threaded-only diagnostics by design (confirmed // with the user), so FALSE/0/throwaway-output is correct here, // not a gap to fill in later. eMoveKernelResult = SearchOneMove(ctx, mv, x, TRUE, // fIsGeneratedMoveStage uDepth, iAlpha, iBeta, iEval, iOrigExtend, // iPositionalExtend TRUE, // fIsLeftoverMove g_SplitInfo[u].fThreat, FALSE, // fFullWindow uRawDepthB, uRawImproveB, g_SplitInfo[u].bbMinorAttacksSnapshot, g_SplitInfo[u].bbRookAttacksSnapshot, #ifdef FH_USE_REGRESSION_MODEL // Same "deliberately // uninstrumented" pattern as // the FH_REGRESSION_COLLECTION // param below -- no node-level // precompute is threaded // through the split machinery, // so this always falls back to // the no-data sentinel on a // helper thread's move. (FHM_NODE_BASE)FHM_MATE_GATED, #endif #ifdef MOVE_ORDERING_EVIDENCE_COLLECTION FALSE, // fThisMoveIsCountermoveMatch 0, // uCMEvidenceBucket #endif #ifdef TEST_NULL FALSE, // fNullCalibEligible 0, // uNullCalibBucket &uNullCalibFirstMoveNodeCostUnused, #endif &uLegalMoves, &iScore #ifdef PERF_COUNTERS , &fMoveIsPruneReduceEligibleUnused , &uThisMoveHangBucketUnused , &uThisMoveGapBucketUnused , &uThisMoveNumBucketUnused , &uThisMoveDepthBucketUnused #endif #ifdef FH_REGRESSION_COLLECTION , &iFhCollectMoveValueUnused #endif ); ASSERT(PositionsAreEquivalent(&ctx->sPosition, &board)); if (MOVE_KERNEL_ILLEGAL == eMoveKernelResult) { continue; } // PRUNED never made the move at all -- no real score to // report. SEARCHED and ABORTED both genuinely made, searched, // and unmade mv (ABORTED's score is a real partial result, per // the kernel's own return-value comment), so both get a // chance to update the split's best score. if ((MOVE_KERNEL_PRUNED != eMoveKernelResult) && (iScore > iBestScore)) { _UpdateSplitInfo(ctx, mv, iScore, u); } // ABORTED means WE_SHOULD_STOP_SEARCHING fired -- a global // stop condition, stronger than (and never explicitly checked // by) this function's own fTerminate flag before unification. // Stop pulling more moves either way. if ((MOVE_KERNEL_ABORTED == eMoveKernelResult) || (TRUE == g_SplitInfo[u].fTerminate)) { break; } } while(1); _SetFinalStats(ctx, u); } #endif