Author: Jeremiah Penery
Date: 02:37:46 05/17/01
Go up one level in this thread
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. They are
artificial constraints placed upon the tree size for the particular state-space
of chess.
If they _were_ part of the algorithm, then a "good" chess algorithm would simply
not search to depths > x, where x is the needed solution depth. So the input
becomes bounded - what now? O(1) again? And does this mean that any algorithm
where input is bounded is also O(1)?
>Therefore, for ("good") chess algorithms and for large N, N+1 won't take take
>longer than N.
>
>>(Ignore the fact that N has a maximum
>>bound - that is completely irrelevant, and has nothing to do with complexity
>>analysis.)
>
>This is not a fact. N is unbounded. I can input a target search depth of a
>million or whatever to a chess algorithm. It will only *search* to a much
>smaller depth, of course, but *that* is irrelevant.
I think you know what I meant. N is practically bounded by the depth of the
chess-tree in this case.
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.