diff options
Diffstat (limited to 'src/split.c')
| -rwxr-xr-x | src/split.c | 1154 |
1 files changed, 1154 insertions, 0 deletions
diff --git a/src/split.c b/src/split.c new file mode 100755 index 0000000..714d77b --- /dev/null +++ b/src/split.c @@ -0,0 +1,1154 @@ +/** + +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 ([email protected]) 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; +#define MAX_SPLITS (20) +#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; + ULONG uIdleLoops = 0; +#ifdef PERF_COUNTERS + 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. + // + uIdleLoops = 0; + ReInitializeSearcherContext(&(g_SplitInfo[u].sRootPosition), ctx); + ctx->pSplitInfo[0] = &(g_SplitInfo[u]); + ctx->uPositional = g_SplitInfo[u].uSplitPositional; + + // + // 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 *)mv.uMove, + &g_SplitInfo[u], + (void *)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 OUT SCORE *piBestScore, + IN OUT MOVE *pmvBest, + IN ULONG uMoveNum, + IN INT iPositionExtend, + IN ULONG uDepth) +{ +/** + +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 + +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); + 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)); +#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].uSplitPositional = ctx->uPositional; + 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].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 forget about the SEARCH_SORT_LIMIT + // stuff here and sort the whole list of moves from + // best..worst. + // + 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)); + if (g_SplitInfo[u].iBestScore < g_SplitInfo[u].iBeta) + { + 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; +#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 + // + 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; + + // + // 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; + SCORE iRoughEval; + ULONG uOrigDepth; + ULONG uDepth; + ULONG uMoveNum = 0; + INT iOrigExtend; + INT iExtend; + MOVE mv; +#ifdef DEBUG + POSITION board; + + memcpy(&board, &ctx->sPosition, sizeof(POSITION)); + ASSERT(PositionsAreEquivalent(&board, &g_SplitInfo[u].sSplitPosition)); +#endif + + iOrigExtend = g_SplitInfo[u].iPositionExtend; + iBeta = g_SplitInfo[u].iBeta; + uOrigDepth = g_SplitInfo[u].uDepth; + ctx->sSearchFlags = g_SplitInfo[u].sSearchFlags; + do + { + iExtend = iOrigExtend; + 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); + ASSERT(iExtend >= -ONE_PLY); + ASSERT(iExtend <= +ONE_PLY); + + if (MakeMove(ctx, mv)) + { + ASSERT((IS_CHECKING_MOVE(mv) && + InCheck(&ctx->sPosition, ctx->sPosition.uToMove)) || + (!IS_CHECKING_MOVE(mv) && + !InCheck(&ctx->sPosition, ctx->sPosition.uToMove))); + iRoughEval = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE); + + // Compute extension + ComputeMoveExtension(ctx, + iAlpha, + iBeta, + (ctx->sMoveStack.uBegin[ctx->uPly - 1] + + uMoveNum), + iRoughEval, + uDepth, + &iExtend); + + // + // Decide whether to history prune + // + if (TRUE == WeShouldDoHistoryPruning(iRoughEval, + iAlpha, + iBeta, + ctx, + uDepth, + (g_SplitInfo[u].uAlreadyDone + + uMoveNum + 1), + mv, + (g_SplitInfo[u].uAlreadyDone + + uMoveNum + 1), + iExtend)) + { + ASSERT(iExtend == 0); + iExtend = -ONE_PLY; + ctx->sPlyInfo[ctx->uPly].iExtensionAmount = -ONE_PLY; + } + + // + // Compute next depth + // + uDepth = uDepth - ONE_PLY + iExtend; + if (uDepth >= MAX_DEPTH_PER_SEARCH) uDepth = 0; + + iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uDepth); + if ((iAlpha < iScore) && (iScore < iBeta)) + { + iScore = -Search(ctx, -iBeta, -iAlpha, uDepth); + } + + // + // Decide whether to research reduced branches to full depth. + // + if ((iExtend < 0) && (iScore >= iBeta)) + { + uDepth += ONE_PLY; + ctx->sPlyInfo[ctx->uPly].iExtensionAmount = 0; + iScore = -Search(ctx, -iBeta, -iAlpha, uDepth); + } + UnmakeMove(ctx, mv); + ASSERT(PositionsAreEquivalent(&ctx->sPosition, &board)); + if (TRUE == g_SplitInfo[u].fTerminate) break; + if (iScore > iBestScore) + { + _UpdateSplitInfo(ctx, mv, iScore, u); + } + } + } + while(1); + _SetFinalStats(ctx, u); +} +#endif |