TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Robert Hyatt

Joined: 27 Feb 2006
Posts: 20338
Location: Birmingham, AL

Post subject: Re: DTS Structure    Posted: Sat May 29, 2010 4:36 pm

Onno Garms wrote:
 bob wrote: The problem is that recursive search means you can split "here" or not at all, because of the call stack.

ACK, but that is a problem for both DTS and YBWC.

No, that is what we are talking about when we mention an iterated search vs a recursive search. In an iterated search, rather than making a recursive call to Search(), you increment "ply" and go back to the top. Rather than doing a return (from a recursive search call) you just decrement ply. So there is no call stack of any kind, and all the data for each ply is available for use or modification, where in a recursive search this is not true.

Quote:

 Quote: With DTS there is no call stack, so you can split at a node that is 10 plies back in the tree just as easily as you can split "here".

You mean "iterative search" rather than "DTS"?

DTS _depends_ on an iterated search... That was the primary underlying principle of the idea...

Quote:

 Quote: That's the main difference.

Isnt' the main difference that in DTS the child that finishes last at a split point takes over the parent? This means, we move nodes to another thread. For this reason, an iterative search is essential for DTS (because we cannot move callstacks of recursive search). For YBW an iterative search is just a benefit on top (allowing to split anywhere in the tree).

To do that, you can't use a recursive search. How can anyone but the "parent" back up thru a split point, since only the parent has the call stack to do this? That why everyone mentions "iterated search" when talking about DTS... One could do it with a recursive search, but it would be incredibly messy since it would be necessary to "unwind" a call stack here and there, and "artificially load one" at other points. Who'd want to debug that?

Quote:

 Quote: As are the data structures and such. But the ability to see all nodes for all threads when a CPU goes idle, rather than having non-idle CPUs ask idle ones to "join in" is a significant efficiency enhancement...

ACK
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Edmund Moshammer Fri May 28, 2010 8:29 am
liuzy Fri May 28, 2010 11:30 am
Edmund Moshammer Fri May 28, 2010 7:21 pm
Zach Wegner Fri May 28, 2010 2:44 pm
Edmund Moshammer Fri May 28, 2010 7:27 pm
Onno Garms Fri May 28, 2010 10:27 pm
Onno Garms Fri May 28, 2010 10:49 pm
Edmund Moshammer Fri May 28, 2010 11:05 pm
Dann Corbit Sat May 29, 2010 12:17 am
Zach Wegner Sat May 29, 2010 1:49 am
Onno Garms Sat May 29, 2010 7:48 am
Lance Perkins Sat May 29, 2010 4:26 am
Robert Hyatt Sat May 29, 2010 5:11 am
Onno Garms Sat May 29, 2010 7:33 am
Re: DTS Structure Robert Hyatt Sat May 29, 2010 4:36 pm
Onno Garms Sun May 30, 2010 8:35 am
Robert Hyatt Sun May 30, 2010 4:57 pm
Joona Kiiski Sun May 30, 2010 7:08 pm
Robert Hyatt Sun May 30, 2010 8:28 pm
Edmund Moshammer Sun May 30, 2010 9:39 pm
Robert Hyatt Mon May 31, 2010 12:25 am
Edmund Moshammer Mon May 31, 2010 8:17 am
Robert Hyatt Mon May 31, 2010 2:47 pm
Edmund Moshammer Mon May 31, 2010 2:56 pm
Robert Hyatt Mon May 31, 2010 9:24 pm
Onno Garms Mon May 31, 2010 5:00 pm
Robert Hyatt Mon May 31, 2010 9:25 pm
Marco Costalba Mon May 31, 2010 5:10 pm
Nils Magnusson Mon May 31, 2010 6:07 pm
Gregory Strong Mon May 31, 2010 7:41 pm
Robert Hyatt Mon May 31, 2010 9:28 pm
Marco Costalba Tue Jun 01, 2010 4:57 am
Robert Hyatt Tue Jun 01, 2010 2:01 pm
Robert Hyatt Tue Jun 01, 2010 2:40 pm
Sam Hamilton Tue Jun 01, 2010 2:52 pm
Robert Hyatt Tue Jun 01, 2010 3:02 pm
Onno Garms Mon May 31, 2010 4:47 pm
Robert Hyatt Mon May 31, 2010 9:30 pm
Edmund Moshammer Sat May 29, 2010 7:43 am
Onno Garms Sat May 29, 2010 8:09 am
Edmund Moshammer Sat May 29, 2010 8:20 am
Robert Hyatt Sat May 29, 2010 4:40 pm
Robert Hyatt Sat May 29, 2010 4:39 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumChess Players ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum