Author: Andrew Dados
Date: 15:51:34 05/09/01
Go up one level in this thread
On May 09, 2001 at 18:30:06, Robert Hyatt wrote: >On May 09, 2001 at 17:23:38, Ricardo Gibert wrote: > >>On May 09, 2001 at 16:11:02, Robert Hyatt wrote: >> >>>On May 09, 2001 at 14:05:16, Ricardo Gibert wrote: >>> >>>>On May 09, 2001 at 14:03:01, Dann Corbit wrote: >>>> >>>>>On May 09, 2001 at 13:50:33, Ricardo Gibert wrote: >>>>> >>>>>>On May 09, 2001 at 13:47:32, Jeremiah Penery wrote: >>>>>> >>>>>>>A lot of people seem to be saying that chess can be solved by an O(1), >>>>>>>constant-time, algorithm. Technically, this may be true. _IF_ you had the >>>>>>>proper algorithm that was capable of computing chess exactly[1], it could >>>>>>>exhibit constant-time behavior. The problems are that no such algorithm exists >>>>>>>today, and the constant would be so large as to have no relevant meaning in >>>>>>>today's world - i.e., it would likely be greater than the age of the universe. >>>>>>>All chess programs are currently using some sort of tree-searching algorithm >>>>>>>(Alpha-Beta or variant), which are provably O(exp(n)) algorithms. Time >>>>>>>increases exponentially with the increase in input depth - depth 5 takes >>>>>>>exponentially less time than depth 6, which in turn takes exponentially less >>>>>>>time than depth 7, and so on. The fact that depth _eventually_ ends _IN CHESS_, >>>>>>>has nothing to do with the complexity of the algorithm. Theoretically you can >>>>>>>give the same algorithm an infinitely sized tree, so that constant-time solution >>>>>>>is impossible. For those who say that chess is O(1), it can't be so if the >>>>>>>program in question is using a tree-search algorithm! >>>>>>> >>>>>>> >>>>>>>[1] This O(1) chess algorithm would have to solve the game not by computing a >>>>>>>tree, because tree-search is demonstrably O(exp(n)) for this type of tree. >>>>>> >>>>>>That it is a tree is not relevant. The tree is finite. That's enough. >>>>> >>>>>So your requirement is that the tree is infinite? >>>>> >>>>>As popeye the sailor says: >>>>>"Uck, uck uck, uck." >>>> >>>>A finite constant to be precise. >>>> >>>>I've been polite and expect you to do the same. >>> >>> >>>again, what is the point of such a distorted definition of "O"? We can't >>>sort infinite items. We can sort reasonable sized sets of items. And we >>>know how to define the running time of the sort using the number of items as >>>a parameter. N^2, NlogN, etc. your definition simply does _not_ agree with >>>what is in any theory book I have on my shelf, starting with Aho, going thru >>>Ulman. This is about the cost of computing something. There is no requirement >>>that the size of the input be infinite. Because no such algorithm will >>>terminate, ever. >> >> >>I never said anything about an infinite number of items to sort. I'll quote from >>my answer to E. Nalimov: >> >>"People frequently confuse bounded and unbounded with finite and infinite, >>respectively. >> >>To see more clearly that they are not the same, consider: >> >>(1) The set of *positive* integers. The number elements in the set is not >>finite, but the set *is* bounded. It has a lower bound of 1 and no upper bound. >> >>(2) A set of integers can be unbounded, but finite. Any set of n integers fits >>this, since n is uninstantiated. >> >>(3) A set real of numbers can have both an upper bound *and* a lower bounded and >>still contain an infinite number of elements e.g. [0,1]. >> >> >> >>The definition of big-O limits itself to where n is unbounded. To use the >>definition, n must be unbounded or at least assumed to be. We can make use of >>big-O by instantiating n, but this should not be confused with n being a >>constant to begin with." > >OK... that is a statement of fact. Can you cite where big-O is limited to >cases where N is unbounded? > >And then can you cite a proof that says that based on the existing rules of >chess, the game is finite (or bounded) in size? One proof is that tablebases are computable. And you may precalculate their sizes. And they are correct. -Andrew-
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.