Author: Robert Hyatt
Date: 15:30:06 05/09/01
Go up one level in this thread
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?
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.