Author: Uri Blass
Date: 02:57:03 05/09/01
Go up one level in this thread
On May 09, 2001 at 05:42:08, Jeremiah Penery wrote: >On May 09, 2001 at 03:39:42, Uri Blass wrote: > >>On May 09, 2001 at 01:11:50, Dann Corbit wrote: >> >>>On May 09, 2001 at 00:41:38, Uri Blass wrote: >>>[snip] >>>>No >>>>Chess is clearly polynomial and even O(1) like every solvable problem that is a >>>>practical problem. >>>> >>>>You need constant time to solve chess when the problem is only that the constant >>>>is large. >>>> >>>>The only problems that are exponential are problems when the size of the input >>>>has no finite upper bound. >>>>You can see the input of every practical problem in the world as something that >>>>has an upper bound so saying that an algorithm is not O(1) has only mathematical >>>>meaning and not practical meaning. >>> >>>Unbelievable that you also do not understand Big-O notation. >> >>I responded to the sentence of Hyatt: >>"In the case of chess it is clearly exponential, which is _not_ any form of a >>polynomial." >> >>I did not say that O(1) is not also O(exp(n)). >>I understand from the sentence of Hyatt that chess is not O(1) and even not >>O(n^500000) > >If I understand this correctly, a minimax search of the chess tree should be >something like O(36^n), where n is the search depth. Of course for most >programs of today, perhaps this can be reduced to O(3^n) or so by introducing >the errors of selective search. I think that even with minimax it is better if you use hash tables and save searching the same position twice. > >I've had very little work with big-O notation, but I did read a couple of the >links given by Dann. Someone please correct me if the above is wrong. :) > >><snipped> >>>I suggest that you read my other posts on the topic. >>> >>>Anyone who says that an O(1) process is not O(exp(n)) does not know what the >>>notation means!!! >>> >>>Anyway, you can say what O(f(n)) is by looking only at the algorithms not the >>>data. Do you really understand this!? >> >>I understand what you mean but >>Every algorithm when there is a bound on the size of the data is practically >>O(1) because exp(constant) is another constant. >> >>Algorithms to solve problem like sort can be described theoretically >>as not O(1) because there is not a finite upper bound for the number of elemnts >>by definition. > >Yes, theoretically you can give infinite elements, but that's really a pointless >exercise. An infinite number of elements in any algorithm should take infinite >time - that's what makes it infinite. If you divide infinity by 1000000000, >it's still infinity. > >You can theoretically give an infinite-size tree to a tree-searching algorithm >too - like the algorithms in chess programs... So tree-search algorithms aren't >O(1) (by your definition!), yet chess algorithms are? > >>For practical purposes you can say that there is a finite upper bound so you can >>say that Solving the practical problems can be done in O(1) when the only >>problem is the constant. >> >>Algorithms to solve problem like chess,go or other games can be described as >>O(1). > >I think that's sort of like wiggling through a loophole in the notation. The >constant term would be so huge it may as well be infinity, for practical >purposes. I agree that it is not relevant for practical purposes. It's very possible that to solve chess you'd need more material than >exists in the universe just to store the information, so again it's a pointless >argument. You need less than it but it is not practical for the near future. For Storing all the legal positions you need less than 10^50 bytes. 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.