DaedTech

Stories about Software

By

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:

[TestClass]
public class BoardTest
{
    [TestClass]
    public class AddPiece
    {
        [TestMethod, Owner("ebd"), TestCategory("Proven"), TestCategory("Unit")]
        public void Does_Not_Throw_Exception_When_Adding_A_Piece_To_An_Unoccupied_Square()
        {
            var board = new Board();

            board.AddPiece(new Pawn(), 2, 1);
        }
    }
}

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:

public class Board
{
    public void AddPiece(Pawn piece, int xCoordinate, int yCoordinate)
    {
                
    }
}

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:

[TestClass]
public class BoardTest
{

    [TestClass]
    public class GetPiece
    {
        [TestMethod, Owner("ebd"), TestCategory("Proven"), TestCategory("Unit")]
        public void Retrieves_Piece_Added_To_Location()
        {
            var piece = new Pawn();
            var board = new Board();
            board.AddPiece(piece, 1, 1);

            Assert.AreEqual(piece, board.GetPiece(1, 1));
        }
    }

    [TestClass]
    public class AddPiece
    {
        [TestMethod, Owner("ebd"), TestCategory("Proven"), TestCategory("Unit")]
        public void Does_Not_Throw_Exception_When_Adding_A_Piece_To_An_Unoccupied_Square()
        {
            var board = new Board();

            board.AddPiece(new Pawn(), 2, 1);
        }
    }       
}

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

public class Board
{
    private readonly Pawn[,] _pieces = new Pawn[8,8];

    public void AddPiece(Pawn piece, int xCoordinate, int yCoordinate)
    {
        _pieces[xCoordinate, yCoordinate] = piece;
    }

    public Pawn GetPiece(int xCoordinate, int yCoordinate)
    {
        return _pieces[xCoordinate, yCoordinate];
    }
}

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

[TestClass]
public class BoardTest
{
    private Pawn Piece { get; set; }

    private Board Target { get; set; }

    [TestInitialize]
    public void BeforeEachTest()
    {
        Piece = new Pawn();
        Target = new Board();
    }

    [TestClass]
    public class GetPiece : BoardTest
    {
        [TestMethod, Owner("ebd"), TestCategory("Proven"), TestCategory("Unit")]
        public void Retrieves_Piece_Added_To_Location()
        {
            Target.AddPiece(Piece, 1, 1);

            Assert.AreEqual(Piece, Target.GetPiece(1, 1));
        }
    }

    [TestClass]
    public class AddPiece : BoardTest
    {
        [TestMethod, Owner("ebd"), TestCategory("Proven"), TestCategory("Unit")]
        public void Does_Not_Throw_Exception_When_Adding_A_Piece_To_An_Unoccupied_Square()
        {
            Target.AddPiece(new Pawn(), 2, 1);
        }
    }
}

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:

[TestClass]
public class PawnTest
{
    [TestClass]
    public class GetMovesFrom
    {
        [TestMethod, Owner("ebd"), TestCategory("Proven"), TestCategory("Unit")]
        public void Returns_2_3_When_Passed_2_2()
        {
            var pawn = new Pawn();

            Tuple possibleMoves = pawn.GetMovesFrom(2, 2);

            Assert.AreEqual(2, possibleMoves.Item1);
            Assert.AreEqual(3, possibleMoves.Item2);
        }
    }
}

Alright, now let’s make this thing pass:

public class Pawn
{
    public Tuple GetMovesFrom(int xCoordinate, int yCoordinate)
    {
        return new Tuple(xCoordinate, yCoordinate + 1);
    }
}

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.
23 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Quagmire
Quagmire
9 years ago

Very nice post… Looking forward to the next part.

Erik Dietrich
9 years ago
Reply to  Quagmire

Thanks! More coming soon.

Jacob
Jacob
9 years ago

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

Erik Dietrich
9 years ago
Reply to  Jacob

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!

Peter DiSalvo
9 years ago
Reply to  Erik Dietrich

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… Read more »

Themba Masina
Themba Masina
9 years ago

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

Erik Dietrich
9 years ago
Reply to  Themba Masina

It’s in the works — thanks for reading!

trackback

[…] => TDD and Modeling a Chess Game […]

Peter DiSalvo
9 years ago

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#… Read more »

Erik Dietrich
9 years ago
Reply to  Peter DiSalvo

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… Read more »

Peter DiSalvo
9 years ago
Reply to  Erik Dietrich

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?

Erik Dietrich
9 years ago
Reply to  Peter DiSalvo

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.

trackback

[…] code samples and walks readers through refactorings. He’s also doing a short series on TDD and modeling a chess game, but not because I asked him for help or anything… […]

trackback

[…] if you’re going to only read one article this week, go read this one (actually, reading the first two parts would be […]

Erin Stanfill
Erin Stanfill
9 years ago

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

Erik Dietrich
9 years ago
Reply to  Erin Stanfill

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
Erin Stanfill
9 years ago
Reply to  Erik Dietrich

Thanks!

cwlocke
cwlocke
8 years ago

I know this post is older but I’ve decided to build my own version of the board game ‘Battleship’… my kids love that game. I’m using this series and inspiration and education. However, I can’t make sense of one part of this post: 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). too many negatives for me to follow… does not mean no.. it’s really not true at all. I assume (based on further reading) that at least some… Read more »

Erik Dietrich
8 years ago
Reply to  cwlocke

Oh, yeah, sorry ’bout that. The thing I hear a lot is “TDD says that you don’t need to plan anything up-front.” That statement is what I was calling a canard, so the message is “TDD *is* compatible with up-front planning.”

Aschwin Wesselius
Aschwin Wesselius
8 years ago

Would it be possible to add links to previous and (at least) next chapters of this series beneath each article?

It is hard to browse the series by using the tags, because it starts with the most recent articles. I started reading this one, but I have no clue how to get to the second chapter the fastest way.

Erik Dietrich
8 years ago

I understand the desire, but it’d frankly be a ton of work for me at this point. If you go here, you can start at the beginning of the tag: https://daedtech.com/tag/chesstdd/page/10 and then just iterate forward by changing it to https://daedtech.com/tag/chesstdd/page/9 and so on. Alternatively, the youtube playlist has just the videos all in order: https://www.youtube.com/playlist?list=PLYee78FfYpodqhAdjPNjo-l2sR2tsc0E4

Aschwin Wesselius
Aschwin Wesselius
8 years ago

I see the Pawn.GetMovesFrom() is returning a Tuple here and later it changes to an IEnumerable. Maybe I’m ahead of this, but I’m trying to find out how I can implement this method in PHP.

If I want to follow the series, I first have to implement a Tuple like structure for this method. Later I have to change it, when you change it in the series, to an IEnumerable.

Do you have any idea how to find or implement these structures in PHP to be able to follow along?

Erik Dietrich
8 years ago

I haven’t really kept pace with PHP language, but it might be tough to keep pace. I make heavy use of lambda expressions and Linq in C#. I feel like PHP has lambdas and closures, but I have no idea whether it has anything like Linq at all or how robust its collection types are. I also don’t know whether PHP supports generics (the “T” in IEnumerable). It may be that you’d have to implement a lot of the things that I use yourself. If you were going to implement IEnumerable, you could, for the purposes of this series, probably… Read more »