Implementing Tic-Tac-Toe using state classes

This post follows on from the previous one on union types, by showing how to use state classes to implement a Tic-Tac-Toe game (a.k.a. Noughts and Crosses here in the UK).

Background

I ran across two mentions of the game of Tic-Tac-Toe recently. First, in the excellent book “Professional Enterprise .NET” by Jon Arking and Scott Millett, chapter 4 describes using TDD for Tic-Tac-Toe.

Secondly, Tony Morris wrote a post a while back that he almost called “What to Solve Before Expecting Me to Take Your Opinions of Static Typing Seriously” in which he describes his disappointment that most programmers couldn’t implement a robust API for a trivial game like Tic-Tac-Toe.

An extremely robust API for a relatively trivial problem … was achieved by exploiting techniques available from static typing and functional programming.
[This] appears to be difficult for many programmers to reproduce.
Tony Morris Understanding Practical API Design

Here is a paraphase of some of his requirements for the API:

If you write a function, I must be able to call it with the same arguments and always get the same results.
If I, as a client of your API, call one of your functions, I should always get a sensible result. Not null or an exception, etc.
If I call Move on a tic-tac-toe board, but the game has finished, I should get a compile-time error. In other words, calling move on inappropriate game states is disallowed by the types themselves.
If I call WhoWonOrDraw on a tic-tac-toe board, but the game hasn’t yet finished, I get a compile-time error.
It is not possible to play out of turn.

So, before reading on, think about how you might do this in C# – can you meet the challenge!

Tests vs static typing

Unit tests were championed by users of dynamic languages such as Smalltalk and Ruby, but C# is statically typed, so surely we can take advantage of this to write fewer tests?

The answer is yes! With a bit of work, you can use the type system to provide you with “compile time unit tests” as it were.

Unfortunately, a typical C# implementation does not take full advantage of the power of static types and therefore does not meet the requirements above. A typical C# (or Java) implementation will have just a single class to represent all the states of the game, with various internal flags, and lots of branching logic. So then of course you need tests to ensure that the code is robust.

_{[Note: I’m not talking about TDD as a process to drive design, but unit tests as a robustness and code coverage tool.]}

For example, in the Professional Enterprise .NET book, the code for a move looks something like:

public void PlaceMarkerAt(Row row, Column column)
{
    if (CanPlaceMarkerAt(row, column))
    {
        // check that slot is not occupied
        ChangeCurrentPlayer();
    }
    else
    {
        throw new ApplicationException(...)
    }
}

And the code for checking the status looks something like this:

public GameStatus Status()
{
    GameStatus gameStatus;

    if (IsAWinner(Player.O))
        gameStatus = GameStatus.PlayerOWins;
    else if (IsAWinner(Player.X))
        gameStatus = GameStatus.PlayerXWins;
    else if (GameIsADraw())
        gameStatus = GameStatus.GameDrawn;
    else if (WhoseTurn() == Player.X)
        gameStatus = GameStatus.AwaitingPlayerXToPlaceMarker;
    else
        gameStatus = GameStatus.AwaitingPlayerOToPlaceMarker;

    return gameStatus;
}

I’m not picking on this book at all – as I said, it is a great book – but it does demonstrate that even best-practice C# code is not maximally benefiting from the type system. Almost every method has (potentially buggy) conditionals and switches which would be unneeded if states were used.

The Tic-Tac-Toe implementation

So, enough talk, how can you create an API for Tic-Tac-Toe that makes Tony Morris happy?

The trick is to create distinct classes for each state in the game, as discussed in the previous post. We’re going to use the template class demonstrated in that post, but you could always create the code by hand.

First, create an IGameState.tt file to generate the interface and the states. In this implementation, we’ll only create three states: GameStateXToMove, GameStateOToMove, and GameStateGameOver.

Here’s the file:

<#
var states = new [] {"GameStateXToMove", "GameStateOToMove","GameStateGameOver"};
#>
<#@ include file="..\FoldStates.ttinclude" #>

And here’s the generated code:

partial interface IGameState
{
    IGameState Transition(
        Func<GameStateXToMove, IGameState> gameStateXToMove,
        Func<GameStateOToMove, IGameState> gameStateOToMove,
        Func<GameStateGameOver, IGameState> gameStateGameOver
        );

    void Action(
        Action<GameStateXToMove> gameStateXToMove,
        Action<GameStateOToMove> gameStateOToMove,
        Action<GameStateGameOver> gameStateGameOver
        );

    TObject Func<TObject>(
        Func<GameStateXToMove, TObject> gameStateXToMove,
        Func<GameStateOToMove, TObject> gameStateOToMove,
        Func<GameStateGameOver, TObject> gameStateGameOver
        );
}

partial class GameStateXToMove : IGameState
{
    IGameState IGameState.Transition(Func<GameStateXToMove, IGameState> gameStateXToMove, Func<GameStateOToMove, IGameState> gameStateOToMove, Func<GameStateGameOver, IGameState> gameStateGameOver)
    {
        return gameStateXToMove(this);
    }

    void IGameState.Action(Action<GameStateXToMove> gameStateXToMove, Action<GameStateOToMove> gameStateOToMove, Action<GameStateGameOver> gameStateGameOver)
    {
        gameStateXToMove(this);
    }

    TObject IGameState.Func<TObject>(Func<GameStateXToMove, TObject> gameStateXToMove, Func<GameStateOToMove, TObject> gameStateOToMove, Func<GameStateGameOver, TObject> gameStateGameOver)
    {
        return gameStateXToMove(this);
    }
}

partial class GameStateOToMove : IGameState
{
    IGameState IGameState.Transition(Func<GameStateXToMove, IGameState> gameStateXToMove, Func<GameStateOToMove, IGameState> gameStateOToMove, Func<GameStateGameOver, IGameState> gameStateGameOver)
    {
        return gameStateOToMove(this);
    }

    void IGameState.Action(Action<GameStateXToMove> gameStateXToMove, Action<GameStateOToMove> gameStateOToMove, Action<GameStateGameOver> gameStateGameOver)
    {
        gameStateOToMove(this);
    }

    TObject IGameState.Func<TObject>(Func<GameStateXToMove, TObject> gameStateXToMove, Func<GameStateOToMove, TObject> gameStateOToMove, Func<GameStateGameOver, TObject> gameStateGameOver)
    {
        return gameStateOToMove(this);
    }
}

partial class GameStateGameOver : IGameState
{
    IGameState IGameState.Transition(Func<GameStateXToMove, IGameState> gameStateXToMove, Func<GameStateOToMove, IGameState> gameStateOToMove, Func<GameStateGameOver, IGameState> gameStateGameOver)
    {
        return gameStateGameOver(this);
    }

    void IGameState.Action(Action<GameStateXToMove> gameStateXToMove, Action<GameStateOToMove> gameStateOToMove, Action<GameStateGameOver> gameStateGameOver)
    {
        gameStateGameOver(this);
    }

    TObject IGameState.Func<TObject>(Func<GameStateXToMove, TObject> gameStateXToMove, Func<GameStateOToMove, TObject> gameStateOToMove, Func<GameStateGameOver, TObject> gameStateGameOver)
    {
        return gameStateGameOver(this);
    }
}

Extending the IGameState interface

Next, we’ll add to the partial interface in a separate file (IGameState.cs):

public partial interface IGameState
{
    bool IsValidMove(Row row, Col col);
}

We’ll add one method (IsValidMove) that is common to all states. Note what is missing though. There is is no Move method or WhoWonOrDraw method. These will be reserved for the state classes.

The GameStateXToMove class

Now let’s look at the code needed for the first state: GameStateXToMove:

public partial class GameStateXToMove : GameStateBase
{
    internal GameStateXToMove()
        : base(new MoveSequence())
    {
    }

    internal GameStateXToMove(MoveSequence moveSequence)
        : base(moveSequence)
    {
    }

    public IGameState Move(Row row, Col col, Action<Move> invalidMoveCallback)
    {
        var move = new Move(row, col, Player.X);
        var newMoveSequence = MoveSequence.WithNewMove(move, invalidMoveCallback);
        return newMoveSequence.IsGameOver()
            ? new GameStateGameOver(newMoveSequence)
            : new GameStateOToMove(newMoveSequence) as IGameState;
    }

    bool IGameState.IsValidMove(Row row, Col col)
    {
        return MoveSequence.IsValidMove(row, col);
    }
}

This class inherits from GameStateBase, which stores a MoveSequence that is common to all three states. The MoveSequence has the intelligence to know which moves are valid and when the game is over. The two constructors initialize the class with either an empty MoveSequence, or a non-empty one.

The Move method exists only in the GameStateXToMove and GameStateOToMove classes. It creates a new move, then appends that it the current MoveSequence, and then creates a new state depending on whether the game is over. If the game is over, the new state is GameStateGameOver, otherwise it is Player O’s turn (GameStateOToMove). Because two different states could be returned, the overall return type must be IGameState, not any particular state.

What happens if the move is invalid? Should we ignore it, throw an exception, or what? This code can’t (and shouldn’t) decide, so the action has been delegated back to the called. In this case, the move sequence is left unchanged – MoveSequence.WithNewMove returns the same list. Again, this is one of the requirements – no unexpected exceptions!

Finally, the IsValidMove method delegates to the MoveSequence. I have deliberately made this an explicit interface implementation so that the methods common to all game states are separate from the state-specific methods.

The GameStateOToMove class

The code for the GameStateOToMove is almost identical, except that in the Move method, the next state is GameStateXToMove, if the game is not over.

public partial class GameStateOToMove : GameStateBase
{
    internal GameStateOToMove()
        : base(new MoveSequence())
    {
    }

    internal GameStateOToMove(MoveSequence moveSequence)
        : base(moveSequence)
    {
    }

    public IGameState Move(Row row, Col col, Action<Move> invalidMoveCallback)
    {
        var move = new Move(row, col, Player.O);
        var newMoveSequence = MoveSequence.WithNewMove(move, invalidMoveCallback);
        return newMoveSequence.IsGameOver()
            ? new GameStateGameOver(newMoveSequence)
            : new GameStateXToMove(newMoveSequence) as IGameState;
    }

    bool IGameState.IsValidMove(Row row, Col col)
    {
        return MoveSequence.IsValidMove(row, col);
    }
}

The GameStateGameOver class

The code for the GameStateGameOver is quite different. It does not implement Move and it does implement WhoWonOrDraw.

public enum GameOverState
{
    XWon, YWon, Draw
}

public partial class GameStateGameOver : GameStateBase
{
    internal GameStateGameOver(MoveSequence moveSequence)
        : base(moveSequence)
    {
    }

    public GameOverState WhoWonOrDraw()
    {
        return MoveSequence.WhoWonOrDraw();
    }

    bool IGameState.IsValidMove(Row row, Col col)
    {
        return false;
    }
}

It can also return false for IsValidMove without even looking at the MoveSequence.

This code is a good example of how the number of conditionals is greatly reduced. Because this class only deals with one state, there are no conditionals at all!

If you think about trying to get 100% code coverage for tests, every conditional doubles the number of code paths to test! So avoiding them has multiple benefits – it makes the code more compact, more readable, less buggy and easier to test thoroughly.

Testing the code

Let’s look at how this code might be tested.

Test: “Player X is the first Player to place a marker.”

The TicTacToeGame wrapper class simply returns a new GameStateXToMove when a new game is started. Then to test which state we are in, we use the Func method, with a lambda for each case.

[Test]
public void PlayerXIsTheFirstPlayerToPlaceAMarker()
{
    var initialState = TicTacToeGame.StartNewGame();
    var isXToPlay = initialState.Func(
        xToMove => true,
        oToMove => false,
        gameOver => false);
    Assert.That(isXToPlay, Is.True);
}

Here’s another test:

Test: “Player O Will Be Next To Take A Turn After Player X Has Placed A Marker”

[Test]
public void PlayerOWillBeNextToTakeATurnAfterPlayerXHasPlacedAMarker()
{
    var initialState = TicTacToeGame.StartNewGame();
    Action<Move> invalidMoveAction = move => Console.WriteLine("The move {0} is not allowed", move);

    // X plays
    var afterFirstMove = initialState.Transition(
        xToMove => xToMove.Move(Row.Row1, Col.Col1, invalidMoveAction),
        oToMove => oToMove,
        gameOver => gameOver);

    var isOToPlay = afterFirstMove.Func(xToMove => false, oToMove => true, gameOver => false);
    Assert.That(isOToPlay, Is.True);
}

Again, a similar technique is used to find out which state we are in.

We can go on like this in a similar vein. Let’s skip to what happens when the game is over:

Test: “If Player X gets three Xs in a row, then the game is won by Player X.”

[Test]
public void IfPlayerXGetsThreeXsInARowThenTheGameIsWonByPlayerX()
{
    var initialState = TicTacToeGame.StartNewGame();
    Action<Move> invalidMoveAction = move => Console.WriteLine("The move {0} is not allowed", move);

    // X plays
    var move1 = initialState.Transition(
        xToMove => xToMove.Move(Row.Row1, Col.Col1, invalidMoveAction),
        oToMove => oToMove,
        gameOver => gameOver);

    // O plays
    var move2 = move1.Transition(
        xToMove => xToMove,
        oToMove => oToMove.Move(Row.Row2, Col.Col1, invalidMoveAction),
        gameOver => gameOver);

    // X plays
    var move3 = move2.Transition(
        xToMove => xToMove.Move(Row.Row1, Col.Col2, invalidMoveAction),
        oToMove => oToMove,
        gameOver => gameOver);

    // O plays
    var move4 = move3.Transition(
        xToMove => xToMove,
        oToMove => oToMove.Move(Row.Row2, Col.Col2, invalidMoveAction),
        gameOver => gameOver);

    // X plays and wins
    var move5 = move4.Transition(
        xToMove => xToMove.Move(Row.Row1, Col.Col3, invalidMoveAction),
        oToMove => oToMove,
        gameOver => gameOver);

    var isGameOver = move5.Func(xToMove => false, oToMove => false, gameOver => true);
    Assert.IsTrue(isGameOver);

    GameOverState? whoWon = null;
    move5.Action(
        xToMove => { },
        oToMove => { },
        gameOver => whoWon = gameOver.WhoWonOrDraw());
    Assert.That(whoWon, Is.EqualTo(GameOverState.XWon));

}

Summary

Looking back at the requirements, did we meet them?

Call a function with the same arguments and always get the same results. Check! The states are immutable.
A client of your API, calling one of your functions, should always get a sensible result. Check! No nulls or exceptions anywhere in the code.
If I call Move but the game has finished, I should get a compile-time error. Check! Try it:

var move5 = move4.Transition(
    xToMove => xToMove.Move(Row.Row1, Col.Col3, invalidMoveAction),
    oToMove => oToMove,
    gameOver => gameOver.Move(Row.Row1, Col.Col3, invalidMoveAction));  // compile time error!

If I call WhoWonOrDraw on a tic-tac-toe board, but the game hasn’t yet finished, I get a compile-time error. Check again! Try it:

move5.Action(
    xToMove => whoWon = xToMove.WhoWonOrDraw(), // compile time error
    oToMove => { },
    gameOver => whoWon = gameOver.WhoWonOrDraw());

It is not possible to play out of turn. Check! If the state is GameStateXToMove then only X can move. The types will not allow player O to move.

So all in all, a nice solution to a thorny problem.

Getting the code

You can get the code from the git repository for this blog (see the about page). This has a full set of examples and unit tests.

boustrophedonic

Thoughts on software and architecture

Implementing Tic-Tac-Toe Using State Classes