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.01 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.