Author: Mike Siler
Date: 17:04:20 03/31/04
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
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.