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