Author: Gareth McCaughan
Date: 11:37:34 04/01/04
Go up one level in this thread
On March 31, 2004 at 23:33:00, Mike Siler wrote: >>> If I recall correctly, Knuth and Moore showed that the minimum number >>> of leaf nodes the standard alpha-beta algorithm will examine when >>> searching to depth d given a fixed branching factor of w is >>> >>> w^Floor(d/2) + w^Ceiling(d/2) + 1 >> >> is not the formula: >> w^Floor(d/2) + w^Ceiling(d/2) - 1 > > I thought it was +1, which is also what Dr. Hyatt said in a post within > the past couple of days. Knuth & Moore, section 6, corollary 1: | If every position on levels 0, 1, ..., l-1 of a game tree | satisfying the conditions of Theorem 1 has exactly d successors, | for some fixed constant d, then the alpha-beta procedure | examines exactly d^floor(l/2) + d^ceiling(l/2) - 1 | positions on level 1.
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.