Author: Ricardo Gibert
Date: 07:35:38 05/09/01
Go up one level in this thread
On May 09, 2001 at 10:02:05, Robert Hyatt wrote: >On May 09, 2001 at 00:41:38, Uri Blass wrote: > >>On May 08, 2001 at 23:44:33, Robert Hyatt wrote: >> >>>On May 08, 2001 at 18:05:08, Jesper Antonsson wrote: >>> >>>>On May 08, 2001 at 15:58:05, Dann Corbit wrote: >>>>>On May 07, 2001 at 17:03:05, Jesper Antonsson wrote: >>>> >>>>>>I can use you as a reference. I remember you in RGCC discussing upper limits on >>>>>>the number of distinct positions in chess and as far as I can remember you >>>>>>agreed there was such a limit. Thus the search space is finite and you can store >>>>>>partial results as you search, and when you have searched all nodes once, you >>>>>>are done. "Another ply deeper" will be almost instantaneous, just as when you >>>>>>find a mate in an easy position and then pull results from hash. NOTE: The >>>>>>practicality of the above approach, or the number of atoms in the universe, is >>>>>>totally irrelevant. >>> >>> >>>I want to point out that the above is apples and oranges. apples = number of >>>unique positions on a chess board; oranges = number of unique positions that >>>occur in games. Why are they different? It has to do with 3-fold repetition >>>and the 50-move rule. IE each unique "position" as you are calling them can >>>be counted as a huge number of chess positions, because there are _lots_ of >>>ways to reach the same position by different sequences of moves. And each >>>of those positions, even though they match piece for piece on the board, they >>>are totally unique. >>> >>> >>>> >>>>>All inputs into any computer program must be finite. Otherwise, the program >>>>>cannot ever terminate or even stop reading the input. >>>> >>>>Yes, and that is irrelevant. I haven't mentioned anything about infinite inputs, >>>>by the way. >>>> >>>>>O(f(N)) means that the time spent by the algorithm will always lie below some >>>>>constant times the function f() if N is large enough. >>>> >>>>Yes, and for chess we can choose a constant that suffices for all N if f(N)=1. >>>>In other words, when the depth is large enough, the search stops exhibiting >>>>exponential properties and another ply won't take any more time than the current >>>>ply, just as when you find mate. Is this so damned hard to understand? >>>> >>>>>Chess is exponential (with all current algorithms). To argue otherwise is just >>>>>plain silly. Similarly for other NP-hard problems or problems of any nature. >>>> >>>>It's you who don't know your theory. >>>> >>>>>Consider sorting. We are not going to insert an infinite set into our sorting >>>>>algorithm. Even if we could magically sort in O(N) it will never terminate. >So >>>>>we are *ALWAYS* talking about finite inputs. The type of function determines >>>>>how large a value of N is feasible. Will you solve a chess tree of depth 5000? >>>>>No. Not now. Probably not ever. As in never-ever. >>>> >>>>Correct, and irrelevant. >>>> >>>>>Your arguments are absurd. >>>> >>>>*sigh* I will never solve chess. Humanity will probably never solve chess >>>>either. A practical, live, chess search from the initial position will exhibit >>>>exponential behaviour. Any real input to an algorithm will be finite. And all >>>>that is all totally irrelevant. The point is that the chess search space is >>>>theoretically finite, and therefore, at a large depth, the search will stop it's >>>>exponential behaviour. That this depth cannot be attained in *practise* has >>>>nothing to do with chess' NP-ness, because that is a theoretical property for >>>>which such practical considerations is irrelevant. >>>> >>>>If you want to misuse well defined theory, I can't stop you, but this is getting >>>>ridiculous. >>> >>>Why not just pick up any theory book and see where a tree search is >>>placed in complexity classes? I'll be happy to cite a couple of dozen such >>>books on my office bookshelves... >>> >>>You are contradicting your self multiple times. Simple sorts are O(N^2). >>>Yet for infinite input they _never_ terminate. Yet they can be sorted with >>>an algorithm in polynomial time. I can give you a sample of a non-deterministic >>>P algorithm as well if you want. NP or not NP doesn't have anything to do with >>>a specific problem instance. It has everything to do with how the problem >>>behaves as the number of input values increases. In the case of chess it is >>>clearly exponential, which is _not_ any form of a polynomial. >> >>No >>Chess is clearly polynomial and even O(1) like every solvable problem that is a >>practical problem. > > >Then give me a polynomial with a term for depth that will produce the number >of nodes the tree will contain for any depth D. > >Note that a polynomial is of the form: > >N = AX^N + BX^(N-1) + CX^(N-2) + ... + constant > >The second you have a power of X that is not a constant, but is some function >of depth (D) then you do _not_ have a polynomial. > > > > > >> >>You need constant time to solve chess when the problem is only that the constant >>is large. > >That has _nothing_ to do with a polynomial. > > >> >>The only problems that are exponential are problems when the size of the input >>has no finite upper bound. >>You can see the input of every practical problem in the world as something that >>has an upper bound so saying that an algorithm is not O(1) has only mathematical >>meaning and not practical meaning. >> >>Uri > > >Uri.... your chess skills are great. But your CS skills are woefully lacking >when you claim N = W ^ D can be converted into a polynomial. Generally, the formula N = W ^ D as it is applied to computer chess assumes for various reasons assumes that w is constant and D unbounded. The actually case is that w is variable and goes to zero for a sufficiently large and finite D, so that N is actually bounded by a finite constant. The bottom line is that in order to order to solve chess, only a finite number of positions need to be considered. This number may be absurdly huge, but it is finite all the same. Therefore, the problem is cannot be NP. BTW, I think your reply to Uri is surely insulting to him and I think he is owed an apology. > >If you have any theory books handy, tell me the title and author and I will tell >you the page number when the tree type of tree search we are talking about is >shown to not be representable by a simple polynomial.
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.