Author: Dann Corbit
Date: 11:38:03 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:45:57, Ricardo Gibert wrote:
>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".
And it hides an impractically large constant in every other problem. Given
infiite time, anything is possible. We don't have infinite time, and that's why
we bother with algorithm analysis.
>>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.
If the result of such calculations is that chess is O(1), then what good is it?
>>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.
Algorithm analysis is used to find complexity of computer algorithms, and is not
a branch of pure math. Turing machines have infinite tapes, but we won't try to
sort any infinite inputs with one.
>
>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 most problems we make no assumptions at all about any sort of bounds. We
count the fundamental operations and see how the behaviour changes with
increasing n.
>In chess, the n is fixed, so strictly speaking it makes no sense to speak of its
>assymptotic behavior as n increases.
It is fixed for any real problem that is to be solved.
>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.
Indeed. Chess is an instance of the algorithm. If you plug in an 'n' you can
calculate about how long it will take the machine to grind to a halt, worst
case.
>
>>
>>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.
I am saying that if chess were O(1) {which it isn't} then it would be O(exp(n))
because every process that is O(1) is also O(exp(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.