Computer Chess Club Archives


Search

Terms

Messages

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

Author: Ralf Elvsén

Date: 17:00:31 06/17/00

Go up one level in this thread


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




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.