Author: Robert Hyatt
Date: 07:15:38 05/20/04
Go up one level in this thread
On May 20, 2004 at 08:45:00, Vincent Diepeveen wrote:
>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.
That "few" include the faculty at every university that teaches AI or computer
science algorithms. Every author of every book that discusses tree searching in
any form. Every author of every paper on the subject.
>
>We first search the siblings before going into the deep.
No we don't.
>
>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
No we don't.
>
>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.
It is _definitely_ a depth-first search. There are only _two_ alternatives.
Breadth-first and best-first. Best-first could look like either depth-first or
breadth-first depending on how the tree happens to be expanded. But there are
_no_ alternatives to depth-first or breadth-first. You are just looking
_incredibly_ foolish once again.
Go pick up _any_ book on CS algorithms. I do mean _any_ book. Or do a google
search. Do anything so that you will stop looking like a complete idiot.
>
>Therefore majority calls it all depth limited, even the deep blue team does do
>so.
depth-limited is a subset of depth-first.
>
>>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.