Author: Dann Corbit
Date: 14:28:33 05/11/01
Go up one level in this thread
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.
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.