Author: Jeremiah Penery
Date: 17:53:49 05/15/01
Go up one level in this thread
On May 15, 2001 at 18:11:57, Jesper Antonsson wrote: >On May 15, 2001 at 11:53:32, David Rasmussen wrote: > >>On May 15, 2001 at 06:40:58, Martin Schubert wrote: >> >>> >>>O-Notation is never about one specific problem, it's about one "family" of >>>problems. If you want to look at the asymptotical behaviour of chess, you need >>>an input n, for example the size of the board. Other things don't make sense. >>>You can't say, something is O(1) because of something is bounded. First you have >>>to define what your "n" is, and then look at the asymptotical behaviour. >>>It doesn't matter for example, if you play chess only on a 8x8-board. The >>>question is "what would happen if you played on a nxn-board?". >>> >>>Martin >> >>Exactly. > >Most of us are talking about chess and "n" as "target search depth". With the current tree-searching algorithms, do you not agree that depth N+1 takes exponentially longer than depth N? (Ignore the fact that N has a maximum bound - that is completely irrelevant, and has nothing to do with complexity analysis.) I grant that _maybe_ it's possible for an algorithm to be constructed that reduces chess to something less than O(exp(n)), but still not O(1). O(1) implies that the algorithm is solved in _constant_ time, REGARDLESS OF N. If you're using ply depth as N, I really don't see how you can conclude O(1). It's clearly seen that for all reachable N (reachable within the potential life of the universe, perhaps), the behavior is O(exp(n)).
This page took 0.01 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.