Computer Chess Club Archives


Search

Terms

Messages

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

Author: Thomas Mayer

Date: 03:15:41 06/18/03

Go up one level in this thread


Hi Uri,

>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.

my godness, Uri - we are talking about pure alpha beta the hole threat... pure
alphabeta definitely excludes any type of pruning...

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

it's simple - that was the question of the initiator of this thread. :)

> 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."

wrong, correctly it must be written the following:

> "alpha-beta has a branching factor of the square
> root of the min-max branching factor."

that's it. Move ordering has no influence at all on the theoretical branching
factor...For perfect ordering alpha beta would need N(D)=SQRT(Nm(D)) where N(D)
is nodes in alpha beta of a certain D=Depth and Nm(D) is Nodes with minimax for
a certain D=Depth... when move ordering is not perfect the practice has shown
that N(D)=5*SQRT(Nm(D)) is a good approch near to reality to calculate the nodes
- the branching factor would not be affected... On first sight this looks
strange - when you think a little bit deeper about that it is logical - better
move ordering will bring you a constant speed up which does simply not affect
the branching factor...

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.