Author: Robert Hyatt
Date: 11:02:42 05/10/01
Go up one level in this thread
On May 10, 2001 at 13:18:24, J. Wesley Cleveland wrote: >On May 09, 2001 at 22:54:25, Robert Hyatt wrote: > >>On May 09, 2001 at 21:27:15, J. Wesley Cleveland wrote: >> >>>On May 09, 2001 at 14:27:03, Dann Corbit wrote: >>> >>>>On May 09, 2001 at 13:33:21, Uri Blass wrote: >>>>[snip] >>>>>>Suppose we find there is a forced mate in 150000 plies? And none sooner? >>>>> >>>>> >>>>>In this case the loser can ask for a draw during the game because of the 50 move >>>>>rule so the mate is not relevant for deciding that the position is drawn. >>>>> >>>>> >>>>>>Can you prove there isn't? >>>>> >>>>>I can prove for a bigger constant that there is not. >>>>>The shortest mate is of less than 10^100 plies because every game of 10^100 >>>>>plies include repetitions and if there is a mate there is a shorter mate with no >>>>>repetitions. >>> >>>> >>>>It does not matter if the limit in plies is 5000 or 150000 because chess is >>>>exponential. Neither of those will ever be computable. That's the whole reason >>>>we bother to find out. >>>> >>>>Let's simplify. We ask this question: >>>> >>>>Given some depth in plies n of my search, what happens to the time when I search >>>>n+1 plies? >>>> >>>>The only thing that can solve this problem is an infinitely fast computer. >>>> >>>>An internet of millions of petaflop computers will never solve it. >>>> >>>>If that is what O(1) means, then tell me what value that definition is. >>> >>>If we have enough memory to represent every possible position, we can use the >>>endgame tablebase algorithm, which is O(n), where n is the maximum number of >>>plies (and O is about 10^50). >> >>So we go to hell in space complexity, to improve time complexity? If I can't >>search the tree within the expected lifetime of the universe, then I certainly >>can't store it in the universe. Neither approach leads me to a warm fuzzy >>feeling that chess is O(1) in time. much less O(1) in space if you assume >>transposition tables and tablebase type storage. > >This is nowhere near the size of the universe. If the mass of the earth were >converted into pure silicon, there would be almost exactly 10^50 atoms of >silicon. Actually, using an alpha-beta search with transposition tables, we >should only need to search O(10^25) nodes = sqrt(10^50). The number I have seen repeatedly is roughly 10^60 as the number of atoms in the known universe. I don't claim it is right as I didn't calculate the number. But it has been used for years.
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.