Four years ago I wrote a bit of code to satisfy an "itch" to see what it would take to create a chess engine in C# / .NET 1.1. Several thousands of lines of code later, it was done and spent a little time up on MSFT's WinForms Code Hero site. I didn't set out to have it there, mind you - it sort of came up as I was in that fabled "85%" complete zone, and that caused a huge push on my part to get it done within a week to make deadline.
Jump forward to present day: I've opened up the "crypt" and peered inside my code for the first time in ages. Cobwebs and other detritus is strewn about - wow. I actually wrote code like this??
So begins my journey to review my chess control code. I have a couple of reasons to use it as a guinea pig: I know that it has some bugs (there's an infamous one that deals with en passant captures), no unit tests and despite the best of intentions isn't that cohesive internally. It's also .NET 1.1, so I'd like to buff it up to leverage some 2.0 features and eventually 3.5 features.
The bulk of the code resides in a single class, RNChessRulesEngine.ChessRulesEngine, which is augmented by five helper classes for managing other features (click to enlarge):
ChessRulesEngine is a real monster: 3000+ lines of code, 100+ methods, 40+ member variables and types, excluding arrays of types. Not all of this is a cause for concern, however: Validating chess piece moves is a non-trivial exercise that can get complicated fast when we're dealing with bit manipulations, masks, state checks and the like. Nonetheless, I know that this engine can be improved, especially with respect to improving its maintainability. Which makes it an excellent candidate for a case study on refactoring existing code. So, let's move along into the kitchen and see what we'll be using to whip this beast into shape.
The Power Tools
Scrolling up and down through the code, it quickly becomes apparent that despite having written this app, I've long since lost the conceptual mental map for understanding the mechanics. Further, I'm not even sure where to begin. There's a few things I'd like to do off the bat, like improving some algebraic coordinate lookup algorithms with arrays, but that's really nibbling 'round the edges. To be a Code Viking and do Odin's Bidding, I need some power tools:
Some of these you probably already have in your kit - these are the core tools that I'll be using to tackle my ancient codebase, and I'll be referring to them in my examples as we take a stroll down my digital memory lane. I mention them all for the benefit of others who may not be as familiar and curious.
The Motivation: Maintainability and Cyclomatic Complexity
I've mentioned above that I want to improve the chess rules engine to "modernize" it, and part of this necessitates refactoring the unwieldy portions of the code that are... how to put this delicately... a bloody nightmare because they're so damn complicated. I know the routines are complex, because I wrote them. But how can I be sure which methods to tackle first? How do I know if my intuitions have any basis in fact?
To answer this question, I'll be leveraging a concept known as cyclomatic complexity (CC), which is a metric that measures how many decisions are taken within a method. Put another way, it is a count of the following expressions in a method or type:
In general, the higher the CC metric, the more complex your code, the more of a nightmare it will be to maintain.
Of the tools I've listed above, three provide the ability to measure CC: NDepend, Refactor! Pro and Reflector (with the separately downloaded Metrics plugin). I decided to use Refactor! Pro's metrics feature from within Visual Studio to get a handle on what I was in for. This is easy to get at from the menu:
Clicking Metrics brings up a modal dialog with a list of methods and their related CC, lines of code and maintainability measures. I filtered on CC and well, now we see where we have to begin looking to make improvements (all supported by unit tests, of course...)
As I've alluded to above, some complexity can't be avoided in this app - but when we look at the DoPlayerMove, IsCastleLegit, and GetInterceptSquares methods with CC scores of 24, 19 and 19 respectively, this tells us where we can begin our investigation and employ some strategies to get those scores down.
Next Steps: Strategies for Reducing Cyclomatic Complexity
In my next post, I'll be reviewing my next steps for tackling the CC of my top three methods, as well as reviewing some of my other tools that I'll be employing to hack down the problem and get an even greater understanding of what's happening within the rules engine; for this, I'll be demoing a really fantastic tool, NDepend. Stay tuned - oh, and Happy Halloween!