Computer Chess Club Archives


Search

Terms

Messages

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

Author: Dave Gomboc

Date: 16:08:35 06/17/00

Go up one level in this thread


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:
>>
>>>On June 16, 2000 at 14:32:35, Robert Hyatt wrote:
>>>
>>>>On June 16, 2000 at 09:43:56, leonid wrote:
>>>>
>>>>>Hi!
>>>>>
>>>>>Is the number between minimax nodes/second, devided on number of nodes/second
>>>>>for alpha-beta, equal to around five?
>>>>>
>>>>>If, for instance, one position in minimax give 1000000 NPS, the same position
>>>>>but solved by alpha-beta logic will indicate around 200000 NPS speed?
>>>>>
>>>>>Leonid.
>>>>
>>>>
>>>>Speed is not an issue.  NPS between alpha/beta and minimax is meaningless.
>>>>Minimax searches way more nodes than alpha/beta, but it also searches faster
>>>>because no moves are tossed out by backward pruning.
>>>>
>>>>The formula you are looking for is this:
>>>>
>>>>for minimax, the total nodes (N) is
>>>>
>>>>N = W^D (W=branching factor, roughly 35-38 for chess, D=depth of search).
>>>>
>>>>For alpha/beta, the total nodes (N) is
>>>>
>>>>N= W^floor(D/2) + W^ceil(D/2)
>>>>
>>>>or when D is even
>>>>
>>>>N=2*W^(D/2)
>>>>
>>>>alpha/beta searches roughly the SQRT(minimax) nodes.  Which is significant.
>>>>In effect, alpha/beta will reach a depth approximately 2x deeper than minimax
>>>>alone will reach.
>>>>
>>>>But NPS really isn't part of the issue, only total nodes searched.
>>>
>>>I would just like to add that the above formula assumes perfect move ordering
>>>for alpha/beta. In other words, the formula above for alph/beta gives the number
>>>of nodes for the minimal search tree. In practice, it should do less well.
>>>
>>>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.

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



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.