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, 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?
    – MikhailTal
    Jul 7, 2014 at 12:12

2 Answers 2


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, 2014 at 17:29
  • 2
    Once you count the possibilities, the number of bits is just the base 2 log of the number. You can't compress any further. Jul 9, 2014 at 17:30
  • What about if we had only lets say 8 pieces?
    – MikhailTal
    Jul 9, 2014 at 17:42
  • 1
    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. 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
    Jul 10, 2014 at 14:02

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

see http://hgm.nubati.net/book_format.html for more information

note that they leave out the information about the movenumber and the actioncounter which counts the number of moves without pawn moves or taking until the 50 move rule draw. But all the other information like castling possibilities or enpassants are included.

  • 1
    That's a hash, not a representation of the position. Given the hash, it's not possible to uniquely determine the position, since there are many more than 2^64 possible positions. Sep 11, 2014 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.