Author: Mike Siler
Date: 20:33:00 03/31/04
Go up one level in this thread
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. 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.