Author: Robert Hyatt
Date: 13:19:25 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:08:18, Ricardo Gibert wrote: >On May 09, 2001 at 11:45:27, Robert Hyatt 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. If we were to allow the size of the chessboard to expand, then the >>>number of steps in its solution would be NP (extremely likely, but not certain!) >>> >>>The mini-max algorithm is provably NP, since in its general formulation, n is >>>unbounded, but in its application to chess n is bounded to a constant and so the >>>number of steps to execute the alogorithm is also bounded to a constant. >>> >>>In some other games, the size of the game is not bounded as it is in chess, so >>>their solution may not be bounded by a constant. In a game like Nim, where the >>>size of the game is unbounded. Despite this, there is a known method to solve it >>>that is O(1). (Actually, it dependes on how you count a "step", so O(log(n)) for >>>instance is another defensible answer). >>> >>>Chess does not qualify as NP for a semantic reason. If the size of the board is >>>not bounded to 8x8 = 64 squares, then it is not chess! >>> >>>In computer since, the use of Big-O is often used "fast and loose". For >>>instance, the running time of bubble sort is descibed as O(n^2). This is not >>>accurate. The number of steps is O(n^2), but some of the steps do not execute in >>>constant time. The time it takes to perform a memory move of or comparison of an >>>item of data depends on the size of the data element. If the keys to be sorted >>>are distinct, then the lower bound on the size of the data element is >>>proportional to log(n). There are other typical examples in other areas of >>>computer science too (e.g. algorithms dealing with matrices). >> >>In complexity theory that is _not_ an issue. The number of memory references >>has nothing to do with O(N^2). In this case, the complexity simply says that >>the solution time varies with the _square_ of the number of inputs. It doesn't >>matter whether you use a 1 bit memory word or a 128 bit memory word. >> >>And clearly for chess, the complexity varies as an exponential function of the >>search depth. >> >>As I have said repeatedly, _no_ algorithm terminates with infinite input so that >>doesn't have anything to do with complexity here at all. Nor does the number of >>"steps" required to do a single task affect it. It is all about the number of >>input values and a function that predicts running time based on that number. >> >>Otherwise we would _never_ see O(Nlog(N)) vs O(N^2) when talking about sort. >>They would be the same since we obviously can't sort an infinite number of >>items, ever. > >You're confusing "infinity" with unbounded. I'm not. > >It's silly to talk about asymptotic behavior as being a function of n when n is >constant. If n is constant, then f(n) is constant. Running time (or whatever) is >then bounded by a constant c. That's O(1). If n is unbounded (that does not mean >infinity, please), then it makes sense to speak of asymptotic behavior as being >bounded by a function of n i.e. f(n).\ D is not a constant. W^D is also not a constant, since we are varying D from 1 to N where N is a very large number. Complexity wants to know how long it takes to compute something when we change the number of input values. In this case it takes an exponential amount of time based directly on the depth D we want to search to. I have seen (a) no proof that chess is finite, since the rules of chess do _not_ make it so; (b) chess is infinite since that is hard to prove but more rational than saying it is not; (c) complexity theory doesn't apply to any algorithm even if we _do_ limit the number of inputs to some large number. The question is, if we go a ply deeper, what does it cost? And that cost is well-known and will hold for the life of the universe at least... > >In a nutshell, if n is unbounded, then we compare O(f(n)) with O(1), then it is >*not* the case that there exists a c sth f(n) = c*(1). If n is bounded, then >such a constant c does exist for f(n) = c*(1). > >Normally n is unbounded such as in the traveling salesman problem or sorting or >searching, etc. In chess, the size of the problem is bounded (fixed, constant, >etc). The size of the board is fixed, otherewise it ceases being chess. If the >size of the board were unbounded, then what you are saying would make sense, but >that is *not* the case. Please cite the FIDE rule that makes chess finite. I am not aware of one. The 50 move rule certainly does not do this, nor does the 3-fold repetition rule. A game does end on a forced mate, or stalemate of course, but those are the only terminal conditions. > >The bottom line is only a finite number of positions need to be considered to >solve chess. That number may be huge, but it is finite all the same. The time it >takes to solve chess is O(1), since there *does* exist a constant c sth the >number of steps needed to solve it is bounded by c*(1). > All I can say (and I am not going to continue arguing) is that every book I have that discusses complexity theory and tree searching says "exponential" not (1) for the complexity. _every_ book. I don't have a one that says that games like chess and checkers are O(1). Even a simple binary tree is exponential. >In the traveling salesman problem, f(n) is NP rather than P, since there does >*not* exist a constant c sth f(n) = c*P, since n is unbounded. > >It essential to understand the terms bounded, unbounded and infinity in their >proper context.
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.