Author: Robert Hyatt
Date: 19:30:10 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. This is the typical N for a tree search... since a tree doesn't have any "inputs" in the sense sort does. In other words, N is simply a function of W and D such that N = W ^ D. Assuming each "N" position takes the same amount of work to search (same assumption as assuming two sort elements take the same amount of time to compare) then N is a number that depends on the exponential W^D. Someone suggested N as the number of pieces on the board. That wouldn't pass any sort of scrutiny for complexity as it is more than exponentially hard to go from 2 pieces to 3, then 3 to 4, etc. > >To me this is all there is to it? > >Paul
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.