Author: Dann Corbit
Date: 11:17:33 05/09/01
Go up one level in this thread
On May 09, 2001 at 14:10:02, Andrew Dados wrote:
[snip]
>I would rather say, that 'finite state number of a problem means O(1)'. Or 'if
>it is solvable once for all (any chess position in our case) then it's O(1).
>Because we proved there exist a formula computable without loops. We don't know
>such a formula yet, but we know it exists. For given traveling salesman problem
>we need those loops as for now.
>
>Now, set up an 8-piece position and leave it overnight for Crafty with 5 piece
>TBs. Would it stay O(exp(n))?
In storage - yes, in computation no. We have already performed the calculation.
Now, again, some will say "the storage cost is finite." and indeed it is, for
any n. But as n increases, storage needs increase exponentially. Now, in the
case of tablebase files, clearly n cannot increase forever. But it will
increase until you can't store the data. Not now, and probably not ever.
Despite all this, the storage requirements for tablebase files are exponential.
>Surely no. Most likely you'll get O(1). So already
>we catching that O(1) tail slowly :)
Again, we are trading O(exp(n)) comutational complexity for O(exp(n)) storage
complexity (which is also not a solution). I suspect that we won't ever have
the 32 piece tablebase file for the same reason that we won't ever compute chess
all the way to the end.
Trading space for time is a common solution. Consider the O(n) calculation for
n!. I can precompute a table of factorials and store them. Then my calculation
of factorials is O(1) {a simple table lookup} but my storage is O(n).
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.