Author: Robert Hyatt
Date: 17:38:06 05/09/01
Go up one level in this thread
On May 09, 2001 at 19:31:32, Ricardo Gibert wrote: >On May 09, 2001 at 19:27:07, Dann Corbit wrote: > >>On May 09, 2001 at 19:23:45, Ricardo Gibert wrote: >>>On May 09, 2001 at 18:16:48, Dann Corbit wrote: >>>>Some people are insisting that finite inputs mean O(1). >>>> >>>>My insistence is that the big-O behavior should model the difference from n to >>>>n+1 and from n to n-1 (past some point n0). >>> >>>Definition: f(n) = O(g(n)) (read as "f of n equals big oh of g of n") iff there >>>exists two positive constants c and n_0 sth |f(n)| <= c*|g(n)| for all n >= n_0. >>> >>>I see nothing in the above definition that talks about "n to n+1 and from n to >>>n-1". >>> >>>I do see that n is unbounded. I also note that in chess, n *is* bounded unless >>>you generalize 8*8 chess to n*n chess when n is then unbounded. If you make such >>>a generalization, you can conclude that n*n chess is O(exp(n)). You can then >>>instantiate it to the 8*8 case to obtain a usable result, but please do not say >>>that 8*8 chess is O(exp(n)) rather than say n*n chess is O(exp(n)). >>>I don't see this can be made more clear. I'm really at a loss as to why you >>>cannot interpret formal definitions correctly. >> >>If someone pays you to give an algorithm analysis of chess will you really >>report that it is O(1)? > > >Yes and I will point to the access of Nalimov EGTBs as an example of such an >algorithm. I will observe that in principle 5-man EGTBs can be extended to >32-man EGTBS, though this has no practical significance. They can't be extended that far at present. They would be wrong. Because they would report mates when there are only draws due to the 50 move rule. Or repetitions. And they might say draw when a search deep enough could get around the cases where the 50 move rule would say draw. I think that it is more than a bit premature to say chess is finite. I have given an example that obviously is not, and which is also within the rules of the game. > > >> >>>> >>>>There are no real algorithms with infinite inputs. These so-called algorithms >>>>can never terminate. >>> >>>I never said anything about infinite inputs. "Unbounded" is not the same as >>>"infinite". Get the terminology straight or you will get nowhere. >> >>When analyzing algorithms, we do make assumptions about data types and ranges. >>Otherwise, the task of analysis itself is impossible.
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.