Stories about Software


TDD and Modeling a Chess Game

For the first post in this series, I’m responding to an email I received asking for help writing an application that allows its users to play a game of chess, with specific emphasis on a feature in which players could see which moves were available for a given piece. The emailer cited a couple of old posts of mine in which I touched on abstractions and the use of TDD. He is at the point of having earned a degree in CS and looking for his first pure programming job and it warms my heart to hear that he’s interested in “doing it right” in the sense of taking an craftsmanship-style approach (teaching himself TDD, reading about design patterns, etc).

Modeling a game of chess is actually an awesome request to demonstrate some subtle but important points, so I’m thrilled about this question. I’m going to take the opportunity presented by this question to cover these points first, so please bear with me.

TDD does not mean no up-front planning!

I’ve heard this canard with some frequency, and it’s really not true at all (at least when done “right” as I envision it). A client or boss doesn’t approach you and say, “hey can you build us a website that manages our 12 different kinds of inventory,” and you then respond by firing up your IDE, writing a unit test and seeing where the chips fall from there. What you do instead is that you start to plan — white boards, diagrams, conversations, requirements definition, etc.

The most important outcome of this sort of planning to me is that you’ll start to decompose the system into logical boundaries, which also means decomposing it into smaller, more manageable problems. This might include defining various bounded contexts, application layers, plugins or modules, etc. If you iterate enough this way (e.g. modules to namespaces, namespaces to classes), you’ll eventually find yourself with a broad design in place and with enough specificity that you can start writing tests that describe meaningful behavior. It’s hard to be too specific here, but suffice it to say that using TDD or any other approach to coding only makes sense when you’ve done enough planning to have a good, sane starting point for a system.

Slap your hand if you’re thinking about 2-D arrays right now.

Okay, so let’s get started with this actual planning. We’ll probably need some kind of concept of chess pieces, but early on we can represent these with something simple, like a character or a chess notation string. So, perhaps we can represent the board by having an 8×8 grid and pieces on it with names like “B_qb” for “black queen’s bishop.” So, we can declare a string[8][8], initialize these strings as appropriate and start writing our tests, right?

Well, wrong I’d say. You don’t want to spend your project thinking about array indices and string parsing — you want to think about chess, chess boards, and playing chess. Strings and arrays are unimportant implementation details that should be mercifully hidden from your view, encapsulated snugly in some kind of class. The unit tests you’re gearing up to write are a good litmus test for this. Done right, at the end of the project, you should be able to switch from an array to a list to a vector to some kind of insane tree structure, and as long as the implementation is still viable all of your unit tests should be green the entire time. If changing from an array to a list renders some of your tests red, then there’s either something wrong with your production code or with your unit tests, but, in either case, there’s definitely something wrong with your design.

Make your dependencies flow one way

So, forget about strings and arrays and let’s define some concepts, like “chess board” and “chess piece.” Now these are going to start having behaviors we can sink our TDD teeth into. For instance, we can probably imagine that “chess board” will be instantiated with an integer that defaults to 8 and corresponds to the number of spaces in any given direction. It will also probably have methods that keep track of pieces, such as place(piece, location) or move(piece, location).

How about “chess piece?” Seems like a good case for inheritance since all of them need to understand how to move in two dimensional spaces, but they all move differently. Of course, that’s probably a little premature. But, what we can say is that the piece should probably have some kind of methods like isLegalMove(board, location). Of course, now board knows about piece and vice-versa, which is kind of icky. When two classes know about one another, you’ve got such a high degree of coupling that you might as well smash them into one class, and suddenly testing and modeling gets hard.

One way around this is to decide on a direction for dependencies to flow and let that guide your design. If class A knows about B, then you seek out a design where B knows nothing about A. So, in our case, should piece know about board or vice-versa? Well, I’d submit that board is essentially a generic collection of piece, so that’s a reasonable dependency direction. Of course, if we’re doing that, it means that the piece can’t know about a board (in the same way that you’d have a list as a means of housing integers without the integer class knowing about the list class).

Model the real world (but not necessarily for the reasons you’d think)

This puts us in a bit of an awkward position. If the piece doesn’t know about the board, how can we figure out whether it’s moving off the edge of the board or whether other pieces are in the way? There’s no way around that, right? And wasn’t the whole point of OOP to model the real world? And in the real world the pieces touch the board and vice versa, so doesn’t that mean they should know about each other?

Well, maybe we’re getting a little ahead of ourselves here. Let’s think about an actual game of chess between a couple of moving humans. Sure, there’s the board and the pieces, but it only ends there if you’re picturing a game of chess on your smart phone. In real life, you’re picking pieces up and moving them. If you move a piece forward three spaces and there’s a piece right in front of it, you’ll knock that piece over. Similarly, if you execute “move ahead 25 spaces,” you’ll drop the piece in your opponent’s lap. So really, it isn’t the board preventing you from making illegal moves, per se. You have some kind of move legality calculator in your head that takes into account what kind of piece you’re talking about and where it’s located on the board, and based on those inputs, you know if a move is legal.

So, my advice here is a little more tempered than a lot of grizzled OOP veterans might offer. Model the real world not because it’s the OOP thing to do or any dogmatic consideration like that. Model the real world because it often jolts you out of a code-centric/procedural way of thinking and because it can make your conceptual model of the problem easier to reason about. An example of the latter is the idea that we’re talking about pieces and boards instead of the 2-day arrays and strings I mentioned a few sections back.

Down to Business

I’m doing this as an exercise where I’m just freewheeling and designing as if I were implementing this problem right now (and just taking a little extra time to note my reasoning). So you’ll have to trust that I’m not sneaking in hours of whiteboarding. I mention this only because the above thinking (deciding on chess piece, board, and some concept of legality evaulator class) is going to be the sum total of my up-front thinking before starting to let the actual process of TDD guide me a bit. It’s critical to recognize that this isn’t zero planning and that I actually might be doing a lot less up front reasoning time than an OOP/TDD novice simply because I’m pretty well experienced knowing how to chart out workable designs from the get-go keeping them flexible and clean as I go. So, without further ado, let’s start coding. (In the future, I might start a youtube channel and use my Pluralsight setup to record such coding sessions if any of you are interested).

First of all, I’m going to create a board class and a piece class. The piece class is going to be a placeholder and the board is just going to hold pieces, for the most part, and toss exceptions for invalid accesses. I think the first thing that I need to be able to do is place a piece on the board. So, I’m going to write this test:

First of all, I’ll mention that I’m following the naming/structuring convention that I picked up from Phil Haack some time back, and that’s why I have the nested classes. Besides that, this is pretty vanilla fare. The pawn class is literally a do-nothing placeholder at this point, and now I just have to make this test not throw an exception, which is pretty easy. I just define the method:

Woohoo! Passing test. But that’s a pretty lame test, so let’s do something else. What good is testing a state mutating method if you don’t have a state querying method (meaning, if I’m going to write to something, it’s pointless unless someone or something can also read from it)? Let’s define another test method:

Alright, now we probably have to make a non (less) stupid implementation. Let’s make this new test pass.

Well, there we go. Now that everything is green, let’s refactor the test class a bit:

This may seem a little over the top, but I believe in ruthlessly eliminating duplication wherever it occurs, and we were duplicating that instantiation logic in the test class. Eliminating noise in the test methods also makes your intentions clearer in your test methods, which communicates more effectively to people what it is you want your code to do.

With that out of the way, let’s define something useful on Pawn as a starting point. Currently, it’s simply a class declaration followed by “{}” Here’s the test that I’m going to write:

Alright, now let’s make this thing pass:

You might be objecting slightly to what I’ve done here in jumping the gun from the simplest thing that could work. Well, I’ll remind you that simplest does not mean stupidest. There’s no need to return a constant here, since the movement of a pawn (move ahead one square) isn’t exactly rocket science. Do the simplest thing to make the tests pass is the discipline, and in either case, we’re adding a quick one liner.

Now, there are all kinds of problems with what we’ve got so far. We’re going to need to differentiate white pieces from black pieces later. GetMoves (plural) returns a single tuple, and, while Tuple is a cool language construct, that clearly needs to go in favor of some kind of value object, and quickly. The board takes an array of pawns instead of a more general piece concept. The most recent unit test has two asserts in it, which isn’t very good. But in spite of all of those shortcomings (which, are going to be my to do list for next post), we now have a board to which you can add pieces and a piece that understands its most basic (and common) movement.

The take-away that I want you to have from this post is two-fold:

  1. Do some up-front planning, particularly as it relates to real-world conceptualizing and dependency flow.
  2. It’s a journey, and you’re not going to get there all at once. Your first few red-green-refactors will leave you with something incomplete to the point of embarrassment. But that’s okay, because TDD is about incremental progress and the simultaneous impossibility of regressions. We can only improve.