Author: Robert Hyatt
Date: 19:54:25 05/09/01
Go up one level in this thread
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 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.