Author: Dann Corbit
Date: 15:12:53 12/10/02
Go up one level in this thread
On December 10, 2002 at 17:55:51, Dann Corbit wrote: >On December 10, 2002 at 17:51:40, Ingo Lindam wrote: > >>On December 10, 2002 at 17:30:47, Dann Corbit wrote: >> >>>On December 10, 2002 at 13:42:36, Bernardo Wesler wrote: >>>[snip] >>>>THE ALGORITHM. A MATHEMATICAL FORMULA THAT , FOR EXAMPLE, ASSURE YOU THAT IF YOU >>>>DO THE FIRST MOVE YOU ALWAYS WIN. >>>>I MEAN TO THINK ABOUT DISCOVERING A CHESS ALGORITHM IS AN UTHOPY? >>> >>>Provably impossible on current hardware and software systems. >>>Maybe in 100 years the game will be formally solved. Not in the near futre. >> >>provably impossible on current hardware...? >>are you sure? > >Absolutely sure. > >To solve chess you must store at least the square root of nodes of the solution >tree. Considering the half move clock and castle rights, it easily exhausts any >possibility of solution. > >>without assuming anything about the kind of solution? > >No assumptions are necessary. We pick an adversary in the tree. It's just like >how you would prove a sort works in O(f(n)). > >>atleast you are assuming the use of hardware... >>(an assumtion I could live with because I wouldn't bet on find the solution >>faster by using just a pencil and a sheet of paper :-)) > >I am assuming that if you turned the universe into silicon chips and devoted >half of them to CPU's and the other half to memory storage that all the stars >will go out before you find the answer. > >>me would like to see the proof for 'provably impossible' as much as I would like >>to see the solution for chess 10^48 formations * 100 states for half-move clock * 4 bits for castle state. sqrt(1.5e+51) = 38729833462074168851792654 [64 moles of positions ;-)] Assume that you can access one position in one nanosecond -- better yet, we will assume that we can correctly compute the value in one nanosecond, access the relevant parts and save the result in one nanosecond. We will assume that our algorithm is totally optimal and move ordering is perfect so that we can achieve the square root of the tree factor. It would take 38729833462074169 seconds to fill the tree. That is 448261961366 days and 1,228,114,962 years. This is an incredibly conservative estimate. It would probably take at least one thousand times that long.
This page took 0.02 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.