Computer Chess Club Archives


Search

Terms

Messages

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

Author: Uri Blass

Date: 01:35:47 06/18/03

Go up one level in this thread


On June 17, 2003 at 20:08:17, Thomas Mayer wrote:

>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

You need to assume also not using hash tables for pruning.
There is an assumption that alpha beta includes no pruning by null move or by
hash tables.

I do not see a reason to make this assumption when most of the programs use
pruning and(or) hash tables.

The right sentence is:
"With perfect move ordering, alpha-beta (with no pruning including not using the
hash tables for pruning) has a branching factor of the square
root of the min-max branching factor."


Uri



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.