Author: Jesper Antonsson
Date: 15:16:15 05/09/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: >>>>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. >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...
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.