DTS Structure

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: DTS Structure

Post by bob » Tue Jun 01, 2010 2:40 pm

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.

BubbaTough
Posts: 1154
Joined: Fri Jun 23, 2006 3:18 am

Re: DTS Structure

Post by BubbaTough » Tue Jun 01, 2010 2:52 pm

[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

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: DTS Structure

Post by bob » Tue Jun 01, 2010 3:02 pm

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.
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[/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.

Post Reply