Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-07-09T17:29:35.273Z
Answers.Text: What about a more compressed one, such that it has a map for every 4 squares and a corresponding code.
Answers.UserDisplayName: MikhailTal
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-07-09T17:30:37.090Z
Answers.Text: Once you count the possibilities, the number of bits is just the base 2 log of the number.  You can't compress any further.
Answers.UserDisplayName: Ross Millikan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-07-09T17:42:23.027Z
Answers.Text: What about if we had only lets say 8 pieces?
Answers.UserDisplayName: MikhailTal
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-07-09T20:21:13.640Z
Answers.Text: 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.
Answers.UserDisplayName: Ross Millikan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-07-10T14:02:15.297Z
Answers.Text: There is a [website](http://kirill-kryukov.com/chess/nulp/) 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.
Answers.UserDisplayName: JiK
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-09-11T07:16:09.133Z
Answers.Text: This doesn't account for pawn promotion, the possibility of en passant squares or castling rights.
Answers.UserDisplayName: David Richerby
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-17T19:32:43.030Z
Answers.Text: @DavidRicherby:  those have very few possibilities so will not impact the number of bits.  The 140 is rounded up from the exact value.  That will cover the additional information.
Answers.UserDisplayName: Ross Millikan
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-07-09T16:22:47.850Z
Answers.LastActivityDate: 2014-07-09T16:22:47.850Z
Answers.UserDisplayName: Ross Millikan
Answers.Body: <p>The engine opening books in polyglot format store the fen in a 64 bit hash. </p>
  
  <p>see <a href="http://hgm.nubati.net/book_format.html" rel="nofollow">http://hgm.nubati.net/book_format.html</a> for more information</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-09-11T07:17:51.870Z
Answers.Text: 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.
Answers.UserDisplayName: David Richerby
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-09-10T16:41:47.477Z
Answers.LastActivityDate: 2014-09-10T16:41:47.477Z
Answers.UserDisplayName: Simon Meyer
Body: <p>What is the most compressed way to "write" a chessboard as an integer considering en passant and castling as always possible no matter what.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-07-07T10:32:57.260Z
Comments.Text: (1) [Forsyth–Edwards Notation](http://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_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.
Comments.UserDisplayName: JiK
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-07-07T12:12:13.357Z
Comments.Text: 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?
Comments.UserDisplayName: MikhailTal
Tags: <notation><fen>
Title: Numerical FEN writing
ThreadText: # Numerical FEN writing
  
  (Asked by: username_0 on 2014-07-07)
  
  What is the most compressed way to "write" a chessboard as an integer considering en passant and castling as always possible no matter what.
  
  **Tags:** notation, fen
  
  > **Comments:**
  > **username_1**: (1) [Forsyth–Edwards Notation](http://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_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.  
  > **username_0**: 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?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2014-07-09. Score: 4
  
  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.
  
  > **Comments:**
  > **username_0**: What about a more compressed one, such that it has a map for every 4 squares and a corresponding code.  
  > **username_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.  
  > **username_0**: What about if we had only lets say 8 pieces?  
  > **username_2**: 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.  
  > **username_1**: There is a [website](http://kirill-kryukov.com/chess/nulp/) 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.  
  > **username_3**: This doesn't account for pawn promotion, the possibility of en passant squares or castling rights.  
  > **username_2**: @username_3:  those have very few possibilities so will not impact the number of bits.  The 140 is rounded up from the exact value.  That will cover the additional information.  
  
  ---
  
  ### Answer by username_4 on 2014-09-10. Score: 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.
  
  > **Comments:**
  > **username_3**: 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.  
  
  ---
  
  