Author: Robert Hyatt
Date: 12:56:38 09/06/03
Go up one level in this thread
On September 06, 2003 at 05:28:39, Gian-Carlo Pascutto wrote: >On September 05, 2003 at 17:26:58, Robert Hyatt wrote: > >>Now, what about that 1/6? It turns out that it is possible to predict with >>some reliability when this is happening, by looking at the node count for >>each root move. And when it appears to be a possibility, those moves that >>appear to have larger-than-usual node counts can be searched one at a time >>with a parallel search, > >I'm not so sure - 1/6 is not particularly impressive, even half of that >isn't. You can do significantly better down in the tree. Your average >correct splits/incorrect splits should be way higher than 1/12. Think about the number a minute. In the _entire_ game, 5/6 of the time the best move at the root is unchanged from start to finish. You can spend 5/6 of your time searching _perfect_ alpha/beta trees with respect to parallel search space vs serial search space. In the other 1/6 of the searches done (say 10 cases in a 60 move game) there are other ways to detect that things are not quite right at the root. Again, I didn't guess on this. I _tested_ it, which is why I wrote the code in the first place. > >Doing better with the tricks is not relevant I'd suspect, since you're not >parallelizing at that point. I _always_ parallelize. The question is "do I split at the root or not?" and I currently do it _both_ ways. At the root when looks reasonable, deeper in the tree when it doesn't... > >Then there's the issue of less splitting overhead - not so sure how relevant >that is. I indeed do way more splits as you but performance doesn't seem >to suffer from that, on the contrary. > >Then there's Tony's remark. Good point, but knowing when your root changes >_is_ an intersting thing that's good to know fast, not only in testsets. Som >maybe that's not a problem either. This is predictable, as I mentioned. Each iteration a non-first move will produce a larger tree increase relative to other moves, suggesting that eventually it will become a new best. > >This is the kind of thing where you really want to test in games to know >for sur eor not. I use it. Care to guess why? I have tested this particular point a _lot_. I didn't do it in the original DTS version. Harry convinced me it was wrong and later versions of DTS did it just like I do it in Crafty. > >You'd have to play a very long match between them to be sure, and then really >hope a statistically significant result turns up. You _don't_ want to worry about the results. This is not a major change. You do care about overall time. Just play a game with smproot=0 then the same game with smproot=1, and see how it affects overall time... That's how I tested it. > >Messy bussiness. It's messy, but it works. The theory certainly supports the idea. If you look up my original parallel search paper published in Parallel Computing, the math certainly supports this approach even though that paper is not about algorithms, but about math. > >-- >GCP
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.