Author: Jesper Antonsson
Date: 14:09:56 05/16/01
Go up one level in this thread
On May 15, 2001 at 21:00:24, Jeremiah Penery wrote: >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. Nonsense. There are chess algorithms, and the rules of chess are a part of those algorithms.
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.