Welcome back to the 4.5^th part of my multi-partite series that traces my progress into refactoring some old code that implements a chess board control – specifically, the rules engine that referees piece movement.  Unfortunately, I’m a bit late with this as some life events intervened, and as a result I’ve had to abbreviate what I wanted to do with this installment.  Hence, version 4.5!

So far, we’ve covered a bit of ground getting the stage set for aggressive refactorings with source control, code analysis tools, unit testing and refactoring aides.  We’ve restructured our solution, moved test projects around, uploaded them to a web-based repository for sharing and devised some tests to exercise the engine across some valid and invalid moves.

Today, we’re going to look at a helper object in the engine (formerly FENAnalyzer, now FENTranslator) that is responsible for setting up the chessboard in a variety of states using a specially-formatted string.  The motivation for examining this object is to be able to test the rules engine with more complex, in-progress game states without having to run-through an entire set of moves as we’ve done with the unit tests for replaying a complete game.

Catching Up…

Before I get too far, some quick notes on changes to the source that you might notice.  If you’re following along at home, I recommend deleting your working copy and pulling down the latest version of the solution – we should be at revision 32 right now:

1. There’s a new solution folder called Tests where I’ve re-located RNChessBoard.RNChessRulesEngine.Tests, and where all future NUnit test assemblies will be stored.
2. I’ve updated the ChessRulesEngineTestFixture class using the Extract Superclass refactoring to create BaseChessRulesEngineTestFixture which allowed me to move some common methods for running the game-move replay methods up the inheritance chain and make them more widely-available.  This is one of the most common refactorings I do when writing unit tests – sometimes, I just cut out the middle-man and write a base class to start off.
   
   I also introduced a new method into this base class for replaying a series of multiple games using jagged-arrays called ReplayTestGameBattery, and added some new replay arrays for testing black and white pawn moves (BlackPawnTestMoves and WhitePawnTestMoves).
3. Renamed FENAnalyzer to FENTranslator to better reflect its dual purpose (ie. constructs and interprets FEN strings)
4. Did some minor renaming and cleaning up of the solution after moving things around – you’ll see this under the imaginative comments of “clean up on aisle x”.

Building new tests with Forsyth-Edwards Notation

While crafting the test arrays for the black and white pawn openings, I found myself wanting to construct mid-game scenarios to enable faster, more precise testing – say, for an emerging en-passant capture.  As it stands, I can only do this by constructing an array of sequential moves to replay the scenario – I wanted to jump right in with a preset board state.

Fortunately, I had already built this exact kind of functionality into the rules engine oh-so-long ago with a helper object called FENTranslator.  This class implements an engine that translates a simple string in Forsyth-Edwards Notation (FEN) into a basic array that the rules engine can then use to set piece positions and game states;  conversely, it can also create a FEN string from a current board set up.  Here’s how it’s used in the WinForms control to set the default start game position:

Quick FEN Primer

FEN strings are comprised of six space-delimited fields that represent the current position of pieces on the board, side to play, castling availability, en passant state and half and full moves.  The first field defines the eight ranks of the chessboard, with the black side pieces in lower-case letters (rook, knight, bishop, queen, king and pawn) and the white in upper-case;  squares that have no pieces are represented by numbers.  The FEN notation for the start of a game would be:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

For example, after the typical white-side queen’s pawn opening, the FEN notation would be:

rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b KQkq - 0 1

Black’s response with his king-side knight to F6:

rnbqkb1r/pppppppp/5n2/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 2

The “KQkq” markers indicate whether either side has used their sole opportunity to castle king-side or queen-side.  For example, if white castles king-side, here’s how the board state would be represented in FEN:

rq2kbnr/pppbpppp/2n5/3p4/2BP4/4PN2/PPP2PPP/RNBQ1RK1 b kq - 0 5

Note that white’s indicator is removed, while black’s remains.  In order to better see how the curtrent board’s FEN changes, I’ve added an additional textbox to our test app that calls the WinForm control’s GetCurrentPositionAsFEN() method, which in turn uses the FENAnalyzer object to generate the string:

Testing the FENTranslator Object

This turned out to be a little easier than I thought:  Initially, I was quite concerned about the edge and corner cases  that this object might present since the typical FEN string has a lot of potential to be malformed.  As it turns out, I accounted for this with some regular expressions.

First Tests – Not Null and Default States

I began my testing by creating the FENTranslatorTestFixture and did the routine Assert.IsNotNull check, and then followed with a more ambitious test containing several assertions to validate the default state for the FENTranslator object.  This object can be instantiated one of two ways, with either a FEN string or an array.  To begin, I needed to supply the the object with a 64–element integer array representing the start state of the board:

   27 private static readonly int[] START_BOARD_ARRAY = new int[64]

   28     {

   29         -4,-2,-3,-5,-6,-3,-2,-4,

   30         -1,-1,-1,-1,-1,-1,-1,-1,

   31         0,0,0,0,0,0,0,0,

   32         0,0,0,0,0,0,0,0,

   33         0,0,0,0,0,0,0,0,

   34         0,0,0,0,0,0,0,0,

   35         1,1,1,1,1,1,1,1,

   36         4,2,3,5,6,3,2,4

   37     };

Negative numbers represent the black pieces, positive numbers white and zeroes indicate an empty square – in practice, the rules engine maintains the current board state with a similar array, so this is a practical setup step.  My test, New_ValidFENString_NotNull instantiates the FENTranslator with this array and checks each of the object’s default states to ensure they are correct:

   57 [Test]

   58 public void New_ValidFENString_NotNull()

   59 {

   60     FENTranslator  fen = new FENTranslator (FEN_START_WHITE);

   61 

   62     Assert.IsNotNull(fen, "FENBuilder failed to instantiate.");

   63     Assert.IsTrue(fen.WhiteKingsideCastle, "Initial white king-side castle state is invalid.");

   64     Assert.IsTrue(fen.WhiteQueensideCastle, "Initial white queen-side castle state is invalid.");

   65     Assert.IsTrue(fen.BlackKingsideCastle, "Initial black king-side castle state is invalid.");

   66     Assert.IsTrue(fen.BlackQueensideCastle, "Initial black queen-side castle state is invalid.");

   67 

   68     Assert.AreEqual(1, fen.FullMoveNumber, "Initial full move number is invalid.");

   69     Assert.AreEqual(0, fen.HalfMoveClock, "Initial half-move number is invalid.");

   70     Assert.AreEqual(PlayerTurn.White, fen.ActiveColor, "Initial player turn is invalid.");

   71 

   72     Assert.IsNotEmpty(fen.ChessBoardArray, "Initial chessboard array property is invalid.");

   73     Assert.AreEqual(START_BOARD_ARRAY, fen.ChessBoardArray, "Initial chessboard array state is invalid.");

   74 

   75     Assert.AreEqual("-", fen.EnPassantTargetSquare, "Initial En Passant target square is invalid.");

   76 }

I added and tested each Assert individually to check my board state – they all passed, so I now had a good baseline regression test that I could move forward from.  Next, I decided to focus on tests that instantiated the object with a FEN string as I thought there would be a lot more work to do here.  To keep things brief, I’m going to review just a few of the tests – you can pull down the source to see more detail and my thinking process at the time.

Next Test – Inverse Relationships with ToString()

One of Hunt & Thomas’ unit testing maxims suggests that you should be able to validate your code by checking inverse relationships.  In other words, is there a way to validate an object’s methods using its output as an input – in our case, this could be done by instantiating the object with the array used in New_ValidFENString_NotNull and call the object’s ToString() implementation:

   18 private const string FEN_START_WHITE = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";

   
   78 [Test]

   79 public void ToString_ValidStartFEN_Equality()

   80 {

   81     FENTranslator  fen = new FENTranslator (FEN_START_WHITE);

   82     Assert.AreEqual(FEN_START_WHITE, fen.ToString(), "Invalid FEN string was returned.");

   83 }

Line 18 shows the string constant I’m using to test for a valid default FEN string;  by calling ToString() on a freshly-instantiated FENTranslator object, there should be no difference – and indeed this test passes.  Of course, this test does suggest that we need to look at some edge cases for instantiation using an array - we’re placing a lot of trust in the ToString() method – but this will do as a backstop for the moment.

Expected Exceptions Tests

A good portion of the tests I added address concerns around instantiating the object with a malformed FEN string.  To support these tests, I un-commented some lines of code in the ImportFEN() method to throw an ArgumentException when it detects fewer than six space-delimited fields:

  205 string[] fenFields = FENString.Split(new char[] {' '},6);

  206 if(fenFields.GetLength(0) < 6)

  207 {

  208     throw new ArgumentException

  209     ("FEN input string does not contain the required six space-delimited fields.");

  210 }

I tested for this using the ExpectedException attribute for my unit test:

   85 [Test,ExpectedException(typeof(System.ArgumentException))]

   86 public void New_BadFENString_NoSpaceDelimiters_ArgumentException()

   87 {

   88     string testFEN = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNRwKQkq-01";

   89     FENTranslator  fen = new FENTranslator (testFEN);

   90 }

But this isn’t quite right – it’s not so much the argument that’s the exception, but the format.  Accordingly, I modified the throw on line 208 to use a FormatException instead and updated my tests.

Next, I did some minor refactorings within the PopulateBoardArrayFromFEN() method to throw a FormatException when presented with a malformed FEN rank string - things weren’t nearly as expressive or complete as I wanted.  So, we went from this:

  261 int sqIndex=0;

  262 for(int rankIndex=0; rankIndex<fenRanks.GetLength(0); rankIndex++)

  263 {    

  264     string rank = fenRanks[rankIndex];

  265     if(!CheckFENRank(rank))

  266     {

  267         throw new ApplicationException

  268           ("The FEN piece placement field contains an incorrect rank string:\n" +

  269            "[" + rank + "]");

  270     }

to this:

  271 int sqIndex=0;

  272 for(int rankIndex=0; rankIndex<fenRanks.GetLength(0); rankIndex++)

  273 {    

  274     string rankString = fenRanks[rankIndex];

  275     if(!IsFENRankStringValid(rankString))

  276     {

  277         string rankException = "The FEN string at rank {0} is not well-formed: [{1}]";

  278         throw new FormatException(string.Format(rankException, rankIndex, rankString));

  279     }

I tested this fragment change in several tests, eg. New_BadFENString_BadBlackRank8_abcdefgh_FormatException, New_BadFENString_InvalidRank3_SpaceCount9_FormatException, New_BadFENString_BadBoardDelimiters_FormatException, etc.

Of course, this led to refactoring the IsFENRankStringValid – just to tighten things up a little, from this:

  446 private bool CheckFENRank(string FENRankString)

  447 {

  448     // Analyze FEN rank for space count

  449     MatchCollection mcSpaces = Regex.Matches(FENRankString,"[1-8]");

  450     int spaces=0;

  451     foreach(Match m in mcSpaces)

  452     {

  453         spaces+=int.Parse(m.Value);

  454     }

  455     if(spaces>8) return false;

to this:

  455 private bool IsFENRankStringValid(string FENRankString)

  456 {

  457      // Parse the FEN string ranks for empty squares

  458      MatchCollection mcEmptySquares = Regex.Matches(FENRankString,"[1-8]");

  459      int emptySquareCount = 0;

  460      foreach (Match m in mcEmptySquares)

  461        emptySquareCount += int.Parse(m.Value);

  462 

  463      if(emptySquareCount > 8) return false;

Incidentally, this method does all the heavy-lifting for validating the FEN string ranks that I was concerned about – by leveraging the Matches method, I can iteratively apply a pattern against a string which makes validating the FEN empty squares and piece positions a snap.

Next Steps:  More edge tests, boundary tests, state tests

So far, we’ve made some good progress testing the FENTranslator object in this post, and learned a little about Forsyth-Edwards Notation along the way, but there’s obviously more to do.  As I’ve mentioned above, there’s room to ensure the values boundaries for the test arrays are within acceptabled ranges (ie, -6 to 6), that the FEN strings for castling and en passant are working, etc.  Ultimately, though, the FENTranslator object wasn’t intended to be an engine as much as a helper class, which I need to keep in mind as I work through refactoring it.

Once I’ve added enough edge/corner case tests to bolster my confidence in the FENTranslator, I can return to constructing additonal regression tests for validating piece movements and their outcomes in the rules engine before moving into any refactoring of that code.  While this may all seem a bit tedious, it is necessary to ensure we don’t make any fatal changes that would break the engine.

As always, you can obtain the latest release of the codebase from http://rnchessboardcontrol.googlecode.com/svn/trunk to see what’s been accomplished so far and to monitor progress as we go along.  Cheers!

It’s funny in an ironic and so very, very wrong kind of way.

Via dotNetSlackers, an all-too-familiar story: If only we'd used ANTS Profiler earlier... we would have had a shot at the $2 million cash prize!.  The familiar part is how code profiling seems to always be a last consideration for developers – not the $2M part, obviously!

Written by a member of the Princeton DARPA Grand Challenge Team (the competition where entrants build driverless vehicles that must successfully negotiate a pre-set course), the post describes how an apparent “memory leak” in their .NET code was causing their test vehicle to literally crash:

We were unique among the teams in the finals, in that we used stereo vision, as opposed to scanning lasers, to detect and range obstacles. All in all, we wrote 10,000 lines of C# code to drive the cars.

In the finals, we ran for 9 miles before succumbing to a memory leak in the obstacle-detection code. Actually, most of our code is written in garbage-collected C#, so it wasn't a memory leak per se, but it wasn't until two weeks later that we discovered the true problem.

The nature of the problem?  Objects that while “deleted”, still maintained subscriptions to events, thus causing their heap to blow chunks.  How did they figure this out?  By profiling their code to see how it was working in real-time:

One of our team members downloaded the 14-day trial of ANTS Profiler, and we ran it on our car's guidance code. We profiled the memory usage and saw the obstacle list blowing up. How could this be? We called "delete" on those old obstacles! To our amazement, it was only minutes before we realized that our list of detected obstacles was never getting garbage collected. Though we thought we had cleared all references to old entries in the list, because the objects were still registered as subscribers to an event, they were never getting deleted.

We added one line of code to remove the event subscription and, over the next three days, we successfully ran the car for 300 miles through the Mojave desert.

Definitely a testament to the power of profiling!

Personally, I prefer AQTime to ANTS as the latter in my experience doesn’t profile SharePoint applications very well – if at all.  It also has an array of reports and dashboards that I like, eg. callgraphs, top-10 hit counts, longest methods to execute (with and without children) and more.  Nonetheless, it’s well worth trying the free versions of each on your own code to see how they work and what you prefer. 

To me, profiliers are the best investment you can make in your tools, outside of an IDE and refactoring aids.

Via Bink.nu:

• Microsoft .NET Framework 2.0 SP1
• Microsoft .NET Framework 3.0 SP1

Each has links for the 32 and 64 bit releases – get ‘em while they’re hot.

I’ve noticed some Google queries in my referrer’s log lately from folks looking to maintain their users’ scroll position after a postback.  This is a “classic” ASP.NET issue, and one that wasn’t handled very well in .NET 1.1 with an IE-specific page directive (somewhat ironically-named “SmartNavigation”) that kacked most of the time and caused sites to lock-up.

‘Good news is that under 2.0 this has been resolved with the MaintainScrollPositionOnPostback page directive which is designed to automagically track your user’s position on the page and snap right back to it after a round-trip to the server.  Here’s how I implemented this for dasBlog’s CommentView.aspx page:

When a user enters a comment to a post and fills out the reCaptcha challenge words, after postback the page will move to show the last comment entered.

How does it work?

Basically, by injecting some client-side Javascript that associates the web form’s OnSubmit handler with a function that’s supplied in the WebResource.axd library that tracks the user’s X/Y position on the page, and then restores it after postback.  For a deep-dive on how the MaintainScrollPositionOnPostback directive works on the client and server side, see Scott Mitchell’s piece on the 4Guys site, Client-Side Enhancements in 2.0.