Author: Bruce Moreland
Date: 14:54:17 08/14/99
Go up one level in this thread
On August 14, 1999 at 11:14:18, KarinsDad wrote: >On August 14, 1999 at 04:22:28, Bruce Moreland wrote: > >> >>On August 14, 1999 at 01:25:50, KarinsDad wrote: >> >>>I wrote a white paper on compressing a random legal position into 20 bytes. >>>Unfortunately, I have not been successful on that. Until I am, that white paper >>>stays put (actually, I have basically convinced myself that it cannot be done, >>>so I doubt I will ever publish that paper). >> >>It can be done if and only if there are <= 2^160 legal positions in chess. The >>technique would involve assigning each legal position a unique number and >>storing that number. You can't do any better than this. >> >>Assuming that there are more than 2^160 legal positions, you still may be able >>to store typical positions in fewer than 160 bits, but only at the cost of >>storing less common positions in more than 160 bits. >> >>bruce > >Due to how close I came, I am also convinced that there are < 2^160 chess >positions. However, a one to one assignment would be a nightmare. Hence, a more >heuristic approach is needed. > >I have not been able to find one. I can get most normal positions down to about >150 bytes or so, but it is those bizarre positions with promotions and minimal >captures to accomplish promotions which result in > 160 bytes. > >I ended up with 351 basic possibilities out of which 69 require more than 160 >bits to store. However, ALL 69 of those possibilities are ones which would NEVER >occur in normal chess play. Normal chess positions compress down below 160 quite >easily. But, that is not the problem I am trying to solve. > >KarinsDad :) I'm going to try to crush you, in the hopes that I'll get you to finish the job on yourself rather than making me fill all of the holes in what follows. White's b-pawn goes to b6 and then takes on a7. It can queen, white's original a-pawn can advance to queen, and black's b-pawn can advance to queen, without any further captures. Black's d-pawn does the same thing to white's c-pawn, and we have three more promoted pieces and we lose another pawn. Two other pawns do the same thing. And now we have 12 promoted pieces and 16 unpromoted pieces. Each promoted piece can exist in one of four forms. You can put the first one on any of 64 squares, for a total of 256 possibilities. You put the second one on any of 63 squares, the third on any of 62, etc. Once you are done you put the remaining pieces on their squares, as appropriate. The simple math here is: (64*4) * (63 * 4) * ... * (53 * 4) * 44 * 43 * ... * 29 If you wad that all up it's 2.30*10^53, which is 177+ bits. If there is a problem with this, it is that there are a *lot* of duplicated positions, but I wonder if there are 18 bits worth. bruce
This page took 0.01 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.