Answers.Body: <p>Extended Position Description (<a href="https://chessprogramming.wikispaces.com/Extended+Position+Description" rel="nofollow">EPD</a>) adds "operations" to FEN. These operations include, among others, best move, repetition count, and predicted move. It's not, obviously, more compact, but it does more.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-02-03T15:51:20.733Z
Answers.LastActivityDate: 2015-02-03T15:51:20.733Z
Answers.UserDisplayName: Pete Becker
Answers.Body: <p>Unless I am missing something obvious, the representation</p>
  
  <pre><code>0      empty
  100    white pawn
  101    black pawn
  110xxx any piece except Rook
  111x   Rook
  </code></pre>
  
  <p>encodes a full house (that is, prior to any capture) in 32*1 + 16*3 + 12*6 + 4*4= 168 positional bits. Plus, of course, 4 castle bits, 3 en passant bits, and 7 or 8 50-move-rule bits.</p>
  
  <p>The worst case (8 pawns has been promoted by the cost of capturing 8 other pawns, resulting in 20 pieces + 4 rooks on board) requires 40*1 + 20*6 + 4*4 = 176 positional bits.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-13T22:57:30.530Z
Answers.Text: If White's a, c, e, and g pawns capture black's b, d, f, and h pawns, then white would get to promote eight pawns and black could promote four.  So I think that pushes the number of bits up to 200.
Answers.UserDisplayName: supercat
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-13T23:05:44.827Z
Answers.Text: @supercat Good catch!
Answers.UserDisplayName: user58697
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-02-03T20:43:56.527Z
Answers.LastActivityDate: 2015-02-03T20:43:56.527Z
Answers.UserDisplayName: user58697
Answers.Body: <p>It is possible to fit the board and all info (except 50 move rule) into an easy manageable 256 bits. I would suggest the following. 64 squares and 4 bits per square allows for 16 possible states. 0 would represent the empty square. Then we have 6 pieces, but I would reserve a 7th for the 'moved rook' so castling possibility can be determined. One bit to indicate white or black. We are using 15 states and are left with 1 more state: value 8 (1000 binary).
  It also represent an emoty square, but we can use that on the 3rd or 6th rank to indicate the pawn ahead of it moved 2 squares and is subject to being captured 'en passant'.
  Finally, we also use this value to indicate the side to move. Find the first empy square on the lower half of the board to indicate it's white to move. On the upper half for black. Better stay clear from the 3rd and 6th rows for easyness.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-08T03:15:38.633Z
Answers.Text: It is possible, although extremely unlikely, for there to not be an empty square on one half of the board.
Answers.UserDisplayName: D M
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-10-21T15:37:53.920Z
Answers.LastActivityDate: 2015-10-21T15:37:53.920Z
Answers.UserDisplayName: BartV
Answers.Body: <p>You asked: One really missing bit in the FEN is the fact that it carries no information as to whether the position corresponds to a checkmate or check for that matter. Of course one can always put the position on the board and see if it's a checkmate or not, but it is not directly deducible from the notation. </p>
  
  <p>At this point, it might be a good a good question if one wants to embed a computationally complex piece of information into what should only be a description. </p>
  
  <p>The same thing applies to move notations - for example, between: algebraic notation (e2e4 b1c3) and SAN (e4 Nc3) - the later requires an engine to compute the TO position of every move, and is computationally complex to decode, while the former doesn't require writing a whole move generator to determine the inferred TO position - which may be of benefit.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-12-18T16:29:01.777Z
Answers.LastActivityDate: 2016-12-18T16:35:52.080Z
Answers.LastEditDate: 2016-12-18T16:35:52.080Z
Answers.UserDisplayName: johnrpenner
Answers.Body: <p>Since you're talking about programming, you're presumably looking for a storage scheme more compact <em>in computer memory space</em> than FEN. Besides going out to research how it's done in large tablebases, two possibilities come to my mind immediately.</p>
  
  <h1>Normal FEN</h1>
  
  <p>For the sake of this discussion, "normal" FEN is just a typical text string represented with 1-byte (8-bit) characters. Let's look at a <em>simplified worst case</em>:</p>
  
  <p><code>r1b1k1n1/1p1p1p1p/p1p1p1p1/1n1q1b1r/R1B1P1N1/1P1P1P1P/P1P1K1P1/1N1Q1B1R w KQkq e3 999 999</code></p>
  
  <p>This isn't a valid FEN of course, but it's an effective upper bound on our complexity. There are eight characters per rank, plus seven slashes, five spaces, and thirteen additional characters make up the remaining fields. That's 89 characters, for a total size of <strong>712 bits</strong>. </p>
  
  <h1>Compressed FEN</h1>
  
  <p>This version is just taking the a FEN representation and using some basic observations to reduce the number of bits required to store it. Here are our observations:</p>
  
  <ol>
  <li>The slashes are unnecessary for machine storage; each rank must simply "add to 8". So we can eliminate slashes in our internal representation.</li>
  <li>The remaining possible characters (in the first section) are: <code>kK qQ rR bB nN pP 12345678</code>. Distinction between 20 characters fits in five bits, so in our simplified worst case, we have five bits times eight files times eight ranks is 320 bits for the first part.</li>
  <li>We don't need any spaces; again they're a convenience for humans. That saves us five characters.</li>
  <li>"Who has the move" is one bit: White or Black.</li>
  <li>Castling availability is four bits: available/unavailable for each of <code>KQkq</code>. </li>
  <li><em>En passant</em> is usually unavailable, and it can occupy a lot of space (six bits to represent all squares), so let's move it to the end and make it optional: if <em>en passant</em> bits are present, it's available, but if it's unavailable we just terminate the representation after the move &amp; half-move bits to save space.</li>
  <li>For simplicity, I'm just allocating ten bits for each of the move and half-move counters. This means that games represented in this format cannot exceed 1023 moves (half-moves since the last capture or pawn advance). </li>
  </ol>
  
  <p>Our full format looks like this (in a simplified worst case with <em>en passant</em> available):</p>
  
  <pre><code>&lt;position&gt;&lt;whose move&gt;&lt;castling&gt;&lt;half moves&gt;&lt;full moves&gt;&lt;en passant&gt;
   320 bits  1 bit       4 bits    10 bits     10 bits     6 bits
  </code></pre>
  
  <p>This gives us a total size of <strong>351 bits</strong> in our impossible worst case, a little less than half the size of our starting point.</p>
  
  <h1>µFEN</h1>
  
  <p>If we abandon FEN altogether for the meat of the representation, we can slim it down a little further. Consider a single arbitrary square. That square can be empty, or it can have a piece on it. If it has a piece, it may be either white or black, and it may be a King, Queen, Rook, Bishop, Knight, or Pawn. That's a total of thirteen different states, which we can represent in four bits; something like this:</p>
  
  <pre><code>0000: empty square
  0001: White Pawn
  0010: White Knight
  0011: White Bishop
  0100: White Rook
  0101: White Queen
  0110: White King
  0111: unused
  1000: unused
  1001: Black Pawn
  1010: Black Knight
  1011: Black Bishop
  1100: Black Rook
  1101: Black Queen
  1110: Black King
  1111: unused
  </code></pre>
  
  <p>Obviously there are some unused "partial bits", so this scheme could almost certainly be improved further by someone with more knowledge of compression techniques, or simply a more careful mapping of the different states. Also in practice, this might be <em>larger</em> than the <em>Compressed FEN</em> described above, since there's no compression of contiguous blank spaces. However, it does represent the whole board in a constant 256 bits (4 bits * 64 squares), which is a 20% improvement in the worst cases.</p>
  
  <p>For simplicity, we'll just tag on the latter half of the <em>Compressed FEN</em> to complete the representation. So the format looks like this:</p>
  
  <pre><code>&lt;position&gt;&lt;whose move&gt;&lt;castling&gt;&lt;half moves&gt;&lt;full moves&gt;&lt;en passant&gt;
   256 bits  1 bit       4 bits    10 bits     10 bits     6 bits
  </code></pre>
  
  <p>That gives us a worst-case space requirement of <strong>287 bits</strong>. Not too bad!</p>
  
  <hr>
  
  <p><strong>Note 1:</strong> Remember, this is all just a <em>worst-case analysis</em> because I have a computer science background. Standard FEN usually performs much better than I have described it, since normal positions aren't the everyone-on-the-white-squares scenario I've used for comparisons here. So the percent improvements are likely a little lower than I've actually represented, but the trend probably still holds, at least for the compressed FEN representation. I'd be very interested if someone wanted to do a probabilistic average-case analysis for standard FEN (and by extension, the compressed version proposed above)!</p>
  
  <p><strong>Note 2:</strong> Remember that the speed tradeoffs for dealing with compressed formats may or may not be worth it for your applications! Depending on what language you're using and the level of control you have over individual bits, you may find that simple FEN is significantly faster to <em>use</em>, even if it requires more space!</p>
  
  <p><strong>Note 3:</strong> If you wanted to add a "check/checkmate/no-check" indicator to either of the new proposed notations, it's an extra two bits to represent the three additional states. Just toss it in before the <em>en passant</em> indicator.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-02-03T19:53:19.810Z
Answers.Text: The en passant information is really just a file, not a square (as the square can be deduced from the file together with the player to move). This reduces your worst case by three bits.
Answers.UserDisplayName: Stephen
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-02-04T09:52:10.840Z
Answers.Text: thanks for this detailed reply. Why in the 4-bit representation we left 0111 1000 1111 for unused? isn't one enough?
Answers.UserDisplayName: user098876
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-02-04T22:27:47.480Z
Answers.Text: @user098876 "unused" there just means that those three combinations are not mapped to anything. That extra "space" is why it's probably possible to improve the per-square mapping further with a more careful scheme, like the one in user58697's answer.
Answers.UserDisplayName: Henry Keiter
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-13T22:54:19.023Z
Answers.Text: Since at most 32 squares can have chess pieces on them, one could easily chop the size from 256 to 192 by using 64 bits to identify which squares are occupied, and then 4x32 bits to say what's on each such square.  Information about castling or en passant could be encoded by using different piece types for "rook that can castle" or "pawn that can be captured en passant".
Answers.UserDisplayName: supercat
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-02-03T19:28:46.073Z
Answers.LastActivityDate: 2015-02-04T06:22:38.003Z
Answers.LastEditDate: 2015-02-04T06:22:38.003Z
Answers.UserDisplayName: Henry Keiter
Body: <p>Apart from the FEN notation, are there other even more compact known chess-position notations? One that would of course also entail castling rights, and en passant possibilities. 
  One really missing bit in the FEN is the fact that it carries no information as to whether the position corresponds to a checkmate or check for that matter. Of course one can always put the position on the board and see if it's a checkmate or not, but it is not directly deducible from the notation. So such property would also be of importance in distinguishing between possible notations (apart from compactness etc.)</p>
  
  <p>If it helps, this is asked for practicality and efficiency reasons in programming. Thanks for any suggestions.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-02-03T07:36:21.580Z
Comments.Text: Why don't you turn this into an answer? I would be interested in a 128 bit chess position encoding.
Comments.UserDisplayName: BlindKungFuMaster
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-02-03T11:27:27.053Z
Comments.Text: @BlindKungFuMaster who are you talking to? :-)
Comments.UserDisplayName: Ellie
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-02-03T11:35:52.690Z
Comments.Text: Oh, just to somebody who realised there is no 128 bit chess position encoding. ;-)
Comments.UserDisplayName: BlindKungFuMaster
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-02-03T13:59:02.533Z
Comments.Text: If we knew what you were trying to accomplish we could give you better answers.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-02-03T15:31:08.340Z
Comments.Text: @TonyEnnis well let's start with whether: are there even alternatives or not?
Comments.UserDisplayName: user098876
Tags: <notation><fen>
Title: Alternatives to the FEN notation
ThreadText: # Alternatives to the FEN notation
  
  (Asked by: username_0 on 2015-02-02)
  
  Apart from the FEN notation, are there other even more compact known chess-position notations? One that would of course also entail castling rights, and en passant possibilities.
  One really missing bit in the FEN is the fact that it carries no information as to whether the position corresponds to a checkmate or check for that matter. Of course one can always put the position on the board and see if it's a checkmate or not, but it is not directly deducible from the notation. So such property would also be of importance in distinguishing between possible notations (apart from compactness etc.)
  
  If it helps, this is asked for practicality and efficiency reasons in programming. Thanks for any suggestions.
  
  **Tags:** notation, fen
  
  > **Comments:**
  > **username_1**: Why don't you turn this into an answer? I would be interested in a 128 bit chess position encoding.  
  > **username_2**: @username_1 who are you talking to? :-)  
  > **username_1**: Oh, just to somebody who realised there is no 128 bit chess position encoding. ;-)  
  > **username_3**: If we knew what you were trying to accomplish we could give you better answers.  
  > **username_0**: @TonyEnnis well let's start with whether: are there even alternatives or not?  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_10 on 2015-02-03. Score: 6 | Accepted answer
  
  Since you're talking about programming, you're presumably looking for a storage scheme more compact in computer memory space than FEN. Besides going out to research how it's done in large tablebases, two possibilities come to my mind immediately.
  Normal FEN
  For the sake of this discussion, "normal" FEN is just a typical text string represented with 1-byte (8-bit) characters. Let's look at a simplified worst case:
  r1b1k1n1/1p1p1p1p/p1p1p1p1/1n1q1b1r/R1B1P1N1/1P1P1P1P/P1P1K1P1/1N1Q1B1R w KQkq e3 999 999
  This isn't a valid FEN of course, but it's an effective upper bound on our complexity. There are eight characters per rank, plus seven slashes, five spaces, and thirteen additional characters make up the remaining fields. That's 89 characters, for a total size of 712 bits. 
  Compressed FEN
  This version is just taking the a FEN representation and using some basic observations to reduce the number of bits required to store it. Here are our observations:
  
  The slashes are unnecessary for machine storage; each rank must simply "add to 8". So we can eliminate slashes in our internal representation.
  The remaining possible characters (in the first section) are: kK qQ rR bB nN pP 12345678. Distinction between 20 characters fits in five bits, so in our simplified worst case, we have five bits times eight files times eight ranks is 320 bits for the first part.
  We don't need any spaces; again they're a convenience for humans. That saves us five characters.
  "Who has the move" is one bit: White or Black.
  Castling availability is four bits: available/unavailable for each of KQkq. 
  En passant is usually unavailable, and it can occupy a lot of space (six bits to represent all squares), so let's move it to the end and make it optional: if en passant bits are present, it's available, but if it's unavailable we just terminate the representation after the move & half-move bits to save space.
  For simplicity, I'm just allocating ten bits for each of the move and half-move counters. This means that games represented in this format cannot exceed 1023 moves (half-moves since the last capture or pawn advance). 
  
  Our full format looks like this (in a simplified worst case with en passant available):
  
   320 bits  1 bit       4 bits    10 bits     10 bits     6 bits
  
  This gives us a total size of 351 bits in our impossible worst case, a little less than half the size of our starting point.
  µFEN
  If we abandon FEN altogether for the meat of the representation, we can slim it down a little further. Consider a single arbitrary square. That square can be empty, or it can have a piece on it. If it has a piece, it may be either white or black, and it may be a King, Queen, Rook, Bishop, Knight, or Pawn. That's a total of thirteen different states, which we can represent in four bits; something like this:
  0000: empty square
  0001: White Pawn
  0010: White Knight
  0011: White Bishop
  0100: White Rook
  0101: White Queen
  0110: White King
  0111: unused
  1000: unused
  1001: Black Pawn
  1010: Black Knight
  1011: Black Bishop
  1100: Black Rook
  1101: Black Queen
  1110: Black King
  1111: unused
  
  Obviously there are some unused "partial bits", so this scheme could almost certainly be improved further by someone with more knowledge of compression techniques, or simply a more careful mapping of the different states. Also in practice, this might be larger than the Compressed FEN described above, since there's no compression of contiguous blank spaces. However, it does represent the whole board in a constant 256 bits (4 bits * 64 squares), which is a 20% improvement in the worst cases.
  For simplicity, we'll just tag on the latter half of the Compressed FEN to complete the representation. So the format looks like this:
  
   256 bits  1 bit       4 bits    10 bits     10 bits     6 bits
  
  That gives us a worst-case space requirement of 287 bits. Not too bad!
  
  Note 1: Remember, this is all just a worst-case analysis because I have a computer science background. Standard FEN usually performs much better than I have described it, since normal positions aren't the everyone-on-the-white-squares scenario I've used for comparisons here. So the percent improvements are likely a little lower than I've actually represented, but the trend probably still holds, at least for the compressed FEN representation. I'd be very interested if someone wanted to do a probabilistic average-case analysis for standard FEN (and by extension, the compressed version proposed above)!
  Note 2: Remember that the speed tradeoffs for dealing with compressed formats may or may not be worth it for your applications! Depending on what language you're using and the level of control you have over individual bits, you may find that simple FEN is significantly faster to use, even if it requires more space!
  Note 3: If you wanted to add a "check/checkmate/no-check" indicator to either of the new proposed notations, it's an extra two bits to represent the three additional states. Just toss it in before the en passant indicator.
  
  > **Comments:**
  > **username_11**: The en passant information is really just a file, not a square (as the square can be deduced from the file together with the player to move). This reduces your worst case by three bits.  
  > **username_0**: thanks for this detailed reply. Why in the 4-bit representation we left 0111 1000 1111 for unused? isn't one enough?  
  > **username_10**: @username_0 "unused" there just means that those three combinations are not mapped to anything. That extra "space" is why it's probably possible to improve the per-square mapping further with a more careful scheme, like the one in username_5's answer.  
  > **username_6**: Since at most 32 squares can have chess pieces on them, one could easily chop the size from 256 to 192 by using 64 bits to identify which squares are occupied, and then 4x32 bits to say what's on each such square.  Information about castling or en passant could be encoded by using different piece types for "rook that can castle" or "pawn that can be captured en passant".  
  
  ---
  
  ### Answer by username_4 on 2015-02-03. Score: 2
  
  Extended Position Description ([EPD](https://chessprogramming.wikispaces.com/Extended+Position+Description)) adds "operations" to FEN. These operations include, among others, best move, repetition count, and predicted move. It's not, obviously, more compact, but it does more.
  
  
  ---
  
  ### Answer by username_5 on 2015-02-03. Score: 1
  
  Unless I am missing something obvious, the representation
  0      empty
  100    white pawn
  101    black pawn
  110xxx any piece except Rook
  111x   Rook
  
  encodes a full house (that is, prior to any capture) in 32*1 + 16*3 + 12*6 + 4*4= 168 positional bits. Plus, of course, 4 castle bits, 3 en passant bits, and 7 or 8 50-move-rule bits.
  The worst case (8 pawns has been promoted by the cost of capturing 8 other pawns, resulting in 20 pieces + 4 rooks on board) requires 40*1 + 20*6 + 4*4 = 176 positional bits.
  
  > **Comments:**
  > **username_6**: If White's a, c, e, and g pawns capture black's b, d, f, and h pawns, then white would get to promote eight pawns and black could promote four.  So I think that pushes the number of bits up to 200.  
  > **username_5**: @username_6 Good catch!  
  
  ---
  
  ### Answer by username_7 on 2015-10-21. Score: 0
  
  It is possible to fit the board and all info (except 50 move rule) into an easy manageable 256 bits. I would suggest the following. 64 squares and 4 bits per square allows for 16 possible states. 0 would represent the empty square. Then we have 6 pieces, but I would reserve a 7th for the 'moved rook' so castling possibility can be determined. One bit to indicate white or black. We are using 15 states and are left with 1 more state: value 8 (1000 binary).
  It also represent an emoty square, but we can use that on the 3rd or 6th rank to indicate the pawn ahead of it moved 2 squares and is subject to being captured 'en passant'.
  Finally, we also use this value to indicate the side to move. Find the first empy square on the lower half of the board to indicate it's white to move. On the upper half for black. Better stay clear from the 3rd and 6th rows for easyness.
  
  > **Comments:**
  > **username_8**: It is possible, although extremely unlikely, for there to not be an empty square on one half of the board.  
  
  ---
  
  ### Answer by username_9 on 2016-12-18. Score: 0
  
  You asked: One really missing bit in the FEN is the fact that it carries no information as to whether the position corresponds to a checkmate or check for that matter. Of course one can always put the position on the board and see if it's a checkmate or not, but it is not directly deducible from the notation.
  
  At this point, it might be a good a good question if one wants to embed a computationally complex piece of information into what should only be a description.
  
  The same thing applies to move notations - for example, between: algebraic notation (e2e4 b1c3) and SAN (e4 Nc3) - the later requires an engine to compute the TO position of every move, and is computationally complex to decode, while the former doesn't require writing a whole move generator to determine the inferred TO position - which may be of benefit.
  
  
  ---
  
  