Author: Dann Corbit
Date: 11:03:01 05/09/01
Go up one level in this thread
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."
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.