0

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
3

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
  • 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. – 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
  • 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. – 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
0

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. – David Richerby Sep 11 '14 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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