Author: Robert Hyatt
Date: 17:48:06 05/09/01
Go up one level in this thread
On May 09, 2001 at 20:29:49, Vincent Vega 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. >> > >Lowest estimates of the number of atoms in the Universe are about 10^30 times >larger than the estimates of the number of tablebase entries needed to play >perfect chess from the starting position. This doesn't even take into account >the fact that only a very small fraction of these positions have a chance of >occurring in a game played perfectly by one side and that compressing them is >quite possible. So please stop perpetuating this "Universe" nonsense. I know what the estimates for atoms in the universe is. Would you please cite a reasonable source that puts the number of chess positions 30 orders below that estimate? The tablebase idea doesn't work. What do you do for tablebase positions that have 0.0 for the evaluation? How far do you search before you conclude that a position can't be won? I happen to believe that the 32-man tablebases could not be computed even _if_ there was enough storage to hold them, something I also don't believe is possible. We are now off to a question of "decidability" if you are familiar with that. The question is "is it decidable whether chess is finite or not?" The answer is that if a forced mate is found that doesn't violate the 50 move rule, then it is decidable that it is finite. If a forced mate is found that does violate the 50-move rule then that search line is no good as the other side would instead choose a draw. If all such lines are refuted, the question is still decidable. But if the game is drawn from the beginning, it is not a decidable question. Because we can _both_ keep playing, trying to win, and until one of us does, the game can continue. and continue... and we can't decide whether it is finite or not... I personally consider the entire discussion not important. The tree search is absolutely of complexity O(W^D) today. It will be so next year. It will be so when the universe is twice as old as it is today. That is long enough for me.
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.