Computer Chess Club Archives




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

Author: Dieter Buerssner

Date: 12:16:11 06/18/03

Go up one level in this thread

On June 18, 2003 at 14:17:31, Dan Andersson wrote:

> The gain is asymptotic to the minimal tree. So it won't be exponential. Simple
>as that ;) I won't write the formula. You work it out for yourself.

I am not so sure. First of all, already with random move ordering, one will get
a much smaller tree than the minimax tree for all practical positions. There
will be many positions, where any move is good enough for a beta cutoff. I
remember a small test, where I got over 50% of beta cutoffs in the first move,
in the cases where beta cutoff was possible (no HT was used) for random move
ordering. I would expect (ignoring the odd/even problem) a constant branching
factor for a search without extensions/pruning. So, perhaps with random move
ordering one would get something like nodes ~ bfr^depth and with perfect move
ordering nodes ~ bfp^depth bfp < bfr < N (number of moves/position). How would
you call this speedup mathematically?


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.