Author: Dan Honeycutt
Date: 17:17:16 03/31/04
Go up one level in this thread
On March 31, 2004 at 20:04:20, 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 > >However, in the paper "Multi-Cut Alpha Beta Pruning in Game Tree Search" which >can be found at http://digilander.libero.it/gargamellachess/papers.htm under >Pruning, there is a diagram of a minimal game tree with fixed branching factor >of 3 and fixed depth of 3 plies. In the diagram, a total of 11 leaf nodes are >examined. When I plugged in some values for the leaf nodes and traced through >the algorithm, I got the same number. But if you use the formula above, you get: > >3^Floor(3/2) + 3^Ceiling(3/2) + 1 = 3^1 + 3^2 + 1 = 13 > >Why the discrepancy? Also, does anyone know how this formula was found/proven or >where I can find this? > >Michael is not the formula: w^Floor(d/2) + w^Ceiling(d/2) - 1 Dan H.
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.