Author: h.g.muller
Date: 12:11:37 02/19/06
Go up one level in this thread
On February 19, 2006 at 09:34:34, Robert Hyatt wrote: >Yes. general formula is this: > >nodes = branching_factor ^ ceil(D/2) + branching_factor ^ floor(D/2) > >For even depths, that is simply > >nodes = 2 * branching_factor ^ (D/2) > >while for odd depths it becomes > >nodes = branching_factor ^ (D/2) + branching_factor ^ (D/2 + 1) It seems you shifted D by 1/2 in the odd case: floor(D/2) equals (D/2 - 1/2) for odd D. So the expression there is nodes = branching_factor ^ (D/2-1/2) + branching_factor ^ (D/2 + 1/2). For big branching_factor B the prefactor of B^(D/2) is thus either 2 or sqrt(B). That makes a geometric average of sqrt(2*sqrt(B)), or 3.55 for B=40. But these formulae are for counting only end leaves, if we also count internal nodes the (leading) pre-factors are 3 and sqrt(B), for a geometric average of sqrt(3*sqrt(B)) = 4.35 (again for B=40). So the number 5 seems a reasonable prefactor if 'positions' refers to all nodes in the tree, and the move ordering is perfect. For imperfect move ordering the exponent goes up, rather than the pre-factor.
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.