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.
  • Quagmire

    Very nice post… Looking forward to the next part.

  • Jacob

    As someone who benefits greatly from screencasts and uses Pluralsight constantly, I’d be very interested to see this on YouTube.

  • Themba Masina

    Looking forward to upcoming posts and the YouTube would be very nice to follow.

  • Pingback: The Baeldung Weekly Review 11

  • http://www.daedtech.com/blog Erik Dietrich

    Thanks! More coming soon.

  • http://www.daedtech.com/blog Erik Dietrich

    That’s now part of the plan. I just did screen capture for the next part in the series, so narration and figuring out how to embed it here are next. Stay tuned!

  • http://www.daedtech.com/blog Erik Dietrich

    It’s in the works — thanks for reading!

  • Peter DiSalvo

    Very cool.

    One of the things I’ve had trouble with is figuring out how to handle methods that return collections. In my TDD travels, I’ve read that you shouldn’t have loops in your tests. So how do you test that a collection has the correct items? Using linq, or in Java, list.contains(…) feels like I’m cheating, but what else are you supposed to do?

    Another issue with collections is determining which collection type to return. Pawn’s GetMovesFrom method will return a collection of some type. Should it be a built-in collection interface, or a custom class that wraps a C# collection, e.g., MovesCollection. Or is it too early to consider this?

  • Peter DiSalvo

    I’ve recently started watching pair programming and TDD walkthrough videos. There doesn’t seem to be many around, but they’re helpful when you find a good one.

    It’s great to see experienced programmers make mistakes and recover from them. As the viewer, it’s almost like a game. I can pause the video and consider what I might do in the face of a particular problem, and then compare it to what the more experienced programmer actually does.

    I find the videos differ from books in that books tend to setup problems with a perfected solution, and even perfected refactorings. When the author refactors to something brilliant, you’re left wondering how they got there. With the videos, you often find the creator’s path is much more natural. I even find experienced programmers making some of the same mistakes I do, the difference is how they recover from it and design their eventual solution.

  • Pingback: This is my ball of mud. There are many like it, but this one is mine. | The Secret Squad

  • http://www.daedtech.com/blog Erik Dietrich

    I think the advice about not looping in tests is generally in regards to looping around your assert statement. If you do that, you’re really executing dozens or hundreds of tests. (e.g. if I had a test that did a foreach on GetMovesFrom() and asserted each returned value was non-null). Seeing if a returned collection contains a value is conceptually only a single assert, and whether you use Linq or iterate manually to do so is just an implementation detail. I don’t think either one of these is “cheating” at all. (I can go into more detail at some point about the problem with loops around asserts, if you’d like)

    As to your second question, my answer would be “go with a standard collection until you have a compelling reason to roll your own.” Earlier in my career, I would often inherit from collection types, which would often lead to custom types that I had created that were really only a c-style TYPEDEF (meaning I had basically just renamed an existing type) or else that tacked on just a bit of functionality. Suffering through some pain over the years, I found that I was happier encapsulating standard collections inside a type as opposed to inheriting from that time (e.g. making BoardCollection hide a 2-d array instead of inherit from a List of Lists or something). This falls in line with the generally popular adage these days “favor composition over inheritance.” (This is also something I could probably expand into a small post — think I might make a draft to remind myself to do that)

  • http://thesecretsquad.wordpress.com Peter DiSalvo

    Thank you for clarifying about asserting with loops.That makes sense now.

    Regarding returning a collection, I’d like to expand my initial question. Upon realizing a method must return a collection, how do you decide which type to return? What would the return type of GetMovesFrom() be? IList, ICollection, simple array? The fact that I’m even questioning which type to use makes me think I should create a custom type that delegates to one of these other types, i.e., defer the decision of which type to actually use. Is that a compelling reason to create a custom collection type?

  • http://www.daedtech.com/blog Erik Dietrich

    In my opinion, no. I’d just pick the lightest-weight option that you need for the time being and use that until it becomes insufficient, somehow. I actually have a post in the works about IEnumerable vs IList return types, so stay tuned for a more elaborate version of my thoughts.

    I’m just finishing up my latest Pluraslight course, so I should have some additional time to continue the series/posts I’ve started here in the next few weeks.

  • Pingback: The Baeldung Weekly Review 14

  • Erin Stanfill

    I really like this series, but wish you would give all of the posts “chess” tag so I could easily share them all. :)

  • http://www.daedtech.com/blog Erik Dietrich

    Good idea, and done! I added the tag “ChessTDD” for all of the posts in this series (and also noticed in the process that I’m not terribly consistent in my tagging). And thanks for sharing them — I appreciate it.

  • Erin Stanfill

    Thanks!