Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: The need to unmake move

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.