Author: Robert Hyatt
Date: 21:50:30 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. This is actually very difficult. IE for a position to be legal, you need to prove the following: 1. side on move is not in check; 2. pieces could actually reach the given position (ie if you have 3 pawns on a single file, the opponent must be missing at least two pawns/pieces; 3. the side not on move actually could have made a legal move to get us to the current position. 4. then the side on move actually could have made a legal move to get us to that previous position. IE 3 and 4 are recursive and could be restated: 3a. The position must be reachable from the opening position of the game. That is yet another exponential problem. Or is that O(1) too. :)
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.