Simple. The search can split anywhere _below_ the lowest active split point. When the master is busy, any idle threads will join in to help it complete whatever it is working on, always at a deeper ply.Onno Garms wrote:Ah, I see. I didn't know that there are implementations without this.bob wrote: This is not a YBW issue, it is an implementation issue.
What happens when all slaves of split S are ready (all children searched) but the master is still busy with something else? Will it continue its task before it returns the result of S to its parent?I use pure YBW in Crafty, And I don't have the issue you mentioned above at all. Yes the original "owner" has to be the one to back up at that node once it has been completed by either itself or "slaves". But that master can go off and work at other points in the tree also, and not sit around holding things up...
DTS Structure
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: DTS Structure
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: DTS Structure
Joona made a comment, you said he was wrong, I replied that we have tested some code that verify what Joona said, you are saying that you don't care because you already know everything.....who's the snotty one here ?bob wrote: B) as for the "amazing case" just keep your snotty attitude to yourself, I know enough about how to do an efficient parallel search without looking at other code...
P.S: I already knew you had answered in that way (I don't know if this is snotty or not), you missed an occasion to surprise me. Please don't reply that you don't care to surprise me....otherwise you'd miss a second one
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: DTS Structure
If you will simply reread what he wrote, and my follow up, I clearly said "this is not quite true" and explained _exactly_ why this is the case. As far as what you tested, I have no idea. I have tested my code, but it does require long games to test parallel search, as it gets better as the depth increases. How you tested this I don't know. It _does_ work. It might be 10%. It might be less. Depending on how effective your implementation is. 10% _does_ make a difference. Not a big one, and one that takes many games to measure. But it does help.mcostalba wrote:Joona made a comment, you said he was wrong, I replied that we have tested some code that verify what Joona said, you are saying that you don't care because you already know everything.....who's the snotty one here ?bob wrote: B) as for the "amazing case" just keep your snotty attitude to yourself, I know enough about how to do an efficient parallel search without looking at other code...
P.S: I already knew you had answered in that way (I don't know if this is snotty or not), you missed an occasion to surprise me. Please don't reply that you don't care to surprise me....otherwise you'd miss a second one
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: DTS Structure
BTW, when you say "know everything" let me ask you a couple of questions:
(1) Do you know who coined the term "Dynamic Tree Splitting"?
(2) Do you know who developed the algorithm?
(3) Do you know who used this algorithm first?
(4) Do you know who coined the acronym "DTS"?
(5) Do you know who designed and implemented this algorithm as their Ph.D. dissertation?
(6) Do you know who then wrote this up and published it in a short-form in the JICCA?
Hint: They all have the _same_ answer.
For the record, I _do_ know what DTS is all about. And YBW. And PVS (not the null-window search used by everyone but "Principle Variation Split" first used in the early 80's.) Etc.
I had my first parallel search working in 1978, for reference. One does learn by experience.
(1) Do you know who coined the term "Dynamic Tree Splitting"?
(2) Do you know who developed the algorithm?
(3) Do you know who used this algorithm first?
(4) Do you know who coined the acronym "DTS"?
(5) Do you know who designed and implemented this algorithm as their Ph.D. dissertation?
(6) Do you know who then wrote this up and published it in a short-form in the JICCA?
Hint: They all have the _same_ answer.
For the record, I _do_ know what DTS is all about. And YBW. And PVS (not the null-window search used by everyone but "Principle Variation Split" first used in the early 80's.) Etc.
I had my first parallel search working in 1978, for reference. One does learn by experience.
-
- Posts: 1154
- Joined: Fri Jun 23, 2006 5:18 am
Re: DTS Structure
[quote="bob" I have tested my code, but it does require long games to test parallel search, as it gets better as the depth increases. How you tested this I don't know. It _does_ work. It might be 10%. It might be less. Depending on how effective your implementation is. 10% _does_ make a difference. Not a big one, and one that takes many games to measure. But it does help.[/quote]
I have not been following the details closely, but I suspect this is the primary issue. Concluding something like this does not help in long games is so very hard without dedicating a lot of time and resources.
-Sam
I have not been following the details closely, but I suspect this is the primary issue. Concluding something like this does not help in long games is so very hard without dedicating a lot of time and resources.
-Sam
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: DTS Structure
I have not been following the details closely, but I suspect this is the primary issue. Concluding something like this does not help in long games is so very hard without dedicating a lot of time and resources.BubbaTough wrote:[quote="bob" I have tested my code, but it does require long games to test parallel search, as it gets better as the depth increases. How you tested this I don't know. It _does_ work. It might be 10%. It might be less. Depending on how effective your implementation is. 10% _does_ make a difference. Not a big one, and one that takes many games to measure. But it does help.
-Sam[/quote]
This has been documented previously, by more than one person doing this kind of research. The deeper you go, the better your parallel search can do, since that gives you more potential split points to choose from. More choices -> better decisions, done correctly.
As long as the discussion includes 1,000 game tests, this is not going anywhere positive. It takes more games than that to find a parallel search improvement, unless you compare non-parallel to parallel where the speedup can be a factor of 3+ for 4 cpus which will show up in fewer games. Tweaking parallel search often produces nothing in most cases, but helps in the endgame, or vice-versa. It is not always easy to measure.