Numerical FEN writing

What is the most compressed way to "write" a chessboard as an integer considering en passant and castling as always possible no matter what.

• (1) Forsyth–Edwards Notation (FEN) is a certain way to decode a chessboard position. I think you don't mean that. (2) "Most compressed" can mean a lot of things, each of which has a different answer: Smallest length of the integer (in bits) on average or worst-case? Are the positions taken form real chess games or can you put any number of any pieces on the board in any positions? etc. etc.
– JiK
Commented Jul 7, 2014 at 10:32
• A normal chess board position. And yes, by most compressed I mean the least number of bits for the integer, for example can you express it as 8 bytes? Commented Jul 7, 2014 at 12:12

If all the pieces are on the board, there are 64!/32!/8!^2/2^6*(32/63)*(31/61) or about 1.2*10^42 positions. This would require 140 bits. The 64!/32! puts the pieces on squares, the divisions account for permuting like pieces, and the last two fractions put the bishop pairs on opposite color squares. I would guess a dozen or so more bits would be required to cover positions with some of the pieces gone, but calculating the exact number is not so easy. Decoding a position from 140 bits can be done, but would be a pain. Clearly 8 bytes will not suffice.

• What about a more compressed one, such that it has a map for every 4 squares and a corresponding code. Commented Jul 9, 2014 at 17:29
• Once you count the possibilities, the number of bits is just the base 2 log of the number. You can't compress any further. Commented Jul 9, 2014 at 17:30
• What about if we had only lets say 8 pieces? Commented Jul 9, 2014 at 17:42
• If you select a specific set of 8 distinct pieces, you would have 64!/(64-8)!, about 1.8*10^14. That takes 48 bits. If you regard the 32 pieces as distinct, then choose 8, then put those on the squares, it is (32 choose 8) or about 10^7 times higher. This would take another 23 or 24 bits. The fact that some of the pieces are identical will reduce this, but it is work to calculate how much. Commented Jul 9, 2014 at 20:21
• There is a website devoted to counting the number of legal positions up to equivalence (definitions given there) with given number of pieces. Currently they have results from 2 to 8 pieces.
– JiK
Commented Jul 10, 2014 at 14:02

The engine opening books in polyglot format store the fen in a 64 bit hash.