Smallest chess board compression Write an algorithm or program that can encode and decode a chess board. The goal is to make the smallest representation of a chessboard that could be used (once decoded) to determine all movement possibilities for a player on that turn.

The encoding must be able to show:


Whose turn it is.
Whether the player can castle on each side.
Whether the player can perform an en-passant, and if so, which of their pawns?
Positions of all pieces.


Important note on castling: If white moves their king one turn, and then moves it back the next, it must be clear that they cannot castle on either side after that. Same would go if they moved their left or right rook. Although the board is visually in the same state as it was two turns ago, the game state has changed. More info here: http://en.wikipedia.org/wiki/Chess#Castling

Important note on en-passant: This is also a turn-sensitive move. Read the rules for more info. http://en.wikipedia.org/wiki/Chess#En_passant

Determine input and output as needed. Major props to whoever can compress it the most!

Your score is determined worst-case scenario - maximum possible size in bits. Make sure you show how you calculated it that number and what you accounted for. Shoot for the smallest worst-case!
Min: 12 bitsMax: Avg:

Had and thought last night that I could possibly make it even smaller.

x   Colour to play next (0 -&gt; Black, 1-&gt; White)
1   Only King left?

00000 Position of White King (0 -&gt; A1 ... 63 -&gt; H8)
00000 Position of Black King

01 00000 11111  WK:A1, BK:H2 (Black to play)
11 00000 11111  WK:A1, BK:H2 (White to play)


The result is an impressive size of 12 bits!

So what about K +1 other type of piece?

x
 0
   0
     000  +Pawn
     001  +Rook   
     010  +Knight
     011  +Bishop
     100  +Queen


There 2 possible arrangement of the sub tree.   

   /\      /\
  +  K    K  +


Both result in the same bit sizes for all pieces. So it make no difference to which we use, I'll choose the first one.

x
 0
  0
   000
      1011001110000000000000000000000000000000000000000000000000000000000000
(+ 000) En-Passant (if &gt;= 2 pawn &amp; pawn in en-passant positions)
(+ 00 ) Castlings  (if &gt;= 1 rook)
Min: 75 bit
Max: 109 bits


So on King +2 other piece types

x
 0
  1
   PRBNQ
   00011  +N +Q
   00101  +B +Q
   00110  +B +N
   01001  +R +Q
   01010  +R +N
   01100  +R +B
   10001  +P +Q
   10010  +P +N
   10100  +P +B
   11000  +P +R


There are 5 possible sub trees (I'll use 1 and 2 to indicate which of the pieces.)

   /\          /\       /\         /\          /\
  /  \        /  \     /  \       /  \        /  \
 K   /\      /\   2   /\   \     1   /\      /\   \
    1  2    K  1     K  2   1       K  2    1  2   K


So we'll require 3 bits to encode which sub tree to use.

x
 0
  1
   PRBNQ
         000  Sub Tree used

Min:= 11 = Header 
       6 = 2 * 3
       4 = 1 * 4
       4 = 1 * 4
      60 = 60    Empty
      --
      85 bits

Max:=  11 = Header
        4 =  2 * 4 Kings
       48 = 16 * 3 Pawns
       12 =  4 * 3 Rook
       42 = 42 * 1 Empty
        3 =  1 * 3 En-Passant
        2 =  1 * 2 Castlings
      ---
      122 bits


Still doing the analysis for more pieces

+3 Other

x
 0
  1
   PRBNQ
         0000  Sub Tree used (of 14 possible)


+4 Other

x
 0
  1
   PRBNQ
         000000  Sub Tree used (of 42 possible)


+5 Other

x
 0
  1
   PRBNQ
         0000000  Sub Tree used (of 132 possible)
 (+000)
 (+00)


Max: 208?



Is it possible to encode all these sub-trees into 9bits?

If we total up all of the possible sub-trees we get 392 possible sub-trees.

 1  0
 2  2
 3  5
 4  14
 5  42
 6  132
    ---
    392  &lt;= 2^9




Using Freq ID

Since there 164603 unique piece frequencies. 

Log2( 164603) = 17.3286110452
             ~ 18 bits

0
 0000 0000 0000 0000 00  Freq ID


(+000)
   (+00)  Castling

Max:= 204 bits



rev 3

Min: 82 Max: 199 Avg: 160

Finally got around doing some analysis to find the maximum bit size.
With optimal huffman encoding for each of the unique piece frequencies.  

               0   Player
              00  Castling
               0  En-Passant Possible
            ?000  En-Passant column (include if En-Passant Possible = 1
  0000 0000 0000  Tree Encoding ID
[Board Encoding]  Between 66 .. 180 bits 


Note this is the worst possible size, which the En-Passant column bits if the number of pawns is greater than one. Irrespective of those pawns colours and position there is the potential for some boards to be 3 bits smaller.

Also there are only 144 different sizes(Worst case) for the size of the board.  



 75 - 216 bits (v2) 
v1  The minimum size is 98 bits (12.25 bytes), only the two kings on the board.

Maximum size is only 216 bits (27 bytes.) In the unlikly:-

  9 x Queens
  1 x King
  2 x Rooks
  2 x Knights
  2 x Bishops
on each side.


On average the size will be around 157 bits (19.625 bytes).

Pieces 

To encode the board I'm using a binary tree encoding scheme. 
An empty square is the most frequent from any where between 32 and 62 appearances.
Next are the pawns, then Rooks, Knights, Bishops and the least frequent are the Queen and King.

0 - left node
1 - righ node

     /\
    e  \    e:= Empty Square
      B/\W  B:= Black ; W:= White
      /  \
     /    \
    /      \
   /\      /\
  p  \    p  \  p:= Pawn
     /\      /\
    /  \    /  \
   /\  /\  /\  /\
  r  b n \ r b n \  r:= Rook; b:= Bishop; n:= Knight
         /\      /\ 
        q  k    q  k  q:= Queen ; k:= King


The starting board can be encode in just 166 bits (20.75 bytes)

  A     B     C      D      E     F     G     H
-----+-----+-----+------+------+-----+-----+------+
10100 10101 10110 101110 101111 10110 10101 10100 | 8 
  100   100   100    100    100   100   100   100 | 7
    0     0     0      0      0     0     0     0 | 6
    0     0     0      0      0     0     0     0 | 5
    0     0     0      0      0     0     0     0 | 4
    0     0     0      0      0     0     0     0 | 3
  110   110   110    110    110   110   110   110 | 2
11100 11101 11110 111110 111111 11110 11101 11100 | 1


To indicate whom's move it takes only single bit 

0-&gt; Black , 1-&gt; White


Castling can be encoded in 4 bits.

 B  W
LR LR
00 00


So I've use 171 bits (21.375 bytes) 

En-Passe can be encoded into just 16 bits (2 bytes)

So in total thats 187 bit (23.375 bytes).

Layout

  bits    Encodes
 0 -  15  En-Passe
16 -  19  Castling
      20  Move 
21 -  23  Unused
24 -&gt; ..  Board


Not written any code yet. 

Notice that 3 of the bits that are unused. So the max is 213bits.



Possible Improvements

1) Reduced the header block form 24 to 8 bits (with @Peter Taylor suggestion)

0 - 2 En-Passant
    3 Move
4 - 7 Castling
8 ... Board Pieces 




2) Variable length header

A small 4 bit fixed header 

0 0 0 0
| | | |
| | | +-&gt; En-Passant Block Present?
| | | 
| | +---&gt; Pawns on board?
| |
| +-----&gt; Castling still possible?
|                
+-------&gt; Who's move? 0-Black 
                      1-White


Next block of additional bits (If castling is still possible)

00 00
|| ||
|| |+-&gt; White Castle Right
|| +--&gt; White Castle Left
||
|+----&gt; Black Castle Right
+-----&gt; Black Castle Left


Next block of additional bits (if pawns are present)

000--&gt; En-Passant column Position


So now I have a variable length header 4 - 11 bits



3) Use a different encoding scheme depending on what pieces are left on the board.

By changing the tree encoding depending on what pieces are on the board and there frequency.

One possible encoding for an end game state (No Pawns)

        /\            
       e /\           
  Black /  \ White
       /    \
      /      \
     /        \       
    /\        /\
   /  \      /  \     
  /   /\    /   /\
 /\  / /\  /\  / /\   
r b n q k  r b n q k


Which is about ~4 bits per piece. 

Which type of pieces are present on the board?

RBNQK Permutation
11111 (11111)


Permutation is Variable length 0-5 bits.
If only one type of piece is left then don't include it.

Which permutation of those pieces to use for the tree? 
This is the factorial of the number of pieces in the above example it is 5 pieces so 120 possible permutations that can be encoded. 

 #    !  bit 
 6  720  10  (If pawn included)
 5  120   6
 4   24   5
 3    6   3
 2    2   1  Don't include as of equal size.
 1    1   0  Don't include as its not needed.


Remember that there is addition bits for the empty squares and color.



Examples

Let's give an example of only QK left

RBNKQ
00011

  /\
 s  \
    /\
  B/  \W
  /\  /\
q  k q  k

101 100  0 x 60 110 111 ==&gt; 60 + (2 x 6) = 60 + 12 = 72 bits for the board

0000 00011 Header ==&gt; 9 bits


81 bits total



Let's give and example of only kings left

 RBNQK
 00001 

  /\
 s  k
   / \
  B   W

 10 0 0 0 0 0 0 0   K... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 11  .... ...k


Put all together 

 header  4   0 0 0 0
 pieces  5   0 0 0 0 1
 perm    0   - - - - - -
  board 66   10 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 11


So I calculate the smallest encoding for board at 75bits (9 bits 3 bit)

Still yet to calculate how this coding scheme affects the maximum size.



Improvement 4

Reduce the number of bits for castling to just 2 bits. Just castling for the player who's turn it is.

 0 Castling possible (from header block)
 LR 
 00


Thinking about it, it maybe better just to include the 2 bits inside the header block.