Author: Jesper Antonsson
Date: 16:19:11 05/13/01
Go up one level in this thread
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. 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.