Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: PVS and MTD(f) branching factor

Author: Thomas Mayer

Date: 17:08:17 06/17/03

Go up one level in this thread


Hi Uri,

>> With perfect move ordering, alpha-beta has a branching factor of the square
>> root of the min-max branching factor.

>No
>It is wrong.
>I think that you forgot a lot of pruning and null move pruning together with
>other ideas reduce the branching factor.

No, it is correct: A perfect alpha beta with perfect move ordering would need
SQRT(Nodes) compared to Mini-Max. In practice something like 5*SQRT(Nodes) is
true... branching Factor of pure mini-max is 40 if we say that a good guess for
approximately moves is 40... so the branching factor for perfect alpha beta
would be around 6... this is also true when the move ordering is not as perfect,
but the number of nodes per each iteration is higher...

Nowadays modern chess programs have a branching factor of around 3 or better...
that is done by pruning, nullmove etc.... but as long alpha-beta does not
include any risk to oversee something with implementing forward pruning and
nullmove things can be overseen... thats the handicap...

Greets, Thomas



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