Author: Ratko V Tomic
Date: 11:17:10 11/03/99
Go up one level in this thread
>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.
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.