Author: Jesper Antonsson
Date: 13:54:34 05/17/01
Go up one level in this thread
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.
> 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.
>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.
Quite right.
>So the input becomes bounded - what now?
No, it doesn't. You can still input larger depths. It's just like you can set a
chess programs max depth to 12 but use a position which yields mate in 6. It
will find the mate, but the input wasn't bounded to 6.
> O(1) again? And does this mean that any algorithm
>where input is bounded is also O(1)?
No.
>>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.
But you can input larger depths to the algorithm.
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.