Author: Robert Hyatt
Date: 19:03:19 05/15/01
Go up one level in this thread
On May 15, 2001 at 18:10:30, Jesper Antonsson wrote:
>On May 15, 2001 at 13:06:09, Robert Hyatt wrote:
>
>>On May 15, 2001 at 06:40:58, Martin Schubert wrote:
>>
>>>On May 14, 2001 at 15:51:29, Robert Hyatt wrote:
>>>
>>>>On May 14, 2001 at 15:05:27, Uri Blass wrote:
>>>>
>>>>>On May 14, 2001 at 13:58:50, Robert Hyatt wrote:
>>>>>
>>>>><snipped>
>>>>>>As far as the "mythical" requirement that N be unbounded, I give this explicit
>>>>>>definition of Big-oh:
>>>>>>
>>>>>>"We say a function g(n) is O(f(n)) for another f(n) if there exist constants
>>>>>>c and N such that for all n>=N, we have g(n) <= cf(n).
>>>>>>
>>>>>>I don't see any _requirement_ that n or N be unbounded.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>If n is bounded and gets only a finite number of values then it is clear that
>>>>>always g(n) is O(1) by this definition
>>>>>
>>>>>In this case g(n) can get only a finite number of values and
>>>>>you can define c=max({g(n)}
>>>>>You get g(n)<=c for all n>=1 and it means by definition that g(n)=O(1).
>>>>>
>>>>>Uri
>>>>
>>>>That is simply an interpretation. As I said, give me a citation that _requires_
>>>>that N be unbounded. Since no _real_ algorithm can have unbounded input. The
>>>>traveling salesman problem is one example. If we define a city as the space
>>>>occupied by 1 atom, which is the smallest "city" of interest, then that is
>>>>O(1), yet it is not given as O(1) in any book I have...
>>>>
>>>>Since by definition _all_ algorithms have finite input to be useful, they are
>>>>all O(1) by this perverted definition. Perhaps math people define this
>>>>differently, but in computational science, we don't consider _all_ algorithms
>>>>to be O(1) as that definition is useless in the extreme.
>>>
>>>O-Notation is never about one specific problem, it's about one "family" of
>>>problems. If you want to look at the asymptotical behaviour of chess, you need
>>>an input n, for example the size of the board. Other things don't make sense.
>>>You can't say, something is O(1) because of something is bounded. First you have
>>>to define what your "n" is, and then look at the asymptotical behaviour.
>>>It doesn't matter for example, if you play chess only on a 8x8-board. The
>>>question is "what would happen if you played on a nxn-board?".
>>>
>>>Martin
>>
>>I'm not interested in NxN. Even though that is a completely bounded game,
>>since there is a very definite maximum for N due to the size of the universe.
>>And we are back to where we started. I am not aware of _any_ problem that is
>>truly unbounded. Which means we don't need any theory work at all, we just
>>say O(1) and go to the next problem, which ought to be easy to solve at O(1)
>>complexity.
>>
>>All I care about is that in 8x8 chess, for each additional ply of depth I try
>>to do, I get an exponential increase in the work required to do the search.
>>For all depth N that are doable in the universe I live within.
>
>Does the big O definition say anything about what's doable in your universe?
Nope. In fact the definition I posted right from a well-known theory book
yesterday did not require that the input be unbounded. But for real-world
problems, +yes+ they have to run in our universe, as that is the only one
we have access to.
>
>>So I will continue to say that N+1 is hard, while some will say it is O(1).
>>I'm waiting to see their algorithm however, that will search to depth=20 and
>>depth=21 in the same amount of time.
>
>Not 20->21, but perhaps 200-201, and certainly with 6000->6001. And this
>algorithm can be constructed, you know that and I know that. That it hasn't been
>done isn't relevant.
6000 is not enough, using the 50-move rule. You need over 10,000 plies before
you run out of pawn pushes or captures. And that tree will never be searched,
period. 38^10000 is big enough that it could be considered infinite with no
loss of accuracy since nobody can count to that number using any speed of
processor and amount of time you want to name. IE one trillion years is only
5 x 10^23 nanoseconds. I don't think the universe is expected to last that
long. counting once per nanosecond, you have barely started by the time the
universe ends. you have reached 10^23. You are counting to 10^10000. Is
that close enough to infinity to be happy?
Saying that eventually chess becomes O(1) is therefore simply nonsense. Unless
you can tell me _exactly_ when it will become O(1). From my vantage point, it
will _never_ happen.
Assume machines get 2x faster a year. When do we get a machine that can count
to that ridiculous number? IE what is log2(38^10000)??? I claim it is so big
no human will ever see chess turn into O(1).
Which means it will stay at O(W^(D/2))
This page took 0.02 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.