Computer Chess Club Archives




Subject: Re: Complexity Analyses of Alpha-Beta

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?

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.


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.