Author: David Rasmussen
Date: 00:06:14 05/11/01
Go up one level in this thread
On May 10, 2001 at 17:19:43, Jesper Antonsson wrote: >On May 10, 2001 at 04:26:27, David Rasmussen wrote: > >>In the same sense, even if chess is finite (which it is), it is still not O(1) >>to solve it, because you will have to look at what happens when the dataset >>grows. In this case, what happens when e.g. the chessboard grows? With any known >>algorithm, the complexity grows as O(a^n). If anyone have an algorithm that is >>in a complexity class lower than this, I would really like to know. > >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. 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. 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. 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. >>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. 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.
This page took 0.05 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.