Author: Martin Schubert
Date: 02:54:02 05/16/01
Go up one level in this thread
On May 15, 2001 at 18:26:25, David Rasmussen 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. >> > >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. The old problem with discussing about mathematics. It doesn't make sense to discuss because usually something is right or wrong. But if someone doesn't understand why it is write or wrong because he doesn't understand the mathematics you can discuss infinitely. Some people believe it's O(1). Let them believe. They don't understand what O-Notation is about, and probably that doesn't matter because they won't need it.
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.