Author: David Rasmussen
Date: 15:12:04 05/16/01
Go up one level in this thread
On May 16, 2001 at 18:00:22, Miguel A. Ballicora wrote: > >Excuse me, I am not a expert on this, but I am very curious about >a phrase that I have seen in all this discussion. "Chess is O(1)" >Is not the notation O() applied to algorithms? Yes. >Well, chess is not an algorithm, it is game. So, should not we talk about >that alpha/beta is O(whatever), Minimax is O(whatever) etc.? Yes. That is exactly the problem. Some people thinks that chess together with alpha-beta is an algorithm in itself. But it is not. The extra stuff that is added to alpha-beta for it to play chess, is just stuff to describe the input to alpha-beta, the gametree. If I make a program sorting one particular list of integers, then this programs runtime is O(1), because the algorithm (which could be e.g. O(n*log(n))), and the input for the algorithm where mixed in the implementation, and it would always execute in the same time, regardless of inputsize, because we can't vary the inputsize. So the runtime of this particular program is O(1). But the runtime of the algorithm used, is not O(1), and the input is not O(1), because that doesn't even make sense. In the same way, chessprograms are O(1), in that they would solve chess in constant time, but the algorithms we use to do it, are not. They are exponential. And the input, chess, is not O(1), because that doesn't even make sense.
This page took 0.02 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.