Author: David Rasmussen
Date: 15:02:10 05/16/01
Go up one level in this thread
On May 16, 2001 at 17:24:25, Jesper Antonsson wrote: >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. > It's one of the parameters in the current algorithms we have, that we can vary. >>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 definition says that if something is O(f(n)) then it means that it is upper bounded by this function with added or multiplied etc. lowerorder terms, for all n larger than some constant a. So even in your sick sense, it it still O(exp(n)) because that is an upper bound. What everybody means here (but it doesn't matter since everyone agrees on what is meant), is that current chess-solving algorithms is big Omega of exp(n), which means that it is _tightly_ bounded by this function. The algorithms used for chess such as alpha-beta, are general, and certainly Omega(exp(n)). The input for alpha-beta, in case of solving a game, is the game tree, defined by the rules. In most games, this gametree is finite, although very large. Chess is just one possible input gametree for alpha-beta. If you want to analyze complexity, you have to do two things: You have to choose what parameters to correlate with runtime, and you have to analyze what happens with runtime, as input varies. Varying the input means to vary the gametrees. Chess is just one gametree, just as a fixed list of integers is just one input for a integer sorting algorithm. Choosing a parameter is important too. If you choose searchdepth, in normal alpha-beta implementations, then you will find that runtime grows exponentially when searchdepth grows linearly. If you want to take the size of the gametree in nodes as your parameter, you will find runtime grows linearly when gametree size grows linearly (naturally), but this is uninteresting. In any case, none of the algorithms we know, operates in constant time, regardless of searchdepth or gametree size. >>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). Prove to me that it is. Or find someone who agrees with you.
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.