Author: José Carlos
Date: 06:02:57 05/10/01
Go up one level in this thread
On May 09, 2001 at 20:39:50, Dann Corbit wrote: >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. 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. José C.
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.