Author: Robert Hyatt
Date: 09:55:49 05/09/01
Go up one level in this thread
On May 09, 2001 at 10:35:38, Ricardo Gibert wrote: >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. > I certainly didn't mean to insult him. However, whether there is a finite number of positions or not has nothing to do with the complexity issue here. In a sort, I can't sort an infinite number of items. In chess, I do not _have_ to terminate the search after 50 move rule has been satisfied. So _nothing_ places an absolute bound on the longest chess game that can be played. And without that bound the entire discussion is pointless since we can't search an infinite chess tree any more than we can sort an infinite number of input values. But the O(W^D) still is perfectly valid and means exactly what it says when the topic is searching a chess tree. There is even nothing that says that for all possible chess games, W decreases. I can simply shuffle a knight back and forth forever and never change W at all... now if you want to make the 50-move-rule _absolute_ then the size of the tree is bounded, but the complexity is _still_ O(W^D) for 0 <= D <= X where X is the value your oracle gives as the deepest possible tree. BTW, if someone tells me "Hyatt, your computer skills are beyond reproach but your chemistry is weak" I won't be insulted. I would realize it is true. >> >>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.