Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Search algorithms in chess programs

Author: James Swafford

Date: 06:20:17 12/13/01

Go up one level in this thread


On December 13, 2001 at 03:33:07, Wylie Garvin wrote:

>On December 12, 2001 at 23:27:58, Russell Reagan wrote:
>
>>Depth-first search is usually what is used in chess programs (at least all that
>>I have seen source for). What are the drawbacks of other search algorithms such
>>as breadth-first and best-first that prevent them from being more widely used in
>>chess programs?
>
>speed and space requirements.  Keep in mind that since nearly all chess programs
>use iterative deepening on their depth first searches, and since chess has a
>high branching factor, even with all the pruning techniques (well >= 2 anyway),
>this means they are essentially getting a breadth-first search in depth-first
>space, O(ply).  With selective search not all lines have the same "depth", but
>the principle still applies.
>

I agree with all that except the O(ply) part.  I think that implies
a linear growth, when in fact it's closer to O(bf^ply).

--
James



>wylie



This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.