Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 11:32:35 06/16/00

Go up one level in this thread


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.



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.