# Computer Chess Club Archives

## Messages

### 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 once made an experiment and found it to be roughly in line with
>>>>this formula.
>>>>
>>>>Ralf
>>>
>>>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).
>>>
>>>Dave
>>
>>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 :)
>>
>>Ralf
>
>
>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.

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.

Dave

```