Author: Rémi Coulom
Date: 08:28:03 10/07/03
Go up one level in this thread
On October 07, 2003 at 09:40:37, Renze Steenhuisen wrote: > >Where can I find the algorithmic complexity analyses of alpha-beta and others? > >Renze If you want the classical reference, it is Knuth and Moore's paper, "An Analysis of Alpha-Beta Pruning", Artificial Intelligence 6, 1975 If you simply need the result, here it is: For a min-max search with braching factor b at depth d, the cost is b^d alpha-beta with perfect move ordering explores b^(n+1) + b^n - 1 terminal positions, with n = d / 2 (that's C integer division). That is to say, the order of magnitude of alpha-beta with perfect move ordering in the square root of minmax. Intuitively, that's because at one ply out of two, you get a beta cutoff with the first move, so the effective branching factor is 1 there. Rémi
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.