Alternatives to the FEN notation

Question

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.

Answer 1

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:

1. The slashes are unnecessary for machine storage; each rank must simply "add to 8". So we can eliminate slashes in our internal representation.
2. 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.
3. We don't need any spaces; again they're a convenience for humans. That saves us five characters.
4. "Who has the move" is one bit: White or Black.
5. Castling availability is four bits: available/unavailable for each of KQkq.
6. 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.
7. 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):

<position><whose move><castling><half moves><full moves><en passant>
 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:

<position><whose move><castling><half moves><full moves><en passant>
 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.

Answer 2

Extended Position Description (EPD) 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 3

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.

Answer 4

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.

Answer 5

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.