Author: Jeremiah Penery
Date: 11:02:05 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. No, it's not. Tell me how the time it takes to search the tree relates to the input depth of the tree. It's constant?! So we can search depth 1000000 in the same time it takes to search depth 3? That's news to me. By your reasoning, every algorithm is O(1), correct? All inputs must be finite, right? The fact that the chess tree is arguably finite does not render tree-search algorithms O(1)! I can theoretically pass an infinite tree to these algorithms - are you going to tell me now that it's O(1)? I'll go to Dann's BogoSort example. If I give it input of 5 numbers, are you going to tell me the _algorithm_ is O(1)? O-notation is used to estimate worst-case running time _based on the size of the input_! It has nothing to do with the specific number/size of inputs you choose. Bogosort seems clearly O(n!), whether any specific input size is finite or not!
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.