Author: Jesper Antonsson
Date: 14:24:25 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). Yes. And the parameter we vary is search depth. >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. If you vary other things than depth, for example board size, I'm not sure that "exponential" suffices. (It's not chess any longer either.) But target depth can be varied, and that is also the usual input to a chess algorithm, along with some A/B bounds and such. >The O(1) "argument", apart from being absurd nonsense, and a misuse of big-O >notation, has no real value for anything or anyone. I don't claim it has "real value", I just claim it is correct. It adheres to the definition. Check it out. (Use the definition to prove me wrong!) >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. Yeah, I have no problem with that. But it's still O(1).
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.