Author: David Rasmussen
Date: 00:16:23 05/11/01
Go up one level in this thread
On May 10, 2001 at 08:30:19, Andrzej Nagorko wrote: >[snip] > >>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. >> > > This is probably cause of all confusion here. If you look at "solve chess" >problem as a problem from "given any game tree prove who wins/draws" class, then >this problem has exponential complexity (taking average branching factor and >tree depth as data size measure, for example). Which is correct approach IMO. On >the other hand some people try to define it as "trim chess tree to depth n and >prove who wins/draws in this tree" and take n as data size measure. Then, thanks >to 50 moves draw rule, proof tree will stop growing for n big enough and this >class of problems will be solveable in constant time. > No it isn't. Because, as I said in my post, you can't talk about complexity without analyzing what happens when the datasize grow. Even if the data that you are actually wanting to use (the chess domain), is fixed, you will still have to look at what happens when the dataset grows. And if the dataset grew (e.g. if the boardsize was n*n and n grew, or the number of different kinds of pieces grew, or...), you would see that even the approach you describe is exponential in time. What people here seem to not understand, is the very basics of what it means to say that something is exponential (or quadratic, linear, logarithmic or constant). It means that in some sense we can draw a graph of some exponential function. But what will be on the axes? On the 2. axis will be the "runtime", that much is clear to anybody. But what is on the 1. axis? The dataset size! And when you take some algorithm you can't just pick one point at the 1. axis (such as chess) and say "this is constant time", just because you have some point on the graph here. You will have to look at how it grows.
This page took 0.01 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.