Computer Chess Club Archives




Subject: Re: Complexity Analyses of Alpha-Beta

Author: Ricardo Gibert

Date: 09:49:44 10/07/03

Go up one level in this thread

On October 07, 2003 at 12:01:33, Renze Steenhuisen wrote:

>On October 07, 2003 at 11:28:03, RĂ©mi Coulom wrote:
>>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
>Is this the _ONLY_ complexity analysis done on chess algorithms? That's kind of
>weird I think, or is it impossible for the others? Or senseless/useless?

The reference he gave has the type of information you are seeking. It is the
only reliable source I know of on this type of theory. It has half a dozen
theorems plus corollaries that include minimax, alpha-beta with optimal move
ordering, alpha-beta with random move ordering, etc. You can also find the paper
in the 43 pages of chapter 9 in the book you can buy at:

For more details about what this book contains, check:

I recommend the book.

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.