Author: David Rasmussen
Date: 14:41:05 05/17/01
Go up one level in this thread
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. 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). >> 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. >>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. >>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.