Chess Coding Challenge - Part 4 - Solution in Human Readable Pseudo-code...

Part 1 - How I Leveraged Scala and FP to Find a Solution
Part 2 - Scala infrastructure source code (and two encoder/decoder implementations)
Part 3 - Scala solution source code (and interim encoder/decoder implementations)

Summary:

The final solution encoder/decoder, HuffmanSimpleKingsPawnOptimal, described in a human readable pseudo-code format.

At a very high level, the number of pawns and their ability to be promoted are the primary constraint of the problem domain. So, a layered approach is used to contextually select an optimal encoding strategy which is then leveraged by the next layer down. 

Details:

Here are the assumptions which were leveraged in the final solution:

1. Both kings are always present in any valid board encoding - even the checkmate state is shown as the final board position prior to the capture of the king
2. Of the 16 pawns present at the start of a game, a maximum of 12 may be promoted
3. Due to the forced pawn promotion rule, there are never any pawns present on the first and last rows of the board

As this is not a description of the journey with which the solution was derived, I will jump straight into describing the decoder.

Decoding the header:

• UseRowDecoder: The first bit the decoder reads is used to select between two pawn decoding strategies; either by row (true) or by column (false)
• WhiteKing: The next 6 bits encode the position of the white king as a linear coordinate value; a value 0-63 inclusive
• BlackKing: The next 6 bits encode the position of the black king as a linear coordinate value; a value 0-63 inclusive
• PawnsToDecode: The next n bits (either 6 or 8 determined by UseRowDecoder) encode for each slice (either row or column) whether one or more pawns are present

Decoding each particular square:

• Index: set to 0 - this is the board squares index which will contain a single integer value of 0 to 63 (inclusive), decode guided by information captured in the header
• StartOfLoop: will decode guided by information captured in the header
• If Index is not equal to WhiteKing, goto IsBlackKing
• Mark the square at the current Index as White King
• Increment Index
• If Index less than 64, goto StartOfLoop else goto EndOfLoop
• IsBlackKing: If Index is not equal to BlackKing, goto IsPiece
• Mark the square at the current Index as Black King
• Increment Index
• If Index less than 64, goto StartOfLoop else goto EndOfLoop
• IsPiece: read a single bit
• If IsPiece is true, goto PieceColor
• Mark the square at the current Index as Empty
• Increment Index
• If Index less than 64, goto StartOfLoop else goto EndOfLoop
• PieceColor: read a single bit - black (0) or white (1)
• SegmentContainsPawns: using both UseRowDecoder and PawnsToDecode from header, figure out if segment for Index must decode for the presence of pawns (true) or not (false)
• If SegmentContainsPawns is false, goto Qbkr
• IsPawn: read a single bit
• If IsPawn is false, goto Qbkr
• Mark the square at the current Index as a PieceColor Pawn
• Increment Index
• If Index less than 64, goto StartOfLoop else goto EndOfLoop
• Qbkr: read two bits
• Mark the square at the current Index as a PieceColor Rook (00), Bishop (01), Knight (10) or Queen (11)
• Increment Index
• If Index less than 64, goto StartOfLoop
• EndOfLoop: input stream should be completely consumed

I know this would be quite a bit easier if I had some images to assist with seeing some of the data and logic. However, those take lots of extra time to generate. So, if/when I get some extra time (and motivation), I will come back and augment this post. Until then, please enjoy the human readable pseudo-code explanation above. :)