Author: Ricardo Gibert
Date: 10:45:57 05/09/01
Go up one level in this thread
On May 09, 2001 at 12:39:23, Dann Corbit wrote:
>On May 09, 2001 at 10:48:15, Ricardo Gibert wrote:
>[snip]
>>>hope you are right also. Of course, the discovery of such an algorithm will
>>>*still* mean that chess is O(exp(n)), for those that know what the term means.
>>>-- wink, wink.
>>
>>But in chess, n is constant. Chess is O(1). If O(exp(n)) were correct, then
>>there would not exist a constant c sth exp(n) = c*(1). Clearly such a constant
>>exists, so you are mistaken. If the size of the chessboard were not limited to
>>8x8, then O(exp(n)) would make sense.
>
>Of course, if such an analysis were correct then you would be agreeing with me,
>because O(1) is a microscopic subset of O(exp(n)).
>
>On the other hand, O(1) is easily computable. What's the answer, then?
O(1) hides an impractically large constant in chess. However, I'll make you a
deal. If you make me immortal and indefinitely extend the existance and extent
of the universe, I promise I will provide "the answer".
>
>All of algorithm analysis would be completely useless using this sort of vacuous
>reasoning.
On the contrary, when n is unbounded or assumed to be unbounded, it is quite
useful.
>
>Will you really sort with an arbitrary number of inputs? Can you cram in more
>than an unsigned 64 bit integer of elements? (or 256 bit integer or one
>trillion bit integer)... If not, then it's BOUNDED and (by golly) O(1) {by the
>'if it is bounded it must be O(1) school of thought'}.
In practice, there is always a bound. This is why computers cannot truly model a
turing machine for instance. A turing machine has an infinite store and a
computer does not, but this does not mean it is not a useful model. You must
make the appropriate assumptions.
In most problems we assume no bound and we can then make useful conclusions. It
is reasonable to make such an assumption, since the upper bound is indefinite.
In other words, we can always build a more powerful computer that will increase
the size of the problem we can solve.
In chess, the n is fixed, so strictly speaking it makes no sense to speak of its
assymptotic behavior as n increases.
In regards to mini-max, that is a general purpose algorithm that is not limited
to chess. There we have no bound, so it *does* make sense to speak of
assymptotic behavior as n increases.
>
>I really can't believe so many smart people don't understand it.
I know the feeling.
It must be the
>educational systems, because there are reams of folks who seem to think this
>way.
>
>Even if you disagree with me, then you agree with me. If a problem is O(1) then
>BY DEFINITION it is O(exp(n)). Hence, you can only agree.
I'm not following what you are trying to say with the above.
But knowing a lid is
>only important if that lid makes the problem practically computable. With
>chess, if we ground the earth into powder for storage and computed until the sun
>went out for time we would not even be approaching the answer. If you call that
>O(1), I don't want you designing any algorithms for me.
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.