# Computer Chess Club Archives

## Messages

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

Date: 17:49:28 06/18/03

Go up one level in this thread

``` Doing some leafing through Knuth and some slight reasoning I came to derive the
following formula. It is approximate. A more exact depends on depth being odd or
even. A more exact one would also double the nodes approximately.
b^l*n^l
b is the branching factor of the tree
l is depth/2 and n is P+(1-P)(b-1).
P is the probability of choosing a cutoff in the first move.
The 'constant' n is the number of nodes searched in the mean when move ordering
fails to find the cutoff. Calcualting n is a bother but some tries are possible
I chose the worst case here. That when cutoff fails I wont find it until the
last move. Not because it is the only possibility. But to err on the side of
caution. This gives an overhead of about 4.5 per two plies when P is 0.9 in
chess. Not a reasonable number. Maybe n=P+(1-P)(b/2) is more reasonable giving
the cutoff a flat distribution in the remaining moves. That gives an overhead of
The main point is that when P goes to 1 n also closes in on 1. And the size
goes
Hope I haven't made a mess when figuring this.