Author: Robert Hyatt
Date: 07:02:05 05/09/01
Go up one level in this thread
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. 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.03 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.