Author: Robert Hyatt
Date: 11:01:46 05/14/01
Go up one level in this thread
On May 13, 2001 at 19:19:11, Jesper Antonsson wrote:
>On May 11, 2001 at 17:28:33, Dann Corbit wrote:
>
>>Of course, everyone agrees by now.
>>
>>Chess is O(1), because if you get a big enough constant (nobody knows what it
>>is) then it will be big enough to outweigh the time to run the program. That's
>>because the board is finite and the pieces are finite and the number of plies is
>>finite (at some point, but at least 5948*2 as a bare minimum). So, with all
>>those finite inputs, the algorithm will eventually terminate. Just wait until
>>it does and pick that number plus 1 as your constant. Q.E.D. This camp (the
>>)(1) camp) is clearly, and unmistakeably correct.
>>
>>Chess is O(exp(n)) because by definition, O(1) is O(exp(n)). So there can be no
>>argument. This is by definition of the terms. Hence, the O(exp(n)) camp is
>>correct by definition, since *every* O(1) function is also an O(exp(n)) function
>>{trivially}.
>>
>>Chess behaves {from ply to ply} in an exponential progression as to time.
>>Whether this is important or not seems to depend on who you are talking to.
>>That's how I do analysis, but since there is no ISO specification for complexity
>>analysis, you can do it however you darn well please.
So long as you don't use any current literature to prove the point. :) In
_my_ references, O(n) is used to predict algorithm run time or memory space.
Nothing else. I don't see any restriction in any reference I have that says
"If the input is not unlimited, it is O(1)". I gave a specific quote in another
branch of this thread to show what I am seeing in my books on complexity.
>>
>>So. Since we all agree 100%, maybe it's time to just forget the whole thing.
>
>Wise words. :-) Agreed.
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.