Author: Robert Hyatt
Date: 22:41:52 09/05/02
Go up one level in this thread
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..
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.