Author: Dann Corbit
Date: 10:01:58 05/10/01
Go up one level in this thread
On May 10, 2001 at 09:02:57, José Carlos wrote: [snip] > I've read this thread quite a bit late, so I probably have missed some posts >somewhere else in the page, but I'll give my opinion (sorry if it's been already >discussed somewhere else): > > Complexity, AFAIK, don't apply to _problems_, but to _algorithms_. So, >different algorithms for solving chess have different complexities. A table >lookup algorithm for solving chess (if such a thing is possible) is O(1). >AlfaBeta with PVS is O(exp(n)), being n the depth. > I don't see how this can be so confusing. Having had a day to soak my head, I have thought it over. Now, there are clearly two schools of thought here. And having given the actual arguments careful consideration, I can see that (in fact) the "other camp" has not made incorrect assertions. In fact, using their line of reasoning, chess is O(1). I find this particular form of definition overly pedantic and useless, but it is -- nevertheless -- entirely correct. My definition is far more useful to me, because I can use it to make money. So I guess I'm really just a mercenary. In short, my definition is superior technologically, and their definition is superior mathematically. So (I suppose) it depends on what you want to do with the answers you get which method you should choose. The way I have always done this sort of thing was just sit down with the algorithm, study what it does, and calculate operations based on scale. Then you know exactly how the algorithm behaves for any input size (worst case only -- I stink at average case analysis). Anyway, I have already apologized to the group -- for indeed, I was wrong. I think there is nothing more to be gained by trying to force my views on anyone. In fact, I am quite sure that I know the chief reason for my strange ire of yesterday. It is my irritation at my own poor communication skills.
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.