Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: New crap statement ? Perpetuum mobile

Author: Dave Gomboc

Date: 15:52:19 10/04/01

Go up one level in this thread


On October 04, 2001 at 18:33:04, Bruce Moreland wrote:

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

Here, we disagree.  It's pretty clear that the tool is bad now.  It became bad
when the data distribution changed.

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

I could have, but even searching in random order would be super-linearly slower
than always examining the last element, so that's a bad algorithm too.

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

Sure.

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

Okay.

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

Fine.

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

Okay.

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

Maybe we aren't? :-)

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

Alpha-beta is provably perfect for some things, but I certainly grant that
searching a tree with heuristic estimates at the tips is not one of them.  In
fact, I'm suggesting that if the parallel algorithm consistently gives
super-linear speedup, then there's a better way even on one processor.

>bruce

Dave



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.