Author: Robert Hyatt
Date: 19:11:15 05/15/01
Go up one level in this thread
On May 15, 2001 at 12:18:43, J. Wesley Cleveland wrote: >On May 14, 2001 at 15:47:47, Robert Hyatt wrote: > >>On May 14, 2001 at 14:51:16, J. Wesley Cleveland wrote: >> >>>On May 13, 2001 at 22:42:00, Robert Hyatt wrote: >>> >>>>On May 13, 2001 at 19:48:59, J. Wesley Cleveland wrote: >>>> >>>>>On May 12, 2001 at 20:41:23, Robert Hyatt wrote: >>>>> >>>>>>On May 11, 2001 at 16:50:28, J. Wesley Cleveland wrote: >>>>>> >>>>>>>Okay. With exact results, you only need the number of plies to the next capture >>>>>>>or pawn move stored with each position to solve the 50 move rule problem. >>>>>>>Repititions are a non-problem, i.e. if from position A, you know that position B >>>>>>>is a forced win, *but* the win leads back through A, you would never choose to >>>>>>>move to B, because you would already know there is a shorter win from A. >>>>>> >>>>>> >>>>>>How would you _know_ that either of those positions were forced wins if you >>>>>>don't save _everything_ as you search? >>>>>> >>>>>You know because you have a string of positions in the hash table, each of which >>>>>is one ply closer to mate. There *can't* be a repitition, or it would be a >>>>>different string. It is just like endgame tablebases, which do not need any >>>>>history of positions. >>>> >>>> >>>>I'm not sure I follow. Endgame tables have _all_ positions available during >>>>their creation. That is how the algorithm works.. find a position that is >>>>marked as "unknown" by backtracking from a position marked as "known". Then >>>>you can mark the unknown entry as mate in one more move than the known entry. >>>>But you must have _all_ positions stored during the creation... _every_ one. >>> >>>I thought that is what we were discussing. If you have a hash table large enough >>>to store every position found in the search, then you do not need total path >>>information with each position, which means you could solve chess by considering >>>"only" about 10^25 positions. So, if Moore's law holds up, we could solve chess >>>by the end of the century, rather than by the end of the universe. >> >> >>First, how do you conclude 10^25? assuming alpha/beta and sqrt(N)? > >It is a classic alpha-beta search with a transposition table large enough to >hold *all* positions found in the search. I'm guessing at the number of >positions, but I feel that the same logic should hold, as only positions with >one side playing perfectly would be seen. I don't follow. We know that within the 50 move rule, the longest game that can be played is something over 10,000 plies. IE 50 moves, then a pawn push or capture, then 50 more, etc. Eventually you run out of pieces and it is a draw. But 38^10000 and 10^25 seem to have little in common. The alpha/beta algorithm is going to search about 38^50000 nodes to search that tree to max depth of 10,000. Another way of estimating is that somewhere along the way, someone found a way to represent a chess position (pieces only) in 168 bits. if you take that as an estimate of the total possible positions then you get 2^168 or roughly 10^165 which is a _huge_ number. If you consider that 1 trillion years is only 10^23 nanoseconds, you begin to grasp the size of that problem. The universe is not 1 trillion years old nor will it last that long either. So we have a finite amount of time to solve chess or admit it is exponential and unsolvable.
This page took 0.01 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.