Author: Dann Corbit
Date: 10:47:49 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:34:26, Andrew Dados wrote: [snip] >Dann, would you consider tic-tac-toe problem as O(1)? Sure you would. It depends on whether you generalize it or not. The search algorithm is NOT O(1). I have not done the calculation, but I suspect that tic-tac-toe is exponential also. It just turns out that sqrt(exp(9)) is not a very big number. So for the particular problem size [3x3 board], this EXPONENTIAL algorithm is solve quicky. Now, try with 4x4 boards, 5x5, up to 1000x1000 boards and tell me what happens. Now, we will never have an infinite board. And yet, I submit that the algorithm is not O(1). >So what is your problem with similar, chess problem? With any problem. The running time of an algorithm is a function of problem size n. There is no such thing as "arbitrary input" in algorithms. All algorithms are calculated in terms of operation counts. The operation counts will scale with problem size. >(Just trying to find a simple analogy why chess problem as in 'solving chess' is >O(1). ) It isn't. >If you are talking about mini-max and n being depth of chess tree search, then >for small n cost of minimax is O(exp(n)) indeed. It will not stay O(exp(n)) for >huge n, because chess is finite problem and has finite number of states needed >to visit ion order to solve the game. > >So Ricardo is right. And you are right. Practical chess trees are of O(exp(n)) >cost for small n; it will not hold for huge n. It holds for all n that matter -- those that we can compute. FIGURING OUT WHAT WE CAN COMPUTE IS THE WHOLE 'REASON TO BE' FOR ALGORITHM ANALYSIS. Have you noticed that sort algorithms, despite fixed inputs are not considered O(1). In fact, show me *any* algorithm with a defined big-O notation and I will prove by the "silly definition" that it is O(1). We need to step back. Why do we ask the question: "What is the big-O performance of this algorithm?" It is for one reason only -- to find out what is practically computable. If we have any algorithm we will only solve for some size n. Now, n might be tens or hundreds or billions or trillions. We spend hours and hours finding out what big-O performance is for the sole reason that we want to know what is possible. Now, if we accept the "fininte inputs means O(1)" definition, then only and idiot would argue that all problems are O(1). If all problems are O(1), then everything is computable. But something is wrong with that picture. Divorce the algorithm from the data. Count the fundamental operations. Describe these as a function. That's what big-O notation boils down to. And if O(f(n)) finds f() to be an exponential function, then we must keep n small or it is of little use to try and solve it (worst case). There is no other value to O(f(n)) calculation. The definition put forth by some that "fininte inputs means O(1)" is useless.
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.