Author: blass uri
Date: 14:25:43 11/03/99
Go up one level in this thread
On November 03, 1999 at 15:03:49, Ratko V Tomic wrote: >> You can have many bishops on the board. I believe that the maximum >> would be 10 bishops, with up to 9 of a single color. >... >> Any scheme to number all positions must take into account any legal >> board position. Otherwise it cannot be used and its value is limited > >This was only a sub-problem, with restrictions as Guido stated (the maximum >material count, i.e. no captures or promotions have occured as yet), in a >different approach to encoding. The approach is based on classifying first all >positions by Material Content (MC; i.e. how many pieces of each kind are there). >Then for each of the distinct MC states one can compute number of distinct >positions they generate and add them up over all MC possibilities. It is easy to >show that the number of distinct materal content states is always below 2^28 >(that's a very rough upper limit, the exact number may be 3-4 bits lower), i.e. >fewer than 28 bits are used to index MC part of the code. As a rough estimate >for the upper bound on the maximum number of states one MC may have, I looked at >the maximum material configuration, which from these calculations needs 133 >whole bits (and this is the case Guido was discussing). So, that gives a rough >upper bound on the number of positions as 133+28=161 bits. Since 28 bit is a >highly non-optimized upper limit on number of MC states, and an average position >will need substantially fewer bits than 133, it seems more likely that all >positions will fit in the 160 bits. It would take a program, though, to go >though all 10^28 MC cases You mean 2^28 and not 10^28 >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 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. 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) 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.