Author: Robert Hyatt
Date: 21:47:05 05/17/01
Go up one level in this thread
On May 17, 2001 at 05:44:03, Uri Blass wrote: >On May 17, 2001 at 05:22:39, Graham Laight 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. >>> >>>Uri >> >>If nobody is willing to to the large sample size, why not do it yourself with a >>small sample size? >> >>If I were sufficiently interested, I would: >> >>* number each piece (e.g. 1 = white pawn, 2 = black pawn etc) >> >>* number the squares on the board from 1 - 64 >> >>* select, at random, the number of pieces to put on the board > >It is not a good idea and you need to select at random the material structure >with the right probability if you want to get equal probability for every >pseudolegel position. > >> >>* for each piece, select a random number from 1 - 64 to select it's board square >> >>* if I intended to do a very small sample (e.g. 20 tries), to get a ball-park >>figure, I would set up a simple spreadsheet to to the above, and use my recalc >>key to get a new list of pieces/positions > >I guess that you may get only 0 legal positions out of 20 if you choose a random >pseudo legal position with equal probability so it is probably not enough. > >It is not important for me to investigate this problem so I do not work on it. >> >>* if I intended to do more than 100 samples, I would either write a more >>sophisticated spreadsheet that would show something like a board (as well as >>rudimentary checks like having 1 white and 1 black king), or write a program to >>draw random boards > >You need to write a special program to generate random board even if you want >only 20 samples because there is no easy way to choose a random position when >every position gets the same probability without a special program. > I don't see why that would matter. If you do an _exhaustive_ search of the chess game tree, you should be able to reach essentially any position with the right moves, which would mean that random positions would be a pretty good way to "Monte-Carlo" the answer for how many of the N total positions would be illegal. There are a few odd cases such as one with 6 white pawns on the e-file. This is possible to reach, but not if black has all his pieces, for example. A simple rule about file-shifts and minumum missing opponent pieces would suffice to handle that. There is no way to do anything other than an exhaustive search if the goal is to _prove_ that the game is won or lost or drawn from the get-go.
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.