Author: David Rasmussen
Date: 15:26:25 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. > You can "resize" the problem of chess and the time to solve it will change too. In an exponential manner. You can't talk about _one_ problem being O of anything. You can talk about a class of problems with at least one parameter to vary, and claim that the time to solve such a problem, is bounded by some kind of function, say an exponential one, when you vary that (or those) parameter(s). In sorting, it's the size of the dataset. In TSP, it's the number of cities. In chess, there isn't anything you can change, and still call it chess, but there are a lot of parameters that you can choose to change, that will change the size of the game tree, to reveal the nature of a game such as chess, when it comes to solving it. You will find that all known algorithms, in this way, is predicted to run in exponential time with respect to this parameter. The O(1) "argument", apart from being absurd nonsense, and a misuse of big-O notation, has no real value for anything or anyone. The notion that chess in it's nature is an exponential, combinatorial problem, on the other hand has lots of real meaning and consequences for anyone who deals with it.
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.