Saturday, April 5, 2014

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)


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. 

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. :)

Monday, March 24, 2014

Chess Coding Challenge - Part 3 - Scala solution source code (and interim encoder/decoder implementations)...

Part 1 - How I Leveraged Scala and FP to Find a Solution
Part 2 - Scala infrastructure source code (and two encoder/decoder implementations)
Part 4 - Solution in Human Readable Pseudo-code


The Scala code (dropbox public folder share - I STILL SO love this) expanding the set of encoder/decoders to include the solution (and interim steps on the path to the final solution). Included are the Coder implementations; HuffmanSimpleKingsPawnOptimal (solution at 167 bits) and the interim solutions of HuffmanSimple, HuffmanSimpleKings, HuffmanSimpleKingsPawnRows, HuffmanSimpleKingsPawnColumns

I'm still finding it difficult to make time to progress this project. I am glad to finally have had the time to sit down and get the solution coded up and available. To explain the final solution is going to take more time than I have available this evening. Suffice to say, it is actually a layered set of sub-solutions. And the entire thing is predicated pawns as the primary constraint, and then on specific rules around pawn promotion upon we (Bill and I) optimized. I will return here with one final post detailing the solution in an English (non-code) explanation. I'm committed to making it happen, but...due to circumstances in my personal life, it will likely be another two weeks before that post happens.

This has been very fun, though. I don't have the motivation right now to redo it in Java. That might change in a month or two. If it does, I will write it up and create a post dedicated just to it.

For those who have continued to have the patience to follow this for the last two months, thank you for playing along with me! I cannot wait to see Jim Nelson's and David Stafford's solutions.

Thursday, February 27, 2014

Chess Coding Challenge - Part 2 - Scala infrastructure source code (and two encoder/decoder implementations)...

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

The Scala code (dropbox public folder share - I SO love this) defining the infrastructure for experimenting with different encoder/decoder pairs. Included the first two coder implementations; SquareBits4 (constant 256 bits) and PieceExistsBitMapPlusSquareBits4 (max of 192 and reduces by four bits for each piece captured)

Honestly, I don't have time to go into much detail this evening. So, below is the 1,000 foot view. The root folder contains two folders; DataSets and eclipse_workspace. The DataSets folder contains a text file containing the "test" boards. It ought to be mostly self-explanitory. The eclipse_workspace folder contains the Eclipse .project. I'll reference that a bit later. All of the Scala files all stored in a single package; org.public_domain.chess_coding_challenge:

  1. This is a fantastic mechanism for "forming" code dynamically. The code you see there is recompiled and run every time you save the file. All the text in the columns to the right are the output from each of the lines. This way of developing is beyond awesome.
  2. Main.scala: This is the root class that is run. It is the Scala analog to any Java class containing a public static main method.
  3. Definitions.scala: All interface definitions. Everything can be understood in terms of the interfaces.
  4. Implementations.scala: All the factories which instantiate implementations of the interfaces in Definitions.scala.
  5. ConvertBits.scala: A helper class to facilitate twiddling bits.
  6. Coders.scala: This is where the actual encoder/decoder pairs are implemented. And this is where the SquareBits4 and PieceExistsBitMapPlusSquareBits4 implementations are defined.
If you are interested in the minimum fuss way of checking this out, I would highly recommend downloading the free Eclipse + Scala-IDE as it is entirely Scala self-contained; i.e. no need to download various Eclipse and Typesafe installs and work to get them all configured and working. You do need to have (the free) JDK7 installed first as Eclipse and Scala both depend completely upon it. You can also use JDK6, but I don't recommend it both for security as well as performance reasons.

Once you have Eclipse installed and have started it...:

  1. Eclipse will want to be pointed at an Eclipse Workspace - select the eclipse_workspace folder (using "Browse" to navigate to it if needed)
  2. Once Eclipse comes up, it will be blank - using the main menu, select File/Import
  3. On that dialog, open the General item which will show a list of items
  4. Select the item "Existing Projects into Workspace" and click "Next"
  5. Next to the "Select root directory", select "Browse" and immediately hit "Okay"
  6. Click "Finish" and the project will be loaded and ready to explore

Have fun! And please let me know if you end up experimenting with writing some encoder/decoder pairs yourself. I am hoping to find more time this weekend to post at least the initial Huffman encoding that launched me onto this tangent/fixation/whatever on Super Bowl Sunday!

Sunday, February 23, 2014

Chess Coding Challenge - Part 1 - How I Leveraged Scala and FP to Find a Solution

NOTE: I have no idea how many parts this series will end up being. It will be as many parts as are needed to tell the story of how this problem came to me, how it tortured me for weeks, how it called me to use so many of the skills I have learned over the +32 years I have been programming, developing and software engineering. As I write new parts, I will be sure to come back here and forward reference them.

Part 2 - Scala infrastructure source code (and two encoder/decoder implementations)

Part 3 - Scala solution source code (and interim encoder/decoder implementations)

The initial problem statement of the Chess Coding Challenge, the years since I first heard it as a job interview question and the numerous Aha...pause...Ah-Shit moments which have followed me right through to writing this blog post.

A couple of years ago, Bill Strahan and I were meeting (like we do every Wed. night for the last 10 years) and he mentioned one of the most notable moments he had ever had when going on job interviews. He said that after they had done all the preliminaries and other such stuff, they asked him a simple question regarding regarding Chess. The problem statement was intentionally simple in context, but belied a very subtle set of below the surface complications. As best as I can remember Bill's telling, here's the problem statement:

  1. Given a picture of an 8x8 chessboard from any valid chess game, what is proveably the absolute minimum number of bits required to losslessly encode all the pieces?

Bill paused and let me mull on it. And then he said that he had gotten a solution to just 176 bits. I mulled for a minute and then reached for my trustiest of tools, RLE (Run Length Encoding). I was certain it would give me the smallest value. And for the starting board, it looked awesome. Bill and I then started discussing specific board positions where RLE might not be as efficient. He then described his solution (which will be described in a later post) and I could see how it worked. He pointed out that he thought there was something more that he could do with the inefficiencies around pawns, but just had not spent any more time on it. We played with the problem space for another couple of minutes and then dropped it.

I picked it up a week or so later. However, my interest in Chess has waned over the years. Once I had learned Go (from David Stafford in 1988), I drifted away from Chess. This problem was slightly more interesting from a computational perspective, though. Since RLE didn't seem to work, I dropped the problem.

Jump ahead a year or so. I've discovered Scala and FP. I am enjoying my experience of lazily learning both. Then, the free Coursera MOOC (Massive Online Open Course) “Functional Programming Principles in Scala” became available with Scala's creator (Martin Odersky) teaching it. I jumped in wholeheartedly (and aced it which included turning in every assignment on-time). During that course, one of the techniques explored is Huffman encoding. This was the first I had ever really explicitly seen this kind of encoding. I enjoyed doing the problem they provided (related to storing words, I think). A day or two after completing the lesson, Bill's interview chess problem just jumped into my mind again. I immediately saw how I could use Huffman encoding to quickly encode the chess board. So, in less than 10 minutes, I reworked the code to encode any chess board. And sure enough, it encoded it in 162 bits, way below Bill's 176 bit solution.

I was so damn elated. I texted him. We got together and showed him the solution. At first he thought it was great. Then, he asked me what would happen with pawn promotions. I said I didn't think it would matter much in typical games. That's when he clarified and said that the problem domain wasn't just typical/normal/average games. It was any game board that was reachable from a valid starting chess board with any legal sequence of moves. A quick check of the math where all 16 pawns were promoted to queens ruined my simple Huffman encoding approach. ARGH!

And so the problem went away for another while...a long while. I happily wrote much Scala/FP and Java code in the intervening time.

Then, on Super Bowl Sunday this year (Feb/2nd), I had just finished a first draft of a Google Document on creating a “Better Scala” (which wouldn't let me sleep the night before after waking to hit the restroom and then keep me up to tell me all about it...for hours...UGH). Due to the a$$whoopin the Seahawks were giving the Broncos, I barely had any attention on the TV.

And that's when this damn Chess problem showed up again. I have NO IDEA why it showed up. But it did. Just popped into my mind along with a new variation on the previous Huffman solution. And this time, it was convinced it had found a solution beating Bill’s.

So, I opened Notepad and just began typing whatever came. I wasn't going to be left alone until I got it out of my head. I had just learned that with my “better Scala” experience. Once I finished, it looked like I consistently got it under 168 bits (21 bytes, one byte less than Bill's solution). I texted Bill and let him know. The plan was to discuss it on Wed. night. The high I felt from resolving the problem was so awesome! I wasn’t able to pay it much attention on Monday. However, it was on my mind as I drove into work on Tuesday morning.

So, Tuesday morning, February 4th, I decided to share my problem with all my software engineering friends on Facebook. It looked like this:
Jim O'Flaherty is facing an interesting "programming" problem:
Given a picture of an 8x8 chessboard from any valid chess game, what is proveably the absolute minimum number of bits required to losslessly encode all the pieces?

{fps}Any guesses on this? And if you guess, please explain how you got to said number of bits. Thank you! I'll wait awhile and then post the answer at which I arrived, and how I got there. The only clue I'll give is I got it under 192 bits (24 bytes).

I then wrote the first comment attempting to offer clarification for all the questions I knew might be coming:
Just as clarification, this is just the pieces on a chessboard that can be arrived at from a valid sequence of moves starting from a standard piece layout for a normal chess game. The encoding does not have to worry about temporal aspects of the game like color to move, castling, en passant, etc. It does have to account for pathological states that arise from maximum pawn promotion (which can be to any valid piece; rook, knight, bishop or queen).

As I was (falsely) convinced I had a solution well under 168 bits and wanted to see if anyone else could find one less than that. I made the post at the beginning of the work day. I then dropped off of Facebook until that evening. Once I got home and logged in, I found that the comment thread on the post had taken on a life of its own. It was awesome seeing all of the different kinds of thoughts about how to encode it.

David Stafford (a friend with whom I competed with when we first got our home computers back in 1981) had asserted in one of his comments that he had his down to 174 and that he thought that an consistent efficient encoding couldn't be variable. And that a variable size encoding couldn't be efficiently placed into a fixed bit window. That made me begin to doubt my solution.

As I went to bed that night, right before I went to sleep, a pathological board layout appeared in my mind. I then couldn't sleep and had to prove that it broke my newly created algorithm. It did. That was one hell of a downer.

I got up for work on Wednesday morning and my brain played with different ways to play with encoding. This began a cycle of finding an encoding that would work great on the previous case's pathological case but then have its own unique pathological case. I did this cycle at least 6 times.

Being it was Wednesday, that evening Bill and I met like we have every week for +10 years. I asked him about his solution again. We stepped through it. And it really did encode the initial board very small. However, at this point I was rapidly becoming an expert in thinking up pathological cases which broke my algorithms. I took a moment to evaluate his algorithm and then asked him to encode what I thought might be a pathological case for his. Sure enough, it pushed well past the 176 he had thought was the max. We then discussed it. I decided to show him my (now defunct) last solution. We talked through it. Then, he realized that we could use part of mine with part of his and come up with a better solution. We worked through it and got it to 172 bits, 2 bits better than David Stafford's solution. We then went about trying to find the pathological case for this new algorithm. The ones we found were consistently encoding below 172.

When I got home that night, I wrote on the Facebook thread about getting to 172 bits. David Stafford had announced his having gotten down his solution down to 171 bits. I was tired and just wanted to get this damn problem out of my head. So, I committed to writing up then new 172 bit solution Bill and I worked through on my blog (this series of posts) and detailing the solution.

Again, right before going to sleep, I thought of a pathological case for the new solution. Sure enough, it went up to 176. That was so damn annoying. I was able to let go a bit for the rest of Thursday and Friday. But, Friday night, my brain wouldn't stop and came up with another variation of the last solution Bill and I had. It worked great to resolve the previous pathological condition, but I immediately set about trying to find the pathological condition for this new algorithm. Sure enough, it had one, too, which topped out at over 180.. It was pretty damn depressing. It was not my favorite weekend.

And then while getting ready for work and just before walking out the door on Monday morning, my brain surprised me with a new solution. However, this one was going to require more than just mental imagining to a conclusion. I was going to have to write code and work through test cases to validate each step in the process. And that was going to take some time.

That Wednesday night, Bill wasn't available due to a conflict. So, I came home and then started working up the solution in Scala (which is what I will be covering in the next several parts). The coding in Scala and FP didn't take long. It was all the pauses to figure out ways to write out test cases, get those sucked in and testable, etc.

I was able to get all the infrastructure completed. And I was able to do the simplest 256 and 192 bit cases. However, I had to stop as I had run out of time. Naturally, Murphy showed up and ensured I didn't get to work on it again...for a freakin week. Between work, Valentine's day and various life events, I didn't get to work on it again for a whole week.

During that week, I then made the following lateral-thinking discovery (well, I it was more making explicit what I already had been doing implicitly):
To solve this problem, I had to stop looking for chess boards arising from two players competing to win a chess game. And instead, I had to begin to look at it as someone intentionally playing valid moves on a chessboard to produce an end state which attempted to break whatever the specific encoding algorithm was being used to capture said state.

When Bill and I met, I explained this to him. I was able to show Bill the Scala and FP code I had written the following Wednesday. But, we didn't have time for me to finish that code. Again, too many real life things happening.

On Thursday (Feb/20th), I finally got the time to finish up all the remaining implementations and ran the resulting code to produce a huge number of results. I took the results, dropped them into Google Spreadsheet. After playing with the numbers, I found a bug in the coders (after having to hand walk through the encoding/decoding to make sure I wasn't losing my mind). I then worked through all the coders to ensure I hadn't missed any implementation details. And then I stepped through each of the test cases (most of which were pathological cases for various coder algorithms).

I then reran the results, dropped them into Google Spreadsheet and finished my analysis. While it is possible I will think of another pathological case, I now sincerely doubt it. But more on why I think that in a later post. {smirk}

The final result – I now have something under David Stafford's 171 bits (for which he has not yet shown his solution).

Still Primarily Using Java at Work (but Scala is finally begining to catch on at work)...

I celebrated my third year of learning Scala and FP (Functional Programming) in January. Looking back, I am VERY happy with both how much Scala and FP skill I have acquired. Much more importantly, though, is how dramatically it has improved my Java skills in completely unanticipated ways. I now have three small projects built in Scala (none in production yet, but all three are used in production support).

Honestly, Scala has ended up being a bit more convoluted trying to get something simple like Scalatra up and offering a simple REST service. The steps required to get to a base project working state in Eclipse are just too involved for me to honestly suggest/prod to my Java software engineering peers to resolve. As such, I am still reluctant to actually get a full on Scala server built up in my IT production environment. There's no problem for me to do it. It's just that I would be the only one with the skills to maintain it. And that's a problem since I now work +12 projects and have to be able to jump into any one of them at a moment's notice.

That said, where I have used Scala, it has been heaven compared to Java. I have a data feed loader which is a very typical ETL (Extract/Transform/Load) problem. And Scala has been just awesome in assisting with finding and updating just the delta between the data feed inputs and the resulting read only DB. I also have a weekly report I must run which details activities that are failing against a production system. The failures are reported as emails which collect in Outlook. It was less than 3 hours work to write a quick command line app which takes the emails at text and turns them into a tab delimited output stream that drops nicely into Excel. The last one is a Java code generator for a home-grown caching system. I've essentially reproduced most of the value of Scala case classes for use in Java. And that is proving to be invaluable as the core system this is initially being implemented against has +40 caches. That's a HUGE amount of Java boilerplate I will no longer have to manually maintain.

In summary, Scala and FP have elevated my productivity as an IT Architect Software Engineer substantially. And by substantially, I mean over 100% with no exaggeration. It's so fulfilling to be able to convert business problems to business value so much faster and flexibly than I was able to do with Java just three years ago.

Sunday, March 18, 2012

Effective Scala video with Josh Suresh

Just saw Josh Sueresh's talk posted on YouTube identifying "Effective Scala" (not a book, just a video) much of which is in his almost released book, "Scala in Depth". Awesome stuff!

In other news, Scala is quickly promoting from Trial to Adopt in the ThoughtWorks industry survey (item 98 in the image to the right). This is a HUGE deal in terms of future development, contract and job opportunities. I couldn't be happier to be riding this wave. It's going to be as good or better than even the Java wave I rode in 1998-2006. Yeeehaaa!

Thursday, March 8, 2012

What draws me to Scala...

I just ran across this article, "Comparing Java and Scala’s Expressiveness". It so succinctly describes how I feel as I learn Scala. It's not just the reduced boilerplate. It's something about feeling like I am doing more real software engineering work as opposed to a huge amount of paperwork (boilerplate) with a tiny amount of actual software engineering!