Author: Jeremiah Penery
Date: 17:47:30 05/17/01
Go up one level in this thread
On May 17, 2001 at 16:54:34, Jesper Antonsson wrote: >On May 17, 2001 at 05:37:46, Jeremiah Penery wrote: > >>I found some very nice notes on O(f(n)). >>http://theory.lcs.mit.edu/classes/6.042/spring01/handouts/l11.pdf >> >>On May 16, 2001 at 16:33:29, Jesper Antonsson wrote: >>>On May 15, 2001 at 20:53:49, Jeremiah Penery wrote: >>>>On May 15, 2001 at 18:11:57, Jesper Antonsson wrote: >>> >>>>>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? >>> >>>I'm not talking about generalized tree search algorithms, I'm talking about >>>specific chess algorithms. Chess algorithms do a tree search, but the rules of >>>chess (which are also part of the algorithm) limit the size of the tree. >> >>The rules of chess are _not_ part of the alpha-beta search algorithm. > >No, but part of the chess algorithms used in chess programs. What is a "chess algorithm"? Currently, they are alpha/beta algorithms. They are simply passed the arguments that limit the size of the tree. Your argument is like taking a sorting algorithm, but giving it a list of only 1000 numbers for input and saying "Sorting 1000 numbers is O(1)". It's not even a valid statement! You can pass the algorithm more than 1000 numbers if you want, but it simply ignores all the extra numbers and sorts the original 1000, in the same amount of time. This really does not make the sorting algorithm O(1). >> They are >>artificial constraints placed upon the tree size for the particular state-space >>of chess. > >Yes, but those constraints are a part of the algorithms. No, they're not. "Chess" as an input to the algorithm is no different than giving "list of 1000 unsorted numbers" to a sorting algorithm. They're both finite input sets which are given to an algorithm. We want to find the running time of the algorithm _in general_, not the specific time it will take for a particular N. >> O(1) again? And does this mean that any algorithm >>where input is bounded is also O(1)? > >No. Please give me an example of an algorithm with bounded input that is not 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.