Author: J. Wesley Cleveland
Date: 14:27:53 05/16/01
Go up one level in this thread
On May 16, 2001 at 16:27:16, Robert Hyatt wrote: >On May 16, 2001 at 16:07:11, Robert Hyatt wrote: > >>On May 16, 2001 at 15:10:33, J. Wesley Cleveland wrote: >> >>>On May 16, 2001 at 14:07:18, Robert Hyatt wrote: >>> >>>>On May 16, 2001 at 13:05:13, J. Wesley Cleveland wrote: >>>> >>>>>On May 15, 2001 at 22:11:15, Robert Hyatt wrote: >>>>> >>>>>>On May 15, 2001 at 12:18:43, J. Wesley Cleveland wrote: >>>>>> >>>>>[snip] >>>>> >>>>>>>>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. >>>>> >>>>>Look at it another way. The only positions that are visited by an alpha/beta >>>>>search (with perfect move ordering) are those where one side plays perfectly. >>>>>The question is what fraction of the total number of positions that is. >>>>> >>>> >>>>The precise formula is: >>>> >>>> N = W^floor(D/2) + W^ceil(D/2) for all D. floor means round down in integer >>>>math, ceil means round up. For the cases where D is even: >>>> >>>> N = 2 * W^(D/2) which is 2 * sqrt(minimax). >>>> >>>>If you assume that the total number of positions is roughly 2^168, then you >>>>get 2 * sqrt(2^168) or 2 * 2^84. Which is fairly close to the number of atoms >>>>in the universe. >>> >>>2^84 = 1.9*10^25 If these were atoms, it would be 32 moles, or about 1kg of >>>silicon. >> >> >>I discovered that I was having a small overflow problem on my calculator. It >>told me that 2^84 was roughly 10^81, which is wrong. > > >I should add, however, that if you searched at DB2's peak speed of one billion >nodes per second, and you could search non-stop for one trillion years (longer >than the expected life of the universe) you would not quite reach the 1% done >stage.... You really need to get that calculator fixed. 10^9 nps * 3.15*10^7 seconds/year *10^12 years = 3.15*10^28 nodes. But, if Moore's law holds until the end of the century, we should be able to solve chess at blitz speeds.
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.