Author: Ricardo Gibert
Date: 17:39:07 06/16/00
Go up one level in this thread
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?
This page took 0 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.