Author: Ricardo Gibert
Date: 11:05:16 05/09/01
Go up one level in this thread
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.
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.