Author: Ricardo Gibert
Date: 14:23:38 05/09/01
Go up one level in this thread
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."
This page took 0.01 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.