Author: Andrew Dados
Date: 12:02:21 05/09/01
Go up one level in this thread
On May 09, 2001 at 14:17:33, Dann Corbit wrote:
>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.
Not exponentially. You'll see less positions with 32 pieces then with 31.
Don't tell me 32 is too big number to estimate limiting bounds.
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).
You can not store all natural numbers, neither you can compute all n!. In
contrast number of chess positions, while it may seem huge for us now, is
bounded and they all can be stored.
You are right that today, for all practical purpose, complexity of mini-max
applied to chess is equal to mini-max applied to stock market and equals
O(exp(n)). However asymptotic behaviour for large n (large means > 100 for me :)
will not be of order O(exp(n)).
And no matter how slow (or fast) we are computing today, we need to distinguish
between practical cost now and theoretical asymptotic cost.
Since one day we will reach O(1000)=O(1001) and then our cost will be O(1) :)
-Andrew-
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.