Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Search algorithms

Author: Dave Gomboc

Date: 09:01:59 11/09/03

Go up one level in this thread


On November 08, 2003 at 12:43:29, Robert Hyatt wrote:

>On November 07, 2003 at 14:16:16, Dave Gomboc wrote:
>
>>On November 06, 2003 at 22:42:14, Robert Hyatt wrote:
>>
>>>On November 06, 2003 at 22:33:04, Robert Hyatt wrote:
>>>
>>>>On November 06, 2003 at 20:45:57, Dave Gomboc wrote:
>>>>
>>>>>On November 06, 2003 at 19:50:09, Robert Hyatt wrote:
>>>>>
>>>>>>On November 06, 2003 at 11:23:36, Dave Gomboc wrote:
>>>>>>
>>>>>>>On November 06, 2003 at 09:49:33, Robert Hyatt wrote:
>>>>>>>
>>>>>>>>On November 06, 2003 at 09:33:28, Renze Steenhuisen wrote:
>>>>>>>>
>>>>>>>>>On November 06, 2003 at 08:33:49, Gian-Carlo Pascutto wrote:
>>>>>>>>>
>>>>>>>>>>On November 06, 2003 at 05:45:53, Renze Steenhuisen wrote:
>>>>>>>>>>
>>>>>>>>>>>Depth-First Algorithms:
>>>>>>>>>>>  AlphaBeta (Fail-hard, Fail-Soft)
>>>>>>>>>>>  MTD(f)
>>>>>>>>>>>
>>>>>>>>>>>Best-First Algorithms:
>>>>>>>>>>>  SSS*
>>>>>>>>>>
>>>>>>>>>>The distinction between the three (and best-first and depth-first)
>>>>>>>>>>is very hazy, read "Research re: search and research" by Aske Plaat.
>>>>>>>>>
>>>>>>>>>Done that already, but as Aske stated: they search the same nodes, but in a
>>>>>>>>>different order.
>>>>>>>>>
>>>>>>>>>MTD(f) and the others are still DF algorithms, the second list works differently
>>>>>>>>>(i.e., the order in which the nodes are expanded is different).
>>>>>>>>>
>>>>>>>>>Or am I talking rubish?
>>>>>>>>>
>>>>>>>>>Renze
>>>>>>>>>
>>>>>>>>>PS:  Am I missing algorithms (either important or not)?
>>>>>>>>>PS2: Are Scout and NegaScout equal?
>>>>>>>>
>>>>>>>>
>>>>>>>>They are just variations on the same idea.  All fall under the umbrella
>>>>>>>>of alpha/beta depth-first search...  (this is in response to your question
>>>>>>>>PS2).
>>>>>>>>
>>>>>>>>depth-first and breadth-first (best-first is one example of the latter)
>>>>>>>>are totally unrelated other than the fact they both search a tree.
>>>>>>>
>>>>>>>Well, no.  Read Plaat's thesis.
>>>>>>>
>>>>>>>Dave
>>>>>>
>>>>>>
>>>>>>I have read it.  It does _not_ say the two are equivalent in any shape
>>>>>>or form, except for the actual tree searched in certain circumstances.
>>>>>>Depth-first and breadth-first are completely different approaches to
>>>>>>growing a tree, even if on some occasions they grow the _same_ tree.
>>>>>
>>>>>In this particular case, the algorithms search the same tree.  Therefore, I
>>>>>think it's reasonable to claim they are they are equivalent in some shape or
>>>>>form -- not in all shapes and all forms, but at list with respect to the nodes
>>>>>searched and the order in which they are searched. :-)
>>>>>
>>>>>Dave
>>>>
>>>>
>>>>I don't believe that last is correct. IE with respect to order.  Particularly
>>>>comparing members of the breadth-first family to the depth-first family and
>>>>not just picking one specific algorithm from each.
>>>
>>>
>>>BTW,  I hope you don't try to convince me all sort algorithms are
>>>equivalent, just because they take the same list and produce the
>>>same final result.  :)
>>
>>Well, what is correct is that the node expansions are done in the same order.
>>
>>Dave
>
>
>Again, what two algorithms specifically are you comparing?  Best first
>and depth-first _never_ expand the nodes in the same order, except for
>trees where each side has only one legal move at every position...

Replied in other thread.

Dave



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