Author: Ricardo Gibert
Date: 14:10:44 05/09/01
Go up one level in this thread
On May 09, 2001 at 15:11:41, Eugene Nalimov wrote: >Ok, here is simple example: let's consider sorting but limit the input by (a) >limiting # of digits in each number (e.g. 1024 bits), and (b) limiting # of >elements in the sequence we want to sort (e.g. max 10**40 elements). Yes, >theoretical # of operations that are necessary to sort such a sequence is >limited. But, nevertheless, you still can say that Of course you can by generalizing the problem. You assume n is unbounded and proceed, which you do very nicely (implicitly). >* insertion sort is O(N*N), >* quick sort is O(N*ln(N)) on average, but O(N*N) in the worst case, >* heap sort is O(N*ln(N)) in the worst case. If you *define your problem* in such a way that n is some *bounded* value (as it is in chess), then the above is not correct. if n is bounded, then I can write a sort routine containing a finite number of steps that is O(1). It won't contain any loops and consist of a series of if-then statements and swaps and that's it. That is clearly O(1). The routine will always execute *within* the same amount of time. If I generalize the problem for any finite n, then the O(1) routine won't work. An array that is larger than the arrays for which it was intended for will break it. I must then use loops to write a procedure and I wind up with something that is O(n*n) (or whatever) in running time. >So I don't see why the fact that something is finite changes something in the >complexity tree search. > Again you mean bounded. It depends on how you define the problem. If the sort problem is bounded in terms of the number of elements and the size of the elements, then the running time is O(1). If the problem is unbounded or you generalize the problem so that is unbounded, it's something else. In computer science, it generally assumed that that a specific problem is to be generalzed so that n is unbounded. This assumption does not apply to chess, since we are only really interested in playing chess on an 8x8 board. People frequently confuse bounded and unbounded with finite and infinite, respectively. To see more clearly that they are not the same, consider: (1) The set of *positive* integers. The number elements in the set is not finite, but the set *is* bounded. It has a lower bound of 1 and no upper bound. (2) A set of integers can be unbounded, but finite. Any set of n integers fits this, since n is uninstantiated. (3) A set real of numbers can have both an upper bound *and* a lower bounded and still contain an infinite number of elements e.g. [0,1]. The definition of big-O limits itself to where n is unbounded. To use the definition, n must be unbounded or at least assumed to be. We can make use of big-O by instantiating n, but this should not be confused with n being a constant to begin with. In chess, n is constant to begin with. If we discuss minimax (which does not limit itself to chess), n is unbounded and we can apply the definition to big-O and conclude a running time that is NP. We can then instantiate its use to chess and come up with something useful. Alternatively, we can talk about tablebases (again this is does not limit itself to chess) and we can conclude that accessing a TB is O(1). We can instantiate its use to chess and of course it remains O(1). We can also conclude that the construction of a TB is NP. In short, chess is O(1). TB access is O(1). TB generation NP. Minimax is NP. If you still don't think it is significant that chess is bounded, consider how far you would get with EGTBs if chess were not limited to using 8x8 boards. Chess playing programs would start by asking what size board do you want to use and you would be sunk, since EGTBs must be pre-calculated and you can't contemplate generating EGTBs on the fly, since that is NP. You hit the same roadblock that I would with my O(1) sort routine. The fact that chess is O(1) is what makes Nalimov EGTBs possible. > >On May 09, 2001 at 14:53:19, Ricardo Gibert wrote: > >>On May 09, 2001 at 14:30:36, Eugene Nalimov wrote: >> >>>Input in our case is (position, depth), and the question is "how longer will >>>take to evaluate (position, depth+1)"? >>> >>>Eugene >> >> >>The time it takes to return an evalutation in both cases is bounded by a >>constant, since the time it takes to solve chess is bounded by a constant (quite >>huge of course). >> >>If the size of the chessboard were a finite, but unbounded value. I would agree >>with you. In that case, no such constant exists. In actuality, chess is >>restricted to an 8x8 board. >> >>In all the definitions for big-O notation I have seen, it is assumed that n is >>unbounded for O(f(n)). This is not the case for chess. >> >>Accessing your Nalimov TBs are good example of an algorithm that is O(1). In >>theory, there is no reason why you can't construct 32 piece EGTBs. In practice, >>it is a different story. >> >> >>> >>>On May 09, 2001 at 14:11:25, Ricardo Gibert wrote: >>> >>>>On May 09, 2001 at 14:08:10, Ricardo Gibert wrote: >>>> >>>>>On May 09, 2001 at 14:04:55, Eugene Nalimov wrote: >>>>> >>>>>>Uri, there is branch of the mathematics (not even computer science, just >>>>>>ordinary mathematics) that studies the complexity of algorithms. Algorithms were >>>>>>used in mathematics long before computers appeared, for example GCD algorithm >>>>>>was known to the classic greeks. >>>>>> >>>>>>*Very* rude explanation of big-O notation is: you have the algorithm that >>>>>>require M operations (or steps, or machine instructions, or clock cycles, etc.) >>>>>>when input in N elements long. You are increasing length of the input; how much >>>>>>operations will be necessary now? That has *nothing* to do with the fact that >>>>>>majority of practically used algorithms will terminate in finite number of steps >>>>>>when input is finite. >>>>>> >>>>>>Eugene >>>>> >>>>> >>>> >>>> >>>>But [in chess] the the length of the input does not increase and that's the >>>>whole point. >>>> >>>> >>>>> >>>>> >>>>>> >>>>>>On May 09, 2001 at 13:37:58, Uri Blass wrote: >>>>>> >>>>>>>On May 09, 2001 at 13:23:25, Dann Corbit wrote: >>>>>>> >>>>>>>>On May 09, 2001 at 13:18:52, Uri Blass wrote: >>>>>>>> >>>>>>>>>On May 09, 2001 at 11:27:46, Dann Corbit wrote: >>>>>>>>> >>>>>>>>>>On May 09, 2001 at 10:12:30, Ricardo Gibert wrote: >>>>>>>>>> >>>>>>>>>>>On May 09, 2001 at 02:00:25, Dann Corbit wrote: >>>>>>>>>>> >>>>>>>>>>>>For those of you who don't want to perform your own web search, just choose one >>>>>>>>>>>>of these: >>>>>>>>>>>> >>>>>>>>>>>>http://hissa.nist.gov/dads/HTML/bigOnotation.html >>>>>>>>>>>>http://bio5495.wustl.edu/textbook-html/node15.html >>>>>>>>>>>>http://umastr.math.umass.edu/~holden/Math136-99_projects/Amstutz-OBoyle-Petravage/big-o.html >>>>>>>>>>>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html >>>>>>>>>>>>http://classes.monterey.edu/CST/CST338-01/world/BigO.html >>>>>>>>>>>>http://shalim.csustan.edu/~john/Classes/CS3100_DataStructures/Previous_Semesters/1999_04_Fall/Examples/big-O >>>>>>>>>>>> >>>>>>>>>>>>CS:201, FCOL! >>>>>>>>>>> >>>>>>>>>>>Big-O notation is used to describe asymtotic behavior. It commonly used to >>>>>>>>>>>describe the "running time" of an algorithm. If an algorithm is O(f(n)), n is >>>>>>>>>>>understood to be a finite, but *unbounded*. (For some reason, "unbounded" gets >>>>>>>>>>>confused with infinity. This is an error, but let's not get into that. It isn't >>>>>>>>>>>relevant here) >>>>>>>>>>> >>>>>>>>>>>In chess, n in is bounded. This is a critical distinction, that means chess is >>>>>>>>>>>*not* NP. >>>>>>>>>> >>>>>>>>>>GREAT! Then it's computable. What's the answer, win-loss-draw? >>>>>>>>>>;-) >>>>>>>>> >>>>>>>>>I see no point in continuing to argue. >>>>>>>>>The question is simply question of definition. >>>>>>>>>I did not say that it is easy to solve. >>>>>>>>> >>>>>>>>>I use the definition of NP only for problems with n that is not bounded >>>>>>>>>otherwise the mathematical definition say that it is O(1)(there is a constant >>>>>>>>>and the only problem is that it is too large) >>>>>>>>> >>>>>>>>>I can agree that chess is practically O(exp(n)) and not polynomial for practical >>>>>>>>>purposes but it does not change the fact that by mathematical definition it is >>>>>>>>>O(1). >>>>>>>> >>>>>>>>This is simply wrong. I guess we are at an impasse. >>>>>>>> >>>>>>>>>You can say that Sorting is also O(1) from theoretical point of view if you look >>>>>>>>>at sorting that is done by a computer. >>>>>>>> >>>>>>>>Show me any algorithms book that says any sorting algorithm is O(1). >>>>>>> >>>>>>>The sorting from theoretical point of view is not O(1) because the size of the >>>>>>>input is not bounded. >>>>>>>Sorting done by a computer has bounded size and every problem of bounded size is >>>>>>>O(1) by the definition that I know. >>>>>>> >>>>>>>A problem can be O(n) only if n is not bounded by a finite bound by the >>>>>>>definition that I use. >>>>>>> >>>>>>>I look at sorting from mathematical point of view and not from computer point of >>>>>>>view and this is the reason that I said that it is not O(1). >>>>>>> >>>>>>>Uri
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.