Author: Dann Corbit
Date: 11:09:16 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. But you just gave that as a necessary and sufficient condition for O(1). If it is not finite, then it *has* to be infinite. Isn't that the only alternative? >I've been polite and expect you to do the same. I'm sorry, I can be something of a jerk at times.
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.