Computer Chess Club Archives

Search

Messages

Subject: Re: Search algorithms in chess programs

Author: Wylie Garvin

Date: 00:33:07 12/13/01

Go up one level in this thread

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.

wylie

• Re: Search algorithms in chess programs James Swafford 06:20:17 12/13/01
• Re: Search algorithms in chess programs Uri Blass 00:47:39 12/13/01
  • Re: Search algorithms in chess programs José Carlos 06:17:23 12/13/01
    • Re: Search algorithms in chess programs Uri Blass 07:13:32 12/13/01
      • Re: Search algorithms in chess programs Christophe Theron 09:35:35 12/13/01
  • Re: Search algorithms in chess programs Wylie Garvin 01:14:23 12/13/01

This page took 0.01 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.