Computer Chess Club Archives




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

Author: Dave Gomboc

Date: 10:47:53 06/19/00

Go up one level in this thread

On June 17, 2000 at 20:53:20, Robert Hyatt wrote:

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

I went and asked Jonathan about where he got the estimate from.  His reply was
that Monty Newborn published the result a long time ago (most likely in the
1970s, and he is "pretty sure" it was co-authored).  Also he mentioned that
somebody told him later that there was a problem with the proof, but that he
didn't know if the error substantially changed the result.

I don't intend to bother him about it further, I'm sure he has more important
things to do.  Hopefully the Newborn tip helps Ralf out.


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