Author: Jesper Antonsson
Date: 13:43:38 05/11/01
Go up one level in this thread
On May 11, 2001 at 03:06:14, David Rasmussen wrote: >On May 10, 2001 at 17:19:43, Jesper Antonsson wrote: >>The chessboard doesn't grow. The current rules of chess is a part of the >>algoritm and the *only* input to it is the target depth. Therefore, a "good" >>chess algorithm is by definition O(1), as the time T(n)<C when n->inf, >>C constant. >That is not true. On the contrary, it's true by definition. >As I said in my original post (and what most people in this >group - including you - do not understand), you cannot talk about the >complexity of some algorithm on some fixed input e.g. chess. Wrong, I consider the target depth to be the input. That is not fixed or limited. The rules of chess (and thereby the search space) is a part of the algorithm, not a parameter, as I see it. Your view is also ok, but I consider it far fetched and a change of subject. This is the Computer-CHESS Club, and the original peculiar statement by Mr. Hyatt was that CHESS was NP and exponential (in the depth). Then the rules of chess are fixed, as is the search space. The target depth is not, and that is what was considered to be input. >You can look at some algorithm (such as alpha-beta search, or tablebase >generating) and talk about what _would_ happen if the input datasize grew, >even if it will never grow in practice. This is an analytical tool. Of course, that's what complexity analysis is about. We disagree on what to choose as input data size. Please understand this, and please understand that your choice is a change of topic from the original discussion. >If you _know_ for a fact that you are never going to sort more or less than, >but precisely 10000 integers, you will still want to look at what happens _if_ >the >datasize grew. At least if you want to make any claims of complexity classes, >and say that the algorithm is O of anything. Otherwise it doesn't make sense. >You can't just say that chess is a fixed, finite domain, therefore any >algorithm >that terminates, that solves chess, is O(1), just because it terminates in >finite time. This is very basic. You misinterpret the argument. Because of the the rules of chess, the search takes finite time even when the the input (depth) approaches infinity. Again, that is by definition O(1). The comparison with sorting a 1000 integers isn't valid, as the input (search depth) isn't fixed for chess. I would say that the "real" domain is infinite, as the target search depth can be any positive integer. >>>Tablebases are not a solution, since it takes exponential time to generate >them. >> >>Not correct, theoretically it takes constant time to generate them, (because >>when we have done the 32 man TBs, we are done) so they are a "solution". > >They _do_ take constant time on a fixed input, like the chess domain, but that >is not what is meant when you talk about complexity. If it were, then _any_ >algorithm that terminates in finite time (all practical algorithms that we know >and use) working on a finite dataset, would be called O(1). It's not. Again, >this is very basic in understand complexity classes and big O notation. I agree, what I meant by a "solution" was that the constant time of table base generation is a proof that chess can be searched in finite time. Then that implies that the exponential behaviour will stop if we search deep enough with a good algorithm. Therefore, the search is constant in the size of the input, the target search depth. >If you don't agree, you have misunderstood something. Go ask your teacher, >professor or instructor where you "learned" about complexity. He'll say the >same. My understanding of this topic is without a doubt as good or better than yours, thank you very much. I agree that it is not meaningful to talk about complexity for sorting 1000 items, while I don't agree that's comparable to chess. You, however, doesn't seem to understand that *depth* was the input considered in the start of this argument, and that *chess* is the topic. My claim about good chess algorithms being O(1) is by definition true. Your claim that a game algorithm that "generalizes" chess and takes different rules (or search spaces) as input would be exponential may also be true, but that's quite irrelevant.
This page took 0.04 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.