Author: Jeremiah Penery
Date: 10:47:32 05/09/01
Go up one level in this thread
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. It would have to have some bit of knowledge beforehand about the game we don't currently have. Even if we have the 32-man tablebases, the problem of calculating them would be O(exp(n)) in memory, even if they only took 10 minutes to calculate! And searching through them to find the answer would be another big problem. The Knight's Tour problem generally took some sort of tree to solve, therefore making it O(exp(n)) (although it could still be computed very quickly on today's computers). But some clever person found an algorithm for it that didn't rely on a tree, therefore reducing the problem to O(n^x). CHESS IS NOT THIS WAY! If you don't agree with this, then all algorithms are O(1), because calculation on an infinite set is impossible, therefore _ALL_ algorithms on _ANY_ set of data input run in O(1) time. Of course, this is absurd.
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.