Author: Jesper Antonsson
Date: 13:33:29 05/16/01
Go up one level in this thread
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.
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 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).
Sorry, it *is* O(1). Check it with the definition, and you will se that it is
so.
>O(1) implies that the algorithm is solved in _constant_ time, REGARDLESS OF N.
Yes, or rather, less than or equal to some constant time, regardless of N. That
is exactly what I'm saying.
>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)).
"Reachable" or the "life of the universe" is irrelevant. I have not seen any
O(f(n)) definition that includes anything about the life of the universe. Have
you?
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.