Author: Jesper Antonsson
Date: 12:22:28 05/10/01
Go up one level in this thread
On May 09, 2001 at 18:55:00, Dann Corbit wrote: >On May 09, 2001 at 18:16:15, Jesper Antonsson wrote: > >>On May 08, 2001 at 23:44:33, Robert Hyatt wrote: >> >>>On May 08, 2001 at 18:05:08, 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. >> >>They are different, but both finite. You have discussed both and their sizes in >>RGCC. You said nothing that I can remember about any of them being infinite. >> >>>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... >> >>Chess is not an unbounded tree search. > >When dealing with an exponential process, only very small inputs can be >computed. If chess were O(1), it would be computationally feasible. Chess is >not computationally feasible. Sorry, but that is not true. O(1) does not mean "computationally feasible". If the constant time is too large, it is too large... >Let's use gaussian elimination to solve a 1 trillion by 1 trillion matrix. >According to your definition, this is O(1). No, it's not, gaussian elimination is O(n^3) (i think). It's not very meaningful to use ordo notation on a problem instance, however. I think you have misinterpreted "my" definition. >But you won't ever solve it, even with a simple O(n^3) problem size. > >Why do we bother with complexity study in the first place? What are we trying >to achieve? We want to know how hard a problem is to solve. Is chess really >among the easiest of all possible problems? > >I submit that this definition is not useful for any real world computations. Hey, I think there was someone who found a O(n^2.73) algorithm for matrix multipliction, which is best so far, but it isn't used in real implementations because of the large constant factor. The theoretical complexity isn't all that is needed when we choose algorithms for real world computations. >>>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. >> >>But chess is both the instance and the class. >> >>>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, it has an upper bound (for time and space) when depth->inf and is therefore >>N. And the standard tree search is not a proof of best behaviour for an >>algorithm that solves the problem, there might be better algorithms. This last, >>you really should be able to admit. >> >>>Ergo I am not sure why the argument is even taking place. IE Aho, Upcroft, >>>Ulman, Knuth, et al have pretty well addressed the tree search problem and its >>>complexity... >> >>Yes they have. It's just the small matter of understanding left... > >Did you note the references I quoted which stated chess belongs to NP. No, I missed those. Would you care to repeat them? (They are wrong, of course, but interesting nonetheless.)
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.