Author: Jesper Antonsson
Date: 14:16:59 05/17/01
Go up one level in this thread
On May 16, 2001 at 18:02:10, David Rasmussen wrote: >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. Yup. >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 algorithms used for chess are chess algorithms, which are alpha-beta with added constraints. The constraints make the algorithms O(1). > 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. Yes, that's one way to look at it, but then it's a different discussion. >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. Obviously. >Varying the input means to vary the gametrees. Not necessarily. > 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. Well, the chess algorithms does not "operate in constant time" but operate in less than a certain constant time. >>>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. I have already proven it. But I'll try again. * Real, existing chess programs source code are generally algorithms. * They take target search depth as input. * As the depth (NOT input) of the game tree is bounded by the rules of chess, (say that the maximum is N), an input of N+k, k>=1 will search exactly the same tree as the search with input N. * Therefore the time taken, t(n)<=C for constant C, when n>N, which makes t(n) belong to O(1) by definition. * We conclude that "good" chess algorithms are O(1) when using depth as the parameter. Please state which of the statements above you don't agree with and why. And please note that the possibility of calculating complexity using other algorithms or inputs doesn't invalidate my proof. >Or find someone who agrees with you. And I have had people agreeing with me already, didn't you see?
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.