Need help on YBWC algorithm

[bob]

Thanks Bob, getting your points. To make clear for me, I would like to ask few questions:

Suppose a split block A is ran by master thread 1, then thread 1 runs out of work and goes to help and currently works in other block, say B. Now, a slave (thread 2) of block A completes the search (found a cut off):

- Will we stop the thread 1 (running block B)? Will we wait thread 1 to complete block B, then be back to work with A?

- Or can we use any available thread to work on A as the master? If yes, can we use that slave (thread 2 - who found cut-off) to return the result to parent (play as the master)?

To do what you suggest at the end requires a true DTS algorithm. If you are using NegaMax, there is no way for anyone else but the original master to "return" back up the tree before the split point. I chose to keep the recursive negamax search because it is so clean, but it does introduce the issue you mention. In my case, the original master will follow the slaves and do a parallel search with them. If it finishes first, it returns back to ThreadWait() and spins until someone gives it work, or until all the "slaves" at the current split point return which will cause it to return from ThreadWait() back into the search at the point where it started the parallel search...

[phhnguyen]

Amazing, I have read somewhere that DTS algorithm is harder than YBWC one to implement. But I see that the thread management of DTS as you mentioned seems be easier to implement and more effect to work

I sticked to (1) as the YBWC idea and be stuck for a while and now see no problem to do (2). The other ideas of YBWC (such as doing parallel only after computing PV move) will be followed strictly. Not sure at the end I will have YBWC or DTS

[bob]

Amazing, I have read somewhere that DTS algorithm is harder than YBWC one to implement. But I see that the thread management of DTS as you mentioned seems be easier to implement and more effect to work

I sticked to (1) as the YBWC idea and be stuck for a while and now see no problem to do (2). The other ideas of YBWC (such as doing parallel only after computing PV move) will be followed strictly. Not sure at the end I will have YBWC or DTS

DTS is a nice model, if you are willing to give up on the recursive negamax formulation. Then when a processor becomes idle, you can look at all the nodes along the current path (rather than just the current ply and for any active processor, rather than just the current processor). That gives you a better chance to (a) find a node that represents significant work (near the root) and which has a better chance of being an ALL node (the more moves you search at any node, the greater the probability it is an ALL node).

But the code is ugly. Ugly. UGLY. Since we found the oldish Cray Blitz source, there is at least a working DTS code to look at. It was nowhere near the final version, but it was DTS and shows the ideas in detail, even if they were later tweaked some.

[phhnguyen]

Hi Bob,
I need you to help to make clear an implementation detail. When studying Crafty, I see the code of search as the following:

for (all moves)
{
...
Thread(tree);
}

Update search result;
return alpha;

As I understand, you still need the main (master) thread to come back from Thread(tree) to update the search result and return alpha, is it correct?

So there is a scenario:

- Thread 1 works in a node A as the master when thread 2 works as a slave one
- Thread 1 runs out of work and go to help node B as a slave
- In the same time, thread 2 finds a cut-off, it stops all other slaves of node A, but can't stop thread 1 because it is still working in node B
- Only after completing work in node B, thread 1 comes back to update node A and return alpha to its parent.

Am I missing somethings? Thanks for your helps.

[bob]

Hi Bob,
I need you to help to make clear an implementation detail. When studying Crafty, I see the code of search as the following:

for (all moves)
{
...
Thread(tree);
}

Update search result;
return alpha;

As I understand, you still need the main (master) thread to come back from Thread(tree) to update the search result and return alpha, is it correct?

Yes...

So there is a scenario:

- Thread 1 works in a node A as the master when thread 2 works as a slave one
- Thread 1 runs out of work and go to help node B as a slave
- In the same time, thread 2 finds a cut-off, it stops all other slaves of node A, but can't stop thread 1 because it is still working in node B

If you look at the Crafty source, each "split block" has a "stop flag" associated with it. If this gets set, the thread using this split block quits searching and returns, and it always returns to "ThreadWait()". It doesn't "terminate" ever. In your example, A asks B to help at the first split point. Then A runs out of work to do and B asks A to help somewhere in the tree _below_ that split point. If B quickly finds a cutoff, it will tell A to stop, which will cause it to return to ThreadWait() and when B finally backs up that same split point and says "done", then A will return from ThreadWait() back into the place where it was in Search when it started the parallel split, and do whatever needs to be done there...

- Only after completing work in node B, thread 1 comes back to update node A and return alpha to its parent.

Am I missing somethings? Thanks for your helps.