Author: J. Wesley Cleveland
Date: 10:16:52 05/16/01
Go up one level in this thread
On May 15, 2001 at 14:21:22, Uri Blass wrote: >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. > >By this logic you can get sqrt(n) for the following position > >[D]8/4b2B/k7/6n1/8/8/4K1R1/8 w - - 0 1 > >It means that programs should be able to solve it without tablebases because > n<(2^5)*(2^5)*(2^6)*(2^6)*(2^6)*(2^6)=2^34 so sqrt(n)<2^17 but I do not know >about a program that can solve it without tablebases inspite of the fact that >hash tables of 128 Mbytes are more than enough to remember 2^17 positions even >if every position is 32 bytes and positions in the endgame can be stored by less >bytes if the program is smart enough. > My estimate (guess) assumes perfect move ordering. I suspect that move ordering is pretty bad here, as evaluating positions that don't involve material loss is pretty hard.
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.