Author: Ricardo Gibert
Date: 20:38:34 03/31/04
Go up one level in this thread
On March 31, 2004 at 23:33:00, Mike Siler wrote: >On March 31, 2004 at 20:17:16, Dan Honeycutt wrote: > >>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. > >I thought it was +1, which is also what Dr. Hyatt said in a post within the past >couple of days. Just plug in d=0 and d=1 to see for yourself whether it ought to be +1 or -1. > >Michael
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.