Computer Chess Club Archives




Subject: Re: Search algorithms in chess programs

Author: Wylie Garvin

Date: 01:14:23 12/13/01

Go up one level in this thread

On December 13, 2001 at 03:47:39, Uri Blass wrote:

>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
>Nearly all?
>I doubt it.
>There are a lot of weak chess programs that do not use this technique.
>One of them (TSCP) even could win a tournament of weak programs that Dan Corbit
>, 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.
>What is the meaning of breadth first and best first search?

In a breadth first search, first you traverse all the nodes at ply 1, then all
the nodes at ply 2, and so on.  In a best-first search, you actually expand
nodes in some order determined by a "best" criteria; an example of this would be
proof-number search, where the criteria for "best" is that a node is a
most-proving node.  Best-first search algorithms generally require you to store
the whole search tree, not just the current line.  Same for breadth-first search
if you do it the naive way.  Another example is Stockman's SSS* algorithm, a
best-first search algorithm.  It turns out that there's an instance of Aske
Plaat's MTD framework (i.e. an iterative depth-first framework) which is
equivalent to SSS*, inasmuch as it expands the same nodes.  Plaat reports that
it doesn't perform as well as the MTD(f) instance, though.

In another sense, the term "depth first" for an MTD instance is misleading,
since it consists of a bunch of zero window alpha-beta calls.  In each of those
alpha-beta calls different nodes will get backward pruned, so different children
will get expanded.


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