Author: KarinsDad
Date: 08:39:32 08/15/99
Go up one level in this thread
On August 14, 1999 at 17:54:17, Bruce Moreland wrote: [snip] > >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 I don't know Bruce. You left out some information in your calculation. The pawns do not have to promote, the other pieces could be off the board, plus you forgot en passant, castling, and side to move. Overall, doing it this way should get you up to about 185 bits or so, but I didn't check the math. However, this type of equation is dubious both since there is duplication and since you are feeding in extra bits due to empty squares. In other words, it takes less space to represent the location of pieces via a bitboard since 50% or more of the squares are empty rather than to indicate the location of every single piece via 8- bits. A simple method is: 64 bits piece location bitboard 1 bit side to move 12 bits king locations and castling 1 bit en passant 2 bits each pawn 4 bits each piece For your example, that would be: 64 + 1 + 12 + (4 * 26) = 181 bits (no need to add an en-passant bit if there are no pawns). If you left a pawn of each color on the board (as opposed to promoting them all), you would drop 4 bits for replacing pieces with pawns, but add one promotion bit, so it would still be below 181 bits. The en passant trick is just one example of many on how further compression can be done, however, the en passant trick only works on about 40 cases out of the 351 (the cases where there are less than 2 pawns on the board). I can represent this particular example that you show in 161 bits worse case. However, there are more obnoxious cases with half of the pawns still being on the board that I can only represent in 165 bits worse case. KarinsDad :) PS. I am at a stage now where I still occasionally come up with a good idea on compressing data. However, I usually find out that it does a good job in some cases, but actually increases the size in others (usually those that I am still trying to get below 161).
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.