Author: Dann Corbit
Date: 15:55:00 05/09/01
Go up one level in this thread
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. Let's use gaussian elimination to solve a 1 trillion by 1 trillion matrix. According to your definition, this is O(1). 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. >>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.
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.