Author: Robert Hyatt
Date: 13:11:02 05/09/01
Go up one level in this thread
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.
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.