Author: blass uri
Date: 00:51:25 08/15/99
Go up one level in this thread
On August 15, 1999 at 00:32:54, blass uri wrote: >On August 14, 1999 at 17:54:17, Bruce Moreland wrote: > >> >>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. <snipped> >We can look at cases when every case is >64*63*...53*44*43*...*29 >if I assume white has 4 queens,4 rooks 4 bishops,4 knights This is a mistake. I forgot that the sides have a king but you divide by a big number even if you divide only by (4!*4!*4!*3!)*(3!*3!*3!*2!) and it is the best case I divide by 24*24*24*6*6*6*6*2 and it is clearly more than 2^18. I also do not understand the 44*43*... because after you put the 12 promoted pawns you have 52 options for the next piece so it should be 52*51*...37 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.