Author: Robert Hyatt
Date: 21:27:00 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. 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. I am reminded of a story: A young kid walks in after school one day and says "Dad, can you explain the difference between theory and reality? We were discussing this in school today and I simply didn't get the difference." The dad thinks for a few minutes, then says "Son, go into the kitchen and ask your mother if she would have sex with the mailman for $1,000,000.00." The young kid walks away puzzled, but does as his dad suggested, and asks his mother the question. She thinks for a couple of minutes and says "Yes I would." The young kid returns to his dad and says "Dad, I asked her, and she said 'yes', but I don't see what this has to do with theory and reality..." The dad explains, "Son, based on that answer I can determine two things: (1) in theory, we are millionaires; (2) in reality, your mother is a slut." :) Computers are real, not theory. Alpha/Beta is O(W^D) not O(1). Let the theorists spend their money and develop their O(1) algorithms. :)
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.