Computer Chess Club Archives




Subject: Re: Is the NPS for minimax devided by NPS in alpha-beta = 5 ?

Author: Robert Hyatt

Date: 17:53:20 06/17/00

Go up one level in this thread

On June 17, 2000 at 20:00:31, Ralf Elvsén wrote:

>On June 17, 2000 at 19:08:35, Dave Gomboc wrote:
>>On June 17, 2000 at 04:09:59, Ralf Elvsén wrote:
>>>On June 16, 2000 at 22:38:41, Robert Hyatt wrote:
>>>>On June 16, 2000 at 20:39:07, Ricardo Gibert wrote:
>>>>>Just out of curiousity, what would alpha/betas formula look like with random
>>>>>move ordering?
>>>>Difficult to say and it would have to have too many assumptions.  IE do you
>>>>assume that for any fail-high node, there is only one move that will fail high?
>>>>Or could there be several different moves that would be good enough to cause
>>>>the fail-high?  The formula is derivable, but probably isn't worth the effort.
>>>Dave Gomboc has given the formula W^(2D/3)   (approximately) .
>>>I asked about the assumptions behind this but didn't get an answer.
>>>I once made an experiment and found it to be roughly in line with
>>>this formula.
>>Hmm, maybe I missed your post, whenever that was.
>Some months ago, but that happens easily.
>>I don't actually ever recall seeing a derivation of the result.  This estimate
>>was discussed (in passing) in a Heuristic Search course that I took (professor:
>>Jonathan Schaeffer).
>I have had a hard time getting anywhere. I figured a random number at the
>leafs, i.e. eval = Random(), distributed in some way, would be an
>assumption which would lead to a result, but the math became too ugly.
>The values of alpha and beta closer to the root
>becomes a probability distribution...
>Also I am not sure this is equivalent to the original problem.
>Another approach, which I think Bob was refering to, is to make assumptions
>about the number of fail-high moves at each node, but that seems to be
>such a crude model that I wouldn't feel very happy with a result (which
>I haven't got anyway).
>Maybe there is some subtle trick or it is just very hard. It's even harder
>when you don't know what to assume :)

Another approach, probably the one taken by Jonathan (I did something similar
for my PhD dissertation) would be to simply generate random numbers for the
eval, which has the same effect as random move ordering, and then try a suite
of test positions to that code.  Do the same test with normal scoring.  And
fit a curve of the form N=W^(f*D) to the observed random data.  f might well
end up .66 as Jonathan mentioned.  It might be bigger or smaller as well,
although it obviously has to be > .5, which is the alpha/beta F value with
optimal ordering.

This page took 0.07 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.