Author: Jeremiah Penery
Date: 18:00:24 05/15/01
Go up one level in this thread
On May 15, 2001 at 18:04:28, Jesper Antonsson wrote: >Nonsense. This is a theory discussion and I don't give a rats ass about >"real-world" problems. In chess, when you go above a certain depth, the time >taken for the algorithm to complete doesn't increase. In the travelling salesman >problem, for example, another city always increase the time taken for the >algorithm to complete. That's why chess is O(1) and the TSP is not. O(f(n)) is used for algorithms, not specific problems. Chess is a specific problem, but the algorithms we use to search the chess-tree can be applied to other problems, maybe ones where every ply added (to infinity) will increase the running time of the algorithm. These algorithms are demonstrably O(exp(n)). The statement "Chess is O(1)" has absolutely zero meaning.
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.