Author: Vincent Diepeveen
Date: 17:24:57 09/21/01
Go up one level in this thread
On September 19, 2001 at 15:31:09, Robert Hyatt wrote:
>On September 19, 2001 at 15:21:50, Robert Hyatt wrote:
>
>>On September 19, 2001 at 10:21:44, Uri Blass wrote:
>>
>>>Not exactly.
>>>
>>>It is possible to get a speed improvement even in part of the 92% of the cases.
>>>The fact that you only need the first move to get a cutoff does not prove that
>>>the order of moves is optimal because it is possible that another move helps you
>>>to get the cutoff faster.
>>>
>>>Uri
>>
>>
>>That is certainly possible. And it could be measured if someone wants to
>>test it. But irregardless, you _never_ want to search two moves at the same
>>time if either will cause a cutoff, because _one_ is doing unnecessary work
>>that is not contributing a thing to the speedup of the sequential algorithm.
>
>
>I should have added more info. here goes.
>
>Suppose move 1 at one of these "fail high" nodes requires 100K nodes to search
>it. Suppose move 2 would only require 50K nodes.
Wrong assumption. In DIEP i use Nullmove. Don't know about crafty much,
but the cutoff difference is huge. Some trees need 1k nodes to cutoff,
other trees from same depth need a million nodes to cutoff.
That's a factor 1000.
The big problem in computerchess is of course that when you search
sequential, that any cutoff is stored into hashtable. Usually your 92%
cutoff rate is not the most optimal cutoff.
Big example: sometimes capturing a piece gives huge tactics but in the
end a small cutoff. Of course programs play the capture first in
move ordering.
But sometimes playing away that piece gives a direct nullmove cutoff
in all the remaining lines.
You save R+1 plies with that tree then.
The deeper you search the bigger the chance that R=3 here:
taking average branching factor from 3 :
3 * 3 * 3 * 3 = 9 * 9 = 81
So a factor 81 is what you save.
We know ONE thing and that's that our sequential search is
NOT even *near* optimal.
The major problem to get a decent speedup in crafty is
your 5% fliprate, which i do not have. In fact it's < 1% in DIEP.
That's a *huge* difference Bob.
That's where you lose the thing in combination with being recursive!
>If you search in parallel there, the first gets thru 50K nodes before
>being told to stop, because the second would have been searched after doing
>50K nodes and failing high. total nodes searched = 100K. 50K unnecessary.
>
>If you search serially here and search the first node. you will use the
>second cpu somewhere deeper in that search, so that the 100K nodes are
>searched in 1/2 the time in parallel. You still fail high. Total nodes
>searched = 100K. _exactly_ the same effort. And in cases where the first
>move fails high and the second does _not_ the cost goes way up. As I do it
>now, the cost doesn't change a bit. The moral, which is well-known to parallel
>alpha/beta searchers, is "never split in parallel at a node that is expected to
>fail high." That is why "Young Brothers Wait" works so well. you have to
>search the first move serially before searching the rest in parallel, to give
>the first move a chance to fail high. If the first doesn't fail high, you know
>this node has a 92% probability of being a fail-low node that needs all branches
>searched.
>
>pretty good odds...
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.