Author: Robert Hyatt
Date: 05:40:27 09/06/02
Go up one level in this thread
On September 06, 2002 at 02:49:15, Dann Corbit wrote:
>On September 06, 2002 at 01:41:52, Robert Hyatt wrote:
>
>>On September 06, 2002 at 00:05:25, Dann Corbit wrote:
>>
>>>On September 05, 2002 at 23:44:54, Robert Hyatt wrote:
>>>[snip]
>>>>That is the point. Super-linear speedup is a direct proof of bad move
>>>>ordering, as that is the only way to get one. I get a few (I am going to
>>>>post a set of positions for Martin in just a few minutes) but those are
>>>>offset (more than offset actually) by less than linear speedups in other
>>>>positions...
>>>
>>>Improved move ordering is one way to get more than linear speedup. But I think
>>>that there may be others.
>>>
>>>Consider chasing the pv with one of the CPU's. As long as you have the move
>>>ordering perfect, and you are not running down a blind canyon, you might
>>>(should) be getting improvement for each forward ply of the pv. Now, as the
>>>second (or nth or whatever) CPU chases along the PV and analyzes, it fills the
>>>hash table with goodies about the future. Some other searches will see this
>>>{far into the future} data and instead of a ce of +0.2 it is a ce of +1.4. This
>>>causes all the poor searches to cut off much more easily. Perhaps it can reduce
>>>the tree to 1/10 of its former size.
>>>
>>>So what I am suggesting is that some *other* searching method than a "brute
>>>expansion of the a/b search tree by labor division" might shrink the tree. And
>>>not just by move ordering but also by improved cutoffs.
>>
>>
>>If that were to work consistently, the sequential algorithm is easy to
>>modify. Create two "pseudo-threads". Search one node on one, then one node
>>on the other, and go back and forth. The _same_ synergistic effect should be
>>found and the same super-linear speedup should occur, _without_ a parallel
>>search at all.
>>
>>That is _always_ the answer to super-linear. IE in the test results I have
>>posted, this algorithm would have helped the serial crafty in 2-3 positions.
>>Of course, it would kill it in others as searching two nodes in parallel is
>>not a good idea for normal alpha/beta..
>
>Then why is it (he asked himself aloud) that pondering does better when you
>guess with extrapolation what is going to be played? Why not just continue to
>ponder at the current root instead? There must be some benefit to the
>extrapolation or there would be no net gain.
If pondering were not so accurate, it wouldn't be as effective, but it would
be a rare day when pondering is not correct at least 50% of the time... and
so it always pays off to do it as it is done...
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.