Author: Jesper Antonsson
Date: 14:50:11 05/17/01
Go up one level in this thread
On May 17, 2001 at 17:41:05, David Rasmussen wrote: >On May 17, 2001 at 17:16:59, Jesper Antonsson wrote: > >> >>The algorithms used for chess are chess algorithms, which are alpha-beta with >>added constraints. The constraints make the algorithms O(1). >> > >It makes the chess programs O(1), but I don't consider a chess program an >algorithm, and it is certainly not that "algorithm", that most of us are >talking about here. Well, I started the argument with Bob, and he seemed to agree with me that we were discussing chess and that depth was the input, at least. Again, I don't think you speak for "most of us". >The reason why I won't waste time on defining this (and all other >real entire programs) as algorithms, is that, on real computers with finite >sizes, input will always be finite, so the algorithm will always terminate >(unless for pathological cases), and so they are all O(1), and so they're >uninteresting to discuss, and define as algorithm, let alone make complexity >analysis on, because the answer is always O(1). Now you are at it again, confusing the finite search trees with finite inputs. They are not the same. >>> 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. >> > >No it is this discussion to the point. The point is that we who disagree with >you, have a different opinion of what algorithm(s) we are talking about, how >much of it is an algorithm, an what an algorithm really is. I think none of us >disagrees that plain chessprograms are O(1), as is all other real software in >real computers. As this is a tautology, and uninteresting, this is obviously not >what most of us are talking about, even if you are. See above. You are confused. >>>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. >> > >I don't agree with your opinion of what an "algorithm" is, and the part of the >domain (a chess program) that you have chosen to define as an algorithm, and to >make statements about. Well, too bad for you. I have stated all along that I was talking about chess algorithms with the inherent constraints the rules of chess implies. >>>Or find someone who agrees with you. >> >>And I have had people agreeing with me already, didn't you see? > >Not really, but there are a lot of messages.
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.