Author: Ralf Elvsén

Date: 01:09:59 06/17/00

Go up one level in this thread

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

- Re: Is the NPS for minimax devided by NPS in alpha-beta = 5 ?
**Dave Gomboc***16:08:35 06/17/00*- Re: Is the NPS for minimax devided by NPS in alpha-beta = 5 ?
**Ralf Elvsén***17:00:31 06/17/00*- Re: Is the NPS for minimax devided by NPS in alpha-beta = 5 ?
**Robert Hyatt***17:53:20 06/17/00*- Re: Is the NPS for minimax devided by NPS in alpha-beta = 5 ?
**Dave Gomboc***10:47:53 06/19/00*

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

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

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

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