Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: New crap statement ? Perpetuum mobile

Author: Bruce Moreland

Date: 15:33:04 10/04/01

Go up one level in this thread


On October 04, 2001 at 18:17:41, Dave Gomboc wrote:

>If the sample data is representative of the population data (rather than being
>outlier data) then the serial algorithm is not fine, it is terrible.

If I gave you that task, how would you write it?  You'd write the serial version
at least, just the way I said.

The data may have been manufactured several years later, and now it doesn't work
very well with that tool, and suddenly it works great with the other tool.  It's
hard to say that the tool is dead bad now.

You could have written the serial one so that it searches in random order, and
that would result in smooth performance even in cases where there were patterns
that would either speed you up or slow you down.

But if you can predict that you'll often get certain patterns, it makes sense to
detect them and be faster.

This may not have been clear to the person who wrote these algorithms the way I
originally suggested.

The same way that not everything is clear to us who mess around with chess
trees.

>But if the parallel algorithm is consistenly better than the sequential one,
>then you can implement a sequential algorithm to simulate the parallel one,
>which will also search the tree in the new, better order.

Of course.  I've never said that the parallel one has to be better than the
serial one.

>>This is why I think that someone who claims to have found a super-linear speedup
>>when doing a parallel search should not be labeled a computer science apostate.
>>A chess tree probably has enough entropy in it that the claim is due to a bug,
>>random chance, or bad performance measurement technique, but it is always
>>possible that some common orderliness inside the tree has been found and
>>exploited.
>
>I already suggested to Vincent that he look for phenomena similar to what is
>described in "Rapid Random Restart".  I have privately speculated about this
>happening in game trees for some time already.

Yes, if we're both talking about the same thing, I don't see why we're
disagreeing.

If we insist that what you are talking about can't exist because alpha-beta is
provably perfect, then we can't acknowledge that this might be possible.

bruce



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.