Author: Ratko V Tomic
Date: 15:17:05 11/03/99
Go up one level in this thread
>> It would take a program, though, to go >>though all 10^28 MC cases > >You mean 2^28 and not 10^28 > Yes, thanks, the 2^28 is the upper bound mentioned few more times there. >>and add up the numbers of positions each generates to >>check if that is the case > >I generated a program to find an upper bound on the number of legal positions >by the same idea some monthes ago. > >It found the number >3.7010630121207222927827147741452119115968e46 >when you ignore the side to move right to castle and the 50 move rule > That is on average 154.7 bits over all positions. What language did you use to get this many significant digits? I know a UBASIC (shareware) can work with thousands of digits precision, but it is an interpreter and may run out of time and/or memory (just the count and worst case estimate should be Ok in UBASIC). I was thinking of maybe just writing a few C functions with +,*,-,/ operations on 32 byte integers, plus conversions to/from long double (10 byte floating point format) to cover the numbers which may be to small as individual add-on but could add up to a significant part when hundreds of millions of the little ones add together. >I think that it is a better idea to classify position on something >slightly more general then material configuration. > >I define a good pawn as a passed pawn or a pawn that is in the same file as >another pawn of the same colour. > >It is possible to find an upper bound for the number of good white pawns >+ the number of promoted white pieces (2*the number of captures of black >pieces+the number of captures of white pieces) > >a similiar upper bound can be proved for black > >I used this observation only to reduce the number of legal material >configurations in my program but it is possible to look at material >configurations when good pawns and bad pawns are different kind of pieces. > I am probably thinking along a similar path. In the method I'm playing with the material classification would be further subdivided by the number of excess pieces (pieces which could only have come from promotions, e.g. White Queens beyond 1 W.Queen, W.Rooks beyond 2, etc). In conjuction with a table for material content for one side (which fits in 14 bits), the classification of excess pieces would allow elimination of black+white pairs which have more than 12 excess pieces (since each side can have up to 8 excess pieces). The excess pieces also help find the maximum pawns which position may have (one pawn less for each new excess piece and also for each new triplet of excess pieces an additional pawn is taken out from the maximum pawns). >It is possible to improve my result by doing 2 counting programs: > >the first program is going to count the number of pawns configurations of >x1 good white pawns, x2 bad white pawns,x3 good black pawns,x4 bad black pawns >for every x1,x2,x3,x4 and remeber these numbers in an array > >the second program is going to count for every material configuration (when you >differntiate between good and bad pawns) the number of possible psaudo legal >positions(using the array that was calculated by the first program). > >I was too lazy to do these 2 programs. >and you need a very long time to run the second program if you have not a super >computer(maybe some days) > There are about 2^55 (i.e. 10^16) distinct pawn configurations for the 8+8 pawn case only. And there are 81 distinct pawn material content cases (8+8 case, while being one of these, gives the largest number of pawn configurations among the 81 cases). So a brute force loop over such sets would not work. One would need specialized combinatorial algorithms which can classify and do the bulk processing on the whole classes of configurations at once (at least be able to do so for the limited purposes of enumeration & classification). At this point for me that is one of those optimizations I have left for much later, if it is needed after the simple things get tried first.
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.