Computer Chess Club Archives




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

Author: Ricardo Gibert

Date: 18:16:50 06/19/03

Go up one level in this thread

On June 18, 2003 at 08:45:52, Uri Blass wrote:

>On June 18, 2003 at 06:15:41, Thomas Mayer wrote:
>>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...
>In this case it is only a question of definition.
>I think that everybody says that program use alpha beta so I thought that
>talking about alpha beta does not mean automatically no 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
>practise of who?
>I never used pure alpha beta(no extensions and no qsearch and no pruning).
>>- 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...
>No It is not logical.
>Better order of moves gives exponential speed up.

No way! This would imply you can go on improving move ordering forever. Once you
have perfect, you have hit a brick wall that cannot be breached.


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.