Author: Peter McKenzie
Date: 17:28:29 05/09/01
Go up one level in this thread
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? cheers, Peter
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.