Author: Uri Blass
Date: 22:26:51 05/17/01
Go up one level in this thread
On May 17, 2001 at 19:08:15, J. Wesley Cleveland wrote: >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. >> >>Uri > >This seems overly complicated. If you have an encoding method, say, that encodes >all positions into 168 bits, then generate random 168 bit numbers and see what >percent of the corresponding positions are legal. I agree with the idea except that 168 is too much and you should use 155 bit numbers. My counting program proved that the number of legal positions is less than 2^155 (the exact upper bound is 3.7010630121207222927827147741452119115968e46) if you do not consider side to move en passant rule and right to castle and it means that you can translate every number that is smaller than 3.7010630121207222927827147741452119115968e46 to a pseudo legal position. I remember that people found a smaller bound by using the fact that part of my material structures are illegal and cannot happen in a game but it was still more than 1e46 The special program that I mean is exactly the program that translates the random numbers to chess positions. The first thing that you need to do in order to develop this program is to translate the number to a material structure(for example 0-4031 can mean king against king because there are 64*63 pseudo legal positions of king against king so I need 64*63=4032 integers,4032-254015 can mean white king and white rook against black king because I need exactly 64*63*62 integers for all the pseudo legal positions of this structure...) Uri
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.