Author: Dann Corbit
Date: 13:33:05 05/09/01
Go up one level in this thread
On May 09, 2001 at 16:17:37, Paul wrote: >Dann, maybe I'm dimm, but doesn't the whole discussion arise out of a different >definition of n? > >In the TSP, n = the number of cities, right? n is variable, and then later used >to give an O(...) estimate of the algorithm depending on that n. > >In chess you can choose different definitions of n: > >1. n = the number of possible (legal) positions, > this means n = constant, there is no variable n in this case, so any > algorithm is of order O(#positions) = O(1). > >2. n = plydepth, this is variable, so you can talk about algorithms (like > alpha-beta) being exponential in n. > >To me this is all there is to it? In both cases it is the same. For any algorithm (e.g. TSP, calculate a chess tree) you have a finite input. For TSP it is a subset of the cities on planet earth. For chess it is a subset of the board positions that are possible. You cannot assume ideal play either, because your opponent might be a bozo. ;-) Anyway using the definition that limited input means O(1) means that all algorithms are O(1). In fact, if it is an algorithm, it must be O(1) because it terminates. Hence, the number of steps to complete is a constant. By definition! ;-) Look at my sorting example. Has anyone refuted it? It is and identical transformation of the chess problem and much simpler. In fact, size_t things probably CAN be sorted, whereas the solution tree to chess cannot be computed. Just the same, the sort routines are not O(1) and chess is not O(1). That[1] algorithm complexity definition has no value whatsoever. [1] "Finite input means O(1)"
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.