Parallel Panic

[BertTuyt]

Ed, herewith the mentioned bug.
I didn't find the older Glaurung source files, but the same bug I saw in the oldest Stockfish source (available on the net).
The code is from the routine :

Code: Select all

void sp_search_pv(SplitPoint *sp, int threadID) {

Here the part where (to my opinion) things "can go wrong".

Code: Select all

          value = -search(pos, ss, -sp->alpha, newDepth, sp->ply+1, true, threadID);

          if (value > sp->alpha && value < sp->beta)
          {
              // When the search fails high at ply 1 while searching the first
              // move at the root, set the flag failHighPly1.  This is used for
              // time managment:  We don't want to stop the search early in
              // such cases, because resolving the fail high at ply 1 could
              // result in a big drop in score at the root.
              if (sp->ply == 1 && RootMoveNumber == 1)
                  Threads[threadID].failHighPly1 = true;

              value = -search_pv(pos, ss, -sp->beta, -sp->alpha, newDepth, sp->ply+1, threadID);
              Threads[threadID].failHighPly1 = false;
        }

Here the chain-reaction principles which can cause the problem:
- Assume the initial alpha is 10 (just a number)
- The minimal window search will start with this value.
- A fail high occurs , value for example 11.
- This does not mean the new score is 11, it indicates that the actual score >= 11 (could even be 100, or whatever).
- But ,....................................... if in the meantime a parallel thread also has found a better score , example 12, then the Splitpoint Alpha value will be changed by the other thread to 12.
- Which does not trigger the condition to do a new search for this thread!!!
- So in the above code the sp->alpha value for the search and then for the if statement could be different !!
- So you should use a local copy of the sp->alpha (see new/most recent code Stockfish).

At least when i examined the logs of all the cores/threads, this was what happened in my case.
After changing and doing the same search 100 times, in all cases the move and score was equal.

I'm not sure if I solved all bugs now, but at least a tricky one.

Bert

[Ed Gilbert]

Ok, thanks for the explanation. I modelled my parallel code somewhat after glaurung's, but the details are much different because I do not use a pvs search, and I don't have anything that is similar to this particular section.

BTW there is a thread active right now on the Talk Chess forum. A Spanish checkers programmer is asking if it is normal for his parallel search to get different node counts when he does fixed depth searches from the same starting position. Bob Hyatt (author of crafty) has just offered his experience on the subject:

Absolutely normal. The nodes can vary. The score can change. And at times you will even get a completely different best move, although this is less common than the first two.

-- Ed

[BertTuyt]

Ed, I'm following this thread also. As the chess community is far more active it is often interesting to follow their discussions.
But as this is the case (pseudo-random behavior of search-results), it is my opinion that debugging, in first instance, should be based on artificial trees, with all options switched off in the search. So in this case you really can test the bone parallel algorithms (not polluted by all other search-refinements/optimizations) .

I will post some thoughts about the most simple type of parallel-search, which is based on the parallel processing of root-nodes.

Maybe not known to all, but there is a structural difference between odd- and even search-depth.
In the post i will explain why parallel root-search (even depth, for a perfect ordered tree) will reach only an asymptotic two-fold increase in speed, even when the number of threads/cores are infinite.
For odd search-depths this is completely different.

Bert

[jj]

Bert,

The search I used for testing is the minmax-search where i search to a given depth and stop the search when the side to move has no capture (if the opposite does have a capture option, i still stop). And if the movecount is 1, i don't 'count" this as an additional ply.
With a "slightly" modified perft i calculated the end -nodes of these search-trees, see table below (maybe some-one can check this, if the count is OK).

Code: Select all

Ply    Number of End-Nodes
7      4,202,204
8      37,413,597
9      351,706,838
10     3,396,182,697

Using the same modified perft, I get the same counts as you.

* Do you have good examples, suggestions for parallel-debugging, or whatever....

I suggest parallel perft (see topic).

Maybe not known to all, but there is a structural difference between odd- and even search-depth.
In the post i will explain why parallel root-search (even depth, for a perfect ordered tree) will reach only an asymptotic two-fold increase in speed, even when the number of threads/cores are infinite.
For odd search-depths this is completely different.

I'm interested to learn about this...

Jan-Jaap