Ultimate Tic-Tac-Toe data model

Question

This is another entry for The Ultimate Tic-Tac-Toe review.

My design criteria were:

• A DLL which encapsulates the data, i.e. the game state
• Don't include the GUI, nor the decision-making (game-playing) logic
• Be careful not to allow corrupted state
• Make it as small (few lines of code) as possible

Here's the DLL code:

using System;
using System.Collections.Generic;

namespace UltimateTicTacToe.Model
{
    // Cell only contains its state, not its own location
    // true -> "O"
    // false -> "X"
    // null -> (not played yet)
    // Immutable because it's a struct.
    public struct Cell
    {
        readonly bool? state;
        public bool? State { get { return state; } }
        public Cell(bool state) { this.state = state; }
    }

    // A trivial struct with fly-weight static instances
    // Immutable because it's a struct.
    // Short, constant-length names like 'L00' so that they line up well.
    public struct Location
    {
        readonly int row;
        readonly int column;
        public int Row { get { return row; } }
        public int Column { get { return column; } }
        public Location(int row, int column)
        {
            this.row = row;
            this.column = column;
        }

        public static Location L00 = new Location(0, 0);
        public static Location L01 = new Location(0, 1);
        public static Location L02 = new Location(0, 2);
        public static Location L10 = new Location(1, 0);
        public static Location L11 = new Location(1, 1);
        public static Location L12 = new Location(1, 2);
        public static Location L20 = new Location(2, 0);
        public static Location L21 = new Location(2, 1);
        public static Location L22 = new Location(2, 2);

        internal static List<Location> All = new List<Location>()
        {
            L00, L01, L02,
            L10, L11, L12,
            L20, L21, L22
        };

        // Simpler than overriding Equals etc.
        // http://stackoverflow.com/a/1502479/49942
        public bool Matches(Location rhs)
        {
            return (this.row == rhs.row) && (this.column == rhs.column);
        }
    }

    // Class so it may be null.
    // Says who won a game or quadrant,
    // and which were the winning locations.
    public class Winner
    {
        public bool Player { get; private set; }
        public Location[] Locations { get; private set; }
        public Winner(bool player, Location[] locations)
        {
            Player = player;
            Locations = locations;
        }
    }

    // public so be careful not to expose too much.
    // Not abstract so this could be used as private
    // member data instead of as a public superclass.
    public class BoardT<TCell>
    {
        readonly TCell[,] cells = new TCell[3, 3];

        // this delegate emulates (is used instead of)
        // `protected abstract bool? getCellState(TCell cell);` 
        readonly Func<TCell, bool?> getCellState;
        public Winner Winner { get; private set; }

        // This list could be a member of Location instead.
        static List<Location[]> lines = new List<Location[]>()
        {
            new Location[]{ Location.L00, Location.L01,Location.L02},
            new Location[]{ Location.L10, Location.L11,Location.L12},
            new Location[]{ Location.L20, Location.L21,Location.L22},
            new Location[]{ Location.L00, Location.L10,Location.L20},
            new Location[]{ Location.L01, Location.L11,Location.L21},
            new Location[]{ Location.L02, Location.L12,Location.L22},
            new Location[]{ Location.L00, Location.L11,Location.L22},
            new Location[]{ Location.L02, Location.L11,Location.L20}
        };

        protected BoardT(Func<TCell, bool?> getCellState)
        {
            this.getCellState = getCellState;
        }

        // Public get for Cell in Quadrant and for Qhadrant in Game.
        // Protected set can only be accessed via subclass.
        public TCell this[Location location]
        {
            get { return cells[location.Row, location.Column]; }
            protected set { cells[location.Row, location.Column] = value; }
        }

        // Invoked by subclass at the end of each Play.
        protected void Recalculate()
        {
            foreach (var line in lines)
            {
                bool? isWon = this.isWon(line);
                if (isWon.HasValue)
                {
                    this.Winner = new Winner(isWon.Value, line);
                    return;
                }
            }
        }

        // private helper for Recalculate.
        bool? isWon(Location[] line)
        {
            bool? rc = null;
            foreach (Location location in line)
            {
                bool? cellState = getCellState(this[location]);
                if (!cellState.HasValue)
                    return null;
                if (!rc.HasValue)
                    rc = cellState;
                else if (rc.Value != cellState.Value)
                    return null;
            }
            return rc;
        }

        // might be full before it's won
        public bool IsFull
        {
            get { return !Location.All.Exists(location => !getCellState(this[location]).HasValue); }
        }
    }

    // Quadrant is a Board of Cell instances
    public class Quadrant : BoardT<Cell>
    {
        internal Quadrant()
            : base(getCellState)
        {
        }
        static bool? getCellState(Cell cell)
        {
            return cell.State;
        }

        internal void Play(Location location, bool cellState)
        {
            if (this[location].State.HasValue)
                throw new Exception("Already played on this cell");
            this[location] = new Cell(cellState);
            Recalculate();
        }
    }

    public enum Variant
    {
        // Helpful for short unit tests,
        // allows one player to play too often.
        Cheat,
        Normal,
        // See "crazy" variant on http://mathwithbaddrawings.com/2013/06/16/ultimate-tic-tac-toe/
        // not currently implemented.
        Crazy
    }

    public class PreviousPlay
    {
        public Location QuadrantLocation { get; private set; }
        public bool Player { get; private set; }
        internal PreviousPlay(Location quadrantLocation, bool player)
        {
            QuadrantLocation = quadrantLocation;
            Player = player;
        }
    }

    // Game is a Board of Quadrant instances.
    public class Game : BoardT<Quadrant>
    {
        readonly Variant variant;
        public PreviousPlay PreviousPlay { get; private set; }

        public Game(Variant variant)
            : base(getCellState)
        {
            Location.All.ForEach(location => base[location] = new Quadrant());
            this.variant = variant;
        }
        static bool? getCellState(Quadrant quadrant)
        {
            if (quadrant.Winner == null)
                return null;
            return quadrant.Winner.Player;
        }

        public void Play(Location quadrantLocation, Location cellLocation, bool cellState)
        {
            switch (variant)
            {
                case Variant.Cheat:
                    break;
                case Variant.Normal:
                    if (PreviousPlay == null)
                        // first player
                        break;
                    if (PreviousPlay.Player == cellState)
                        throw new Exception("This player has already played");
                    Quadrant requiredQuadrant = base[PreviousPlay.QuadrantLocation];
                    bool canPlay = (requiredQuadrant.Winner == null) &&
                        // testing the isFull condition wasn't in the game specs but is required
                        !requiredQuadrant.IsFull;
                    if (canPlay && !PreviousPlay.QuadrantLocation.Matches(quadrantLocation))
                        throw new Exception("Not playing in the required quadrant");
                    break;
                case Variant.Crazy:
                default:
                    throw new NotImplementedException();

            }
            Quadrant quadrant = base[quadrantLocation];
            quadrant.Play(cellLocation, cellState);
            Recalculate();
            PreviousPlay = new PreviousPlay(cellLocation, cellState);
        }
    }
}

I decided to do without events (i.e. callbacks) in the implementation: for example, cell doesn't tell quadrant when the cell state changes (the quadrant only knows because it's the quadrant which is modifying the cell).

Here's some user code (from a separate project):

using System;

using UltimateTicTacToe.Model;

namespace UltimateTicTacToe
{
    class Program
    {
        static void Main(string[] args)
        {
            test1();
            test2();
            test3();
        }

        static void test3()
        {
            // TODO test a game which exercises the Quadrant.IsFull property.
        }

        static void test2()
        {
            Game game = new Game(Variant.Normal);
            game.Play(Location.L00, Location.L11, false);

            // try to play out of turn
            bool failed = false;
            try
            {
                game.Play(Location.L11, Location.L11, false);
                failed = true;
            }
            catch (Exception) { }
            assert(!failed);

            // try to play in the wrong quadrant
            try
            {
                game.Play(Location.L22, Location.L11, true);
                failed = true;
            }
            catch (Exception) { }
            assert(!failed);

            // try to play properly
            game.Play(Location.L11, Location.L11, true);
        }

        static void test1()
        {
            Game game = new Game(Variant.Cheat);

            Quadrant quadrant = game[Location.L00];
            assert(quadrant.Winner == null);

            // play a row on top-left
            game.Play(Location.L00, Location.L00, false);
            game.Play(Location.L00, Location.L01, false);
            game.Play(Location.L00, Location.L02, false);
            assert(quadrant.Winner.Player == false);

            assert(quadrant[Location.L00].State == false);
            assert(quadrant[Location.L22].State == null);
            assert(game.Winner == null);

            // play a column in center
            game.Play(Location.L11, Location.L00, false);
            game.Play(Location.L11, Location.L10, false);
            game.Play(Location.L11, Location.L20, false);
            // play a diagonal on bottom-right
            game.Play(Location.L22, Location.L02, false);
            game.Play(Location.L22, Location.L11, false);
            game.Play(Location.L22, Location.L20, false);

            assert(game.Winner.Player == false);
        }

        static void assert(bool b)
        {
            if (!b)
                throw new Exception();
        }
    }
}

Is there a more idiomatic way to code that assert function at the bottom, when I want to assert in a release build?

Answer 1

Here's a bug:

• Someone can play on an already-won quadrant (is this allowed by the rules?).
• If they play on an empty space of an already-won quadrant they can 'win again' i.e. trigger the Recalculate logic and potentially get a different Winner.

---

Cell state is bool? and Player is a corresponding bool.

It makes sense (code would be more readable) to replace bool with an enum Player { X, O }, remove the struct Cell definition altogether, and use BoardT<Player?> as the subclass (or member data) of Quadrant.

---

The bool canPlay calculation could be a internal bool CanPlay { get {...}} property of Quadrant.

public bool CanPlay(Location quadrantLocation) (which depends on the PreviousPlay in Game) should be a public method of Game, because the UI will want it in order to know whether to render each quadrant as playable.

Answer 2

nullable bools give me a weird twitchy feeling behind my eyeballs.

If you need three states you should really wrap it in something like a Enum.

EDIT: somebody already said that. oops.

Answer 3

Why do you hardcode the board initialization (you have 9 LOCs for initializing possible locations, 8 LOCs for initializing possible lines...)? It takes a lot of LOCs, and make the code less maintainable (what if you want to play 4x4?). You can initialize the possible Locations using loops, and you can calculate the lines on-the-fly (go over all rows, go over all columns, go over diagonals). I would even consider doing away with the Location struct altogether, and use actual [row,column] to indicate a location.

Another small point - I think you should rename the class PreviousPlay - the name suggests more of a member name (a state) than a class name. If you don't like to use Play, maybe HistoricPlay?