Author: Robert Hyatt
Date: 15:28:13 05/09/01
Go up one level in this thread
On May 09, 2001 at 17:59:48, Jesper Antonsson wrote: >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? I am not sure what you mean. There is no "linear" list of chess positions in any way I can think of using "linear". The complexity issue simply asks "how hard will it be to compute this function if I increase the number of inputs by 1?" In the case of chess, an "input" is a "ply"... > 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). How do you define "deep enough?" If we could prove that white wins within 80 plies, then that would do it. but so far, we have not proven that. And since the game isn't over until mate or stalemate occurs, unless the two players decide to call it a draw for various reasons, I'm not ready to say it is "finite" until someone offers reasonable proof that it is... > >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. > We just have to disagree then. I see _no_ way to express f(w,d) compared to f(w,d+1) in any polynomial form. And I see nothing that convinces me that we can say the game of chess is finite without a rule change that mandates the 50- move rule. >So, now I have done my best and if you still don't agree, we'll have to agree to >disagree. Agreed. :)
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.