Author: Christophe Theron
Date: 12:17:41 11/08/03
Go up one level in this thread
On November 07, 2003 at 09:22:45, Gian-Carlo Pascutto wrote:
>On November 06, 2003 at 19:48:33, Robert Hyatt wrote:
>
>>On November 06, 2003 at 10:18:37, Gian-Carlo Pascutto wrote:
>>
>>>On November 06, 2003 at 09:47:32, Robert Hyatt wrote:
>>>
>>>>I'm not sure how you could say that the distinction is very hazy. They
>>>>are as different as night and day...
>>>
>>>Read the thesis, you will understand.
>>>
>>>--
>>>GCP
>>
>>This is one of those cases where I don't have to "read the thesis to
>>understand". There's a _ton_ of books that discuss the differences
>>between breadth-first and depth-first search strategies. They are
>>_never_ mentioned in the same paragraph as having similar properties.
>>Because they don't.
>
>They search the same (amount of) nodes. For game tree search, that's a pretty
>fucking important performance criterium.
>
>Discovering the similarity between SSS and AlpahBeta+TT allowed MTD(n,f) to
>be developed, which is one of the best tree searching algorithms out
>there.
SSS (actually it's SSS*, read "Heuristics" by Judea Perl, 1990) is not a
practical tree search algorithm, because you need to store the entire search
space if you want to use SSS*.
MTD(f) has been proved to search the same tree as SSS* in extreme cases (when
the hash table has an infinite size actually).
And MTD(f) is a search algorithm that can practically be implemented. It suffers
if your hash table is not big enough (it becomes significantly worse than SSS*),
and will traverse the same nodes multiple times, but still works. SSS* cannot
work if you do not have enough storage.
So SSS* and MTD(f) have something to do with each other, but they are vastly
different. So different actually that nobody would try to implement SSS* in a
competitive chess program when some have used MTD(f) succesfully.
All exhaustive (brute force) search algorithms have something to do with each
other in the sense that they will search the same tree.
But from a practical point of view, these algorithms end up with vastly
different properties.
I think that's what Bob wants to stress out.
Christophe
>You're saying that's all irrelevant because it's best first and depth
>first and hence they have 'automatically' nothing to do with each other
>and anyone suggesting otherwhise is 'automatically' wrong even though
>you've not read the articles explaining it?
>
>Geez, maybe tomorrow you'll start giving 'proof by induction' too.
>
>--
>GCP
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.