Author: blass uri
Date: 17:53:27 11/03/99
Go up one level in this thread
On November 03, 1999 at 18:17:05, Ratko V Tomic wrote: >>> 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 used C and my first program did not get so many significant digits. Dan corbit translated my program to C++ and got these many significant digits. > >>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). Maybe you mean that for each new triplet of excess pieces an additional piece or pawn is taken out of the maximum pawns+pieces. an additional pawn is not correct because of the fact that white can promote more than 3 pawns only by taking black pieces. > > >>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). 8+8 case does not give the largest number of cases because I know that all the pawns are blocked and in every file we have only 6*5/2=15 cases so we have only 15^8 case(less than 2^32) 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. I agree that you need some combinatorial optimizations and it is possible to do it. I count for every case of xa white pawns and ya black pawns in file a, xb white pawns and yb black pawns in file b.... when it is easy to calculate the number of cases of xa white pawns and y1 black pawns in file a is 6!/(xa!*ya!*(6-xa-ya)!) if xa=1 then you know that in xa/(xa+ya) cases you have a passed pawn(a good white pawn) and if xa>1 then you know that all the white pawns are good pawns by my definition. You have to divide the case to 2 cases(there is a passed pawn and there is no passed pawn in the file). every case like this can have many pawns structures(if you have 6 options in 4 files(with one pawn) and 15 options in 4 files with 2 pawns you can calculate 6^4*15^4 cases with the same 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.