Author: Jesper Antonsson
Date: 13:57:37 05/16/01
Go up one level in this thread
On May 15, 2001 at 21:50:35, Robert Hyatt wrote: >On May 15, 2001 at 18:04:28, Jesper Antonsson wrote: >> >>Nonsense. This is a theory discussion and I don't give a rats ass about >>"real-world" problems. In chess, when you go above a certain depth, the time >>taken for the algorithm to complete doesn't increase. In the travelling salesman >>problem, for example, another city always increase the time taken for the >>algorithm to complete. That's why chess is O(1) and the TSP is not. > >As I said, real-world. The TSP problem is a real-world problem that is not >unbounded in size, simply because the number of cities in the world is finite >and countable. Chess may or may not be finite. The 50-move rule has not been >a part of the game forever. It is relatively recent. And within the past 20 >years it has been suspended for specific endings, and then later the suspension >was lifted. If we go back to prior-50-move-rule, the game is most certainly >infinite in any way you care to define infinite, for the real-world. There >is no way to search a tree to depth 1,000,000 for example. Not now. Not >ever. Never. Even if we know the game can be solved in that depth of >search. > >Yet the tree _still_ exhibits O(W^(D/2)) complexity for all D that I can reach >now, or that I will _ever_ be able to reach. To call this O(1) is nonsense. >Perhaps that is why theorists are somewhat useless? You are telling me that >as I increase D, the search time remains O(1), yet every time I do it, it >takes over 6X longer for the next search. One of those is wrong. I can prove >which with a simple program that I already have... > >O() does _perfectly_ at predicting the run-time of alpha/beta. For today. >For next Century. For time at the end of the universe. Each successive D >will multiply by roughly a factor of 6 the time for the previous D. And if >D happens to be limited, in some artificial way, but in a way that will never >affect the actual search, the so what? Big-Oh _still_ predicts the run-time >correctly in my model, not in the O(1) model... Therefore the O(1) model is >not only useless... it is worthless... > > > >> >>>Big-Oh is _still_ a conceptual way to predict program run-time as the input >>>is increased in some way. I posted a direct quote from one theory book >>>yesterday. I can post others that make the same statement... >> >>You also quoted a definition. Use it. > >I am. It predicts the run-time of an algorithm. I've not varied from >that definition one iota. That was not the definition. And again, you can't go around changing well known and accepted definitions because it doesn't fit your intuitive notion of what is usable or good for "prediction". You have to accept the definition and the fact that chess is O(1). If you want to express that chess have exponential behaviour in practice, then just say so, and stop misusing the theoretical/asymptotical big-O notation (and P-NP, for that matter). Actually, I see that I'm getting nowhere with you on this topic, I have just continued the discussion so other people won't get misled by you. As you are very respected, by me and others, for you expertise in the chess programming field and your helpful attitude, people may take your words for truth in areas were your knowledge are not equally excellent. But now I'm getting quite tired, perhaps your stamina exceeds mine... That doesn't mean you are right, though. :-) >O(1) doesn't predict _anything_... > > > >> >>>In "theory" this "asymptotic behavior" might make sense. In practical terms, >>>it does not, and all the complexity analysis of algorithms, for any real-world >>>algorithm you name, must be of O(1) which is nonsense to those of us that are >>>working on algorithms. >> >>Yes, I agree, that's nonsense.
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.