Author: Vincent Diepeveen
Date: 05:45:00 05/20/04
Go up one level in this thread
On May 19, 2004 at 22:59:15, Robert Hyatt wrote:
>On May 19, 2004 at 22:28:50, Vincent Diepeveen wrote:
>
>>main() {
>> search(10); // search 10 ply depthfirst
>>
>> for i = 1 to 10 // depth limited 1..10 ply search
>> search(i);
>>}
>>
>>search(int depth) {
>> if depth == 0
>> then return eval();
>> else for all moves
>> search(depth-1);
>>}
>>
>>Robert Morgan Hyatt doesn't seem to understand this in his thesis.
>
>
>Find any good ai book. Look up "depth first search". minimax and alpha/beta
>are examples. The idea is that the memory space requirement for depth-first is
>O(d) while the memory space requirement for breadth-first (the _only_
>alternative) is O(w^d).
This is not about memory space but how you search.
Note there is only a few who make the mistake calling this depth first.
We first search the siblings before going into the deep.
So for a search line X we first search it 1 ply then all its brothers, 2 ply
then all its brothers, 3 ply then all its brothers etcetera
So it is definitely depth limited. And it is more like breath first search than
a depth first search. But definitely not a depth first search.
Therefore majority calls it all depth limited, even the deep blue team does do
so.
>depth-first search
>
>(algorithm)
>
>Definition: (1) Any search algorithm which considers outgoing edges of a vertex
>before any neighbors of the vertex, that is, outgoing edges of the vertex's
>predecessor in the search. Extremes are searched first. This is easily
>implemented with recursion. (2) An algorithm which marks all vertices in a
>directed graph in the order they are discovered and finished, partitioning the
>graph into a forest.
>
>Also known as DFS.
>
>See also breadth-first search, best-first search.
>
>Note: [CLR90, pages 477-485]
>
>Author: PEB
>
>Or go here:
>
>http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic26/#dfs
>http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/NODE65.HTM
>
>
>I showed this to a faculty member that teaches AI at another University. He
>responded "is this guy a clown, an idiot, or is he really that stupid?" I think
>that says it all.
>
>So it isn't "Robert Morgan Hyatt" that doesn't know what he is talking about.
>You need to look in the mirror. Once again you are _dead_ busted here. minimax
>and alpha-beta do _exactly_ as the above definition says. Just do a google
>search on depth-first search, read, and stop looking like a fool.
>
>And by all means _stop_ making up false definitions to suit your own agenda.
>You can't usurp the meaning of well-known AI terms and re-define them to mean
>something you choose.
>
>Yet one more big lie. When will you grow up and stop?
>
>lookin' even better, Vincent...
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.