Initial checkin for typhoon chess engine.

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