Author: Guido
Date: 03:10:36 11/04/99
Go up one level in this thread
On November 03, 1999 at 14:17:10, Ratko V Tomic wrote: >>Total dispositions: (48!/(32!*8!))^2 / 64 = 2.14 10^40 ===> 134 bits >> >>I think that the number is wrong and that the correct answer is 1/4 of this >>value, so 132 bits are sufficient to represent all the positions. A new >>help for the goal of a maximum of 160 bits to represent every chess >>legal position! > >That's not as simple as 2 more bits. Namely if you place 8+8 pawns first into >their 48 square pawn space, then you proceed with 2+2 bishops, the 1st bishop >may have anywhere from 16 to 32 squares avaliable, depending on how many in >which color squares the particular pawn configuration has taken. The same goes >for the 2nd white bishop. The black bishops would only have one less square each >(taken by the matching white bishops). > >If, instead of pawns, you place 4 bishops (no promotions assumed, so they take >opposite color squares) first on the empty board, you get (32*31)^2/4 = 246016 = >17.91 bits. But then when you start placing pawns, you have to break down these >4-bishop configurations into 5 subsets, based on how many bishops (0 to 4) fall >within the 48 pawn-usable squares. Say you get numbers N0, N1, .., N4 for 0 >bishops in the pawn area to 4 bishops in the pawn area (case N2 further >subdivides in the 2 subsets, based on whether 2 bishops in each area could step >on each other or not). Then you compute for each of the 5 cases the number of >pawn configurations (which depends on the number of free pawn squares, which >start with 48 for the N0 cases, down to 44 for the N4 cases), as P0, P1,..., P4. >The final number pawn + bishops cases is then P0*N0 + P1*N1 +.. + P4*N4. The >remaining 12 pieces can then be placed as before starting with 44 avaliable >squares for their placements, down to 32 free squares when the placement is >complete. > >For N0 to N4 we have: > > N0 = [(8*7)^2]/4 = 784 > N1 = 4*(24*8*7*8)/4 = 10752 > N2 = [2*(24*23*8*7) + 4*(24*24*8*8)]/4 = 52320 > N3 = 4*(24*23*24*8)/4 = 105984 > N4 = [(24*23)^2]/4 = 76176 > >Although the total here is the same as for the 4 bishops before splitting to 5 >cases, (246016), each subset allowes different numbers of pawn configurations, >so we can't just multiply total bishop cases with total pawn cases. > >For the corresponding P0 to P4 pawn configurations we have: > > P0 = 48!/(32!*8!*8!) = 2.901991 * 10^16 > P1 = 47!/(31!*8!*8!) = 1.934660 * 10^16 > P2 = 46!/(30!*8!*8!) = 1.276053 * 10^16 > P3 = 45!/(29!*8!*8!) = 8.322082 * 10^15 > P4 = 44!/(28!*8!*8!) = 5.363120 * 10^15 > >So the Bishops + pawns give NBP=P0*N0+P1*N1+...+P4*N4 positions, which with >figures above gives: > > NBP = 2.188946 * 10^21 = 70.89 bits > >The remaining 12 pieces will have number of placements: > > NR = 44!/(32!*2!*2!) = 2.526*10^18 = 61.13 bits > >The total is then 132.02 bits for the full board & bishop color restriction. The >earlier, bishop non-optimized calculation gave 133.97 bits. The saving is thus a >little under 2 bits (1.95 bits). When rounded up to the integer number of bits >(as the actual storage would end up using), the optimized case needs 133 whole >bits, while the unoptimized needs 134 whole bits, hence the effective saving is >1 bit only. YOU ARE RIGHT! The number of bits is not 2, but 1.95 as you wrote. But IMHO there are two errors in your calculations that compensate each other! The positions of 4 bishops on the empty board are (32*31)^2 = 984064, i.e. 4 times your value, and the same error is present in N0, N1, N2, N3 and N4. All these values must be multiplied by 4, so the value of NBP would be: NBP = 4 * 2.188946 * 10^21 = 8.755784 * 10^21 But NR, always IMO, must be divided by 4, giving: NR = 44!/(32!*2!*2!*2!*2!) = 6.314 * 10^17 Obviously the product doesn't change and the conclusion is right. Before repeating your calculations I convinced myself with the following considerations: Forgetting the pawns, imagine you have a 2x2 board and try to put on the board 4 bishops, 2 white and 2 black. It is easy to found that there are 6 different positions, 4 of which satisfy the chess legality condition (square of different colour for white bishops and for black bishops), while only 2 must be rejected! In this case the fraction is 2/3 instead of 1/4. If we increase the dimensions of the board to 4x4, 6x6, 8x8 (only even number of square per side), this fraction will decrease until it will reach the value of 1/4 for a board of infinite dimensions. In a general case with N squares (N is a square of an even number), this fraction is equal to: F = (N/2)^2 * (N/2-1)^2 / (N * (N-1) * (N-2) * (N-3) / 4) The limit for N ==> infinite is clearly 1/4. With this formula I can obtain an approximation of your result of 1.95 bits in a very easy way: Four bishops without constraints (as rooks or knights) can be disposed on an empty chess board in: 64*63*62*61/(2!*2!) = 3812256 positions On the contrary the legal positions for the 4 bishops are: (32*31)^2 = 984064 Now: 3812256 / 984064 = 3.874 ==> 1.954 bits The correct calculation must keep into account pawns and therefore it is necessary to follow your procedure, but the result is only a little different. In my last message KDDKDD ending was KQQKQQ ending! D (from: Domina) is the symbol used in neolatin and other languages for queen. Regards Guido
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.