Author: Robert Hyatt
Date: 22:21:43 05/16/01
Go up one level in this thread
On May 16, 2001 at 18:12:04, David Rasmussen wrote: >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. I have tried to be quite clear in my use of the word "chess", saying on several occasions that by "chess" I really mean "the alpha/beta minimax algorithm used to play the game of chess." Chess is easier to type. I think most everybody knows what we are talking about since we continually mention square_root(W^D) or w^(D/2) as the exponential function that defines the size of the tree for all useful D.
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.