Author: Dann Corbit
Date: 11:59:15 05/16/01
Go up one level in this thread
On May 16, 2001 at 14:55:07, Dann Corbit wrote: >On May 16, 2001 at 14:35:18, Uri Blass 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. Note that 168 is not cast in stone either. It might be a >>>few bits more or less, but it is probably close. >> >>It is proved to be clearly less than 2^168. >>I believe my counting program proved that it is less than 2^160 but I have not >>the numbers near me. >>I guess it is between 2^140 and 2^150. >> >>I had an idea how to get a good estimate for it by a program but nobody tried to >>calculate an estimate for it. >> >>My idea is simply to generate a lot of random pseudo legal positions(1000000 is >>enough) and try to find the number of legal positions. >> >>In order to generate pseudo legal position you need to the following steps: >> >>1)Calculate the number of pseudo legal positions for every possible legal >>material structure >>2)generate a random pseudo legal position. >>3)check if the pseudo legal position can be achieved by a chess game. >> >>If you find that the number of pseudo legal positions is 10^47 and you also find >>that 173 out of 1000000 pseudo legal positions are legal then >>10^47*173\1000000 is a very good estimate for the number of the legal positions. >>(If you have enough pseudo legal positions that are legal you can be sure with >>95% confidence that the mistake in the estimate is less than 10%) >> >>It seems that nobody is really interested in the number of legal positions so we >>are not going to know a good estimate. > >One way to get an absoulute upper bound is by a minimum encoding. I believe >KarinsDad had an encoding that was 164 bits in length (IIRC). If true, then >there cannot possibly be more than 2^164th chess positions, and surely less than >that since some fraction won't be legal. But as an absolute upper bound, we can >say a correct encoding that enumerates all chess positions in n bits implies >with certainty that there cannot be more than 2^n possible states and hence >positions to that vector. > >If (for instance) you could somehow encode a chess position that would work for >any board position into 100 bits, that would prove that 2^100 is the largest >possible number of board positions. Weak math again. For an n-bit encoding, we could have all bits set, rendering the maximum possible count for an n-bit encoding as: count = 2^(n+1)-1
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.