Author: Andrzej Nagorko
Date: 05:30:19 05/10/01
Go up one level in this thread
[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. Andrzej
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.