# 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 Jul 7 '14 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? – MikhailTal Jul 7 '14 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. – MikhailTal Jul 9 '14 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. – Ross Millikan Jul 9 '14 at 17:30
• What about if we had only lets say 8 pieces? – MikhailTal Jul 9 '14 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. – Ross Millikan Jul 9 '14 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 Jul 10 '14 at 14:02

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