Computer Chess Club Archives


Search

Terms

Messages

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

Author: Dan Andersson

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
about 2.5 per two plies.
 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.

MvH Dan Andersson



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.