Computer Chess Club Archives


Search

Terms

Messages

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
>made.
>
>, 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
>
>What is the meaning of breadth first and best first search?
>
>Uri

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.

http://www.xs4all.nl/~aske/mtdf.html

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.

wylie



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.