Computer Chess Club Archives


Search

Terms

Messages

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?
>>>
>>>Renze
>>
>>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?
>
>Renze

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:

http://www.amazon.com/exec/obidos/tg/detail/-/1575862123/102-4859423-6363344?v=glance#product-details

For more details about what this book contains, check:

http://www-cs-faculty.stanford.edu/~knuth/aa.html

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.