Author: Jesper Antonsson
Date: 14:59:48 05/09/01
Go up one level in this thread
On May 09, 2001 at 16:11:02, Robert Hyatt wrote: >again, what is the point of such a distorted definition of "O"? We can't >sort infinite items. We can sort reasonable sized sets of items. And we >know how to define the running time of the sort using the number of items as >a parameter. N^2, NlogN, etc. your definition simply does _not_ agree with >what is in any theory book I have on my shelf, starting with Aho, going thru >Ulman. This is about the cost of computing something. There is no requirement >that the size of the input be infinite. Because no such algorithm will >terminate, ever. Bob, this is my last try: A chess algorithm, smartly implemented, with tree search, and that stores each computed value to reuse on transpositions and researches and such, is not an ordinary general tree search algorithm; it is restricted. Would you call a search through a linear list exponential? It is a tree, you know, just with a branching factor of one... Another type of restriction is imposed, by the rules of chess, on the chess tree. That restriction is (at least potentially, with careful coding) *inherent in the algorithm*. That limitation is that "another ply" won't take more time when were deep enough, and that's why the algorithm is O(1). If you think the standard definitions in Aho, Ullman and friends does not agree with me, you simply do not understand those definitions or the fundamental search restrictions *inherent* in a "good" (but of course impractical, never- terminating-in-practise, yada, yada) chess-solving-algorithm. Again, it's not about "finite input", (Dann's peculiar misinterpretation) it's quite the opposite, that *arbitrary* input (depth) can processed in (pre-selected) theoretically finite time. That is by *definition* O(1). Then there is the *problem* of solving chess. Despite what you think, the use of a specific algorithm on a certain problem does not say anything about whether the *problem* is P, NP or whatever. This is partly because we might have bad algorithms. I have already given other reasons why chess is P and I don't have time for repetitions or better explanations, so I can only ask you to reread. So, now I have done my best and if you still don't agree, we'll have to agree to disagree.
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.