Author: Dann Corbit
Date: 17:39:50 05/09/01
Go up one level in this thread
On May 09, 2001 at 20:28:29, Peter McKenzie wrote: >On May 09, 2001 at 20:05:24, Dann Corbit wrote: > >>On May 09, 2001 at 20:00:09, Peter McKenzie wrote: >> >>>On May 09, 2001 at 19:34:08, Dann Corbit wrote: >>> >>>>On May 09, 2001 at 19:31:32, Ricardo Gibert wrote: >>>>[snip] >>>>>>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. >>>> >>>>This is an incompetent assessment. 32 man EGTB's cannot even conceivably be >>>>attempted if half the universe were turned into computers and the other half >>>>computed madly until the power went out. >>> >>>Dan, it seems to me that Ricardo is presenting a logical argument here. I don't >>>think the argument is refuted by you calling it incompetent! >>> >>>Similarly, I don't see why the practical difficulties of constructing 32 man >>>EGTBs should detract from their theoretical existance. >> >>Because if you can't make one, it won't ever exist. > >I don't think that matters in this context. Two points: > >1) Just because we can't make one now doesn't mean we will never be able to make >one. For 32 EGTBs, we may discover for example some incredible compression >scheme that will allow them to be built with the state of the art technology in >20 years time. > >2) In any case, we were talking about 'theory' weren't we? Who cares if we can >built it or not. It is more of a thought experiment. > >> >>Sort of like powering a rocket to the moon with a spoonful of baking soda and a >>tablespoon of vinegar. "You can't get there from here." >> >>"Why should we let reality get in the way of a perfectly good discussion?" >>He asked himself aloud. >> >>Let me ask you (Peter) as someone who seems very sensible and 'detached from the >>heat of the battle' -- >> >>Do you consider an algorithm like Alpha-Beta with PV search for the game of >>chess to be exponential or O(1) or something else? Why do you so answer? > >I would consider THIS ALGORITHM to be O(exp(n)) where n is search depth between >1 and MAX_N, where MAX_N is some large N (deepest node required to solve chess >by search). > >But I would consider the game of chess to have a theoretical complexity of O(1) >since it can in theory be solved by a big lookup table. > >Sound reasonable? I will never use that definition. It isn't useful for computation. I don't think that is the way it is done in the industry. It is frightening to think that I might have an algorithm analyzed, and get an answer "It is O(1)" when it is completely intractible. It seems to me that there should be a way to clearly define this in an method that is both unambiguous and useful. "Chess is O(1)" isn't it.
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.