Author: Uri Blass
Date: 21:41:38 05/08/01
Go up one level in this thread
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. You need constant time to solve chess when the problem is only that the constant is large. 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
This page took 0.04 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.