jwes wrote:There has been discussion of using FEN to store positions in databases. It seems to me that a binary format could be more space efficient and at least as easy to parse. The format I devised is:
64 bit bitmap where each 1 bit represents an occupied square or the ep square if there is one.
32 4 bit chunks which define the contents of each occupied square in order.
The 16 possible 4 bit chunks are:
Code: Select all
0 WP 8 BP
1 WN 9 BN
2 WB 10 BB
3 WR that can castle 11 BR that can castle
4 WR that cannot castle 12 BR that cannot castle
5 WQ 13 BQ
6 WK wtm 14 BK
7 WK btm 15 ep square
This would allow any legal position to be encoded in 24 bytes unless repetition count, 50 move count, or move no. are needed. This is less than half the average epd length and perhaps 25% more than the theroretical minimum.
I use a similar scheme for learning databases and the unique position generator used for deep perfts. I use the regular 12 pieces, plus pawn-that-can-be-captured-ep, rook-that-can-castle, and king-whose-side-is-to-move.
Speed is an issue generating these things though and it has crossed my mind that the PEXP/PDEP insrtructions from recent intels might be able to produce a 192 bit position much faster, assuming you have appropriate bitboards handy (I haven't really thought it through in detail, I don't own such a cpu.)
For example, store the 64 occupied bitboard. Now create four 32-bit "reduced bitboards" by using PEXP, occupied, and various other bitboards.
The first one would probably be white_occupied. Next one take all rooks and pawns (of both colors), OR them, and use PEXP. Third could be rooks, bishops and queens. Fourth queens and knights. So if you were to take corresponding bits from each of the "reduced bitboards" you would end up with a table something like:
Code: Select all
0000 black king
0001 black knight
0010 black bishop
0011 black queen
0100 black pawn
0101
0110 black rook
0111
1000 white king
1001 white knight
1010 white bishop
1011 white queen
1100 white pawn
1101
1110 white rook
1111
Hope I didn't screw that up, did it off the top of my head.
You could then manually set the last bit for rooks which can castle and a pawn that can be captured ep (which would use the unused codes above). Still needed is a quick way to represent which color is to move.