Author: blass uri
Date: 21:32:54 08/14/99
Go up one level in this thread
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. This is not the only problem. There are also many illegal positions but only the problem you mentioned worth more than 18 bits. 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 and black has 3 queens,3 rooks,3 bishops,3 knights then you divide by 24*24*24*24*6*6*6*6 and it is more than 2^18 and even more than 2^28 and in every case you devide by at least this number because numbers like 5!*2! are bigger relative to 4!*3!. It does not prove that the number of legal positions is less than 2^160 because there are many legal positions when not all the pieces are promoted. My counting program proved that if you do not consider side to move 50 move rule and rules like castling then 3.7010630121207222927827147741452119115968e46 is an upper bound for the number of legal positions. It is possible to do a program to improve this bound but it is not important to me now. 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.