What is the most compressed way to "write" a chessboard as an integer considering en passant and castling as always possible no matter what.
2
-
(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.– JiKJul 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?– MikhailTalJul 7, 2014 at 12:12
Add a comment
|
2 Answers
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. Jul 9, 2014 at 17:29
-
2Once 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
-
-
1If 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
-
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.
-
1That'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