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