3
\$\begingroup\$

A friend of mine asked me to help him with his Tic-Tac-Toe implementation. He's a beginner, so we ended up implementing a simple state-machine that reacts to the moves. I was curious how I might better solve the problem, and came up with my own implementation (GitHub).

  • What would you change?
  • Is there anything I missed what could cause harm?
  • Is there better approach or meaningful optimization?

Player

In order to avoid primitive obsession (working with strings...) there's player representation with necessary method for checking equality.

public class Player : IEquatable<Player>
{
    public static readonly Player Blank = new Player('\0');

    public Player(char mark)
    {
        Mark = mark;
    }

    public char Mark { get; }
    public static bool IsBlank(Player player) =>
        player == null || player.Equals(Blank);

    public bool Equals(Player other) =>
        other != null
        && Mark == other.Mark;

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }

        return obj is Player player && Equals(player);
    }

    public override int GetHashCode() =>
        Mark.GetHashCode();
}

Playground representation

Game field, knowing its number and whether player took it or not. Base block of playground.

[DebuggerDisplay("{Index}: {Player != null ? Player.Mark.ToString() : \"-\"}")]
public struct Field
{
    private Player _player;

    public Field(int index)
    {
        Index = index;
        _player = null;
    }

    public int Index { get; }
    public bool IsEmpty => _player == null;
    public Player Player
    {
        get => _player;
        set => _player = value ?? throw new ArgumentException("Cannot set null player.");
    }
}

Playground representation - it knows there are 9 fields, it can check itself for state and allows one to perform turn.

public class Playground
{
    private static readonly (int, int, int)[] WinningCoords =
    {
        (0, 1, 2), // 1st row
        (3, 4, 5), // 2nd row
        (6, 7, 8), // 3rd row
        (0, 3, 6), // 1st col
        (1, 4, 7), // 2nd col
        (2, 5, 8), // 3rd col
        (0, 4, 8), // top left -> bottom right
        (2, 4, 6), // bottom left -> upper right
    };

    private readonly Field[] _fields;
    private readonly int _emptyFields;

    public Playground()
    {
        _fields = new Field[9];
        _emptyFields = _fields.Length;

        // initialize fields
        for (var i = 0; i < _fields.Length; i++)
        {
            _fields[i] = new Field(i + 1);
        }
    }

    private Playground(Field[] field)
    {
        _fields = field;
        _emptyFields = _fields.Count(f => f.Player == null);
    }

    public IReadOnlyList<Field> Fields => _fields;

    public Playground Turn(int index, Player player)
    {
        if (index < 1 || index > _fields.Length)
        {
            throw new ArgumentOutOfRangeException(
                nameof(index),
                $"Invalid turn, allowed index is in range [1..{_fields.Length}]");
        }

        if (Player.IsBlank(player))
        {
            throw new ArgumentException("Cannot turn with blank player.", nameof(player));
        }

        if (!_fields[index - 1].IsEmpty)
        {
            throw new ArgumentException($"Field {index} is already occupied.", nameof(index));
        }

        // copying array of structs - copying values
        var fields = new Field[9];
        _fields.CopyTo(fields, 0);

        // turn with player
        fields[index - 1].Player = player;

        return new Playground(fields);
    }

    public PlaygroundState GetState()
    {
        // player can win in 5th turn in the best case
        if (_emptyFields > 4)
        {
            return PlaygroundState.NotComplete;
        }

        bool FieldEqual(Field f1, Field f2)
        {
            return !Player.IsBlank(f1.Player) && f1.Player.Equals(f2.Player);
        }

        // try to find winner (rows, cols, diagonales)
        foreach ((int, int, int) i in WinningCoords)
        {
            (int a, int b, int c) = i;
            if (FieldEqual(_fields[a], _fields[b]) && FieldEqual(_fields[b], _fields[c]))
            {
                return PlaygroundState.Winner(_fields[a].Player);
            }
        }

        return _emptyFields == 0
            ? PlaygroundState.Tie
            : PlaygroundState.NotComplete;
    }
}

To keep playground as minimal as it could be, there's extension method for getting empty fields (nothing complex).

public static class PlaygroundExtensions
{
    public static IEnumerable<Field> EmptyFields(this Playground playground)
    {
        if (playground == null)
        {
            throw new ArgumentNullException(nameof(playground));
        }

        return playground.Fields.Where(f => f.IsEmpty);
    }
}

Playground state holds necessary information about state of the game - it's just container holding information.

public class PlaygroundState
{
    public static readonly PlaygroundState NotComplete = new PlaygroundState(GameState.NotComplete, Player.Blank);
    public static readonly PlaygroundState Tie = new PlaygroundState(GameState.Tie, Player.Blank);

    private PlaygroundState(GameState state, Player player)
    {
        State = state;
        Player = player;
    }

    public GameState State { get; }
    public Player Player { get; }

    public static PlaygroundState Winner(Player player) => new PlaygroundState(GameState.Winning, player);
}

... and game state itself.

public enum GameState
{
    NotComplete,
    Winning,
    Tie
}

The Game

And finally Tic-Tac-Toe solver.

public class Solver
{
    private readonly Player _player;
    private readonly Player _opponent;

    public Solver(Player player, Player opponent)
    {
        _player = player ?? throw new ArgumentNullException(nameof(player));
        _opponent = opponent ?? throw new ArgumentNullException(nameof(opponent));

        if (player.Equals(opponent))
        {
            throw new ArgumentException("Both players are the same, does not compute.", nameof(opponent));
        }
    }

    public (bool CanTurn, int Index) CalulateBestMove(Playground playground)
    {
        if (playground == null)
        {
            throw new ArgumentNullException(nameof(playground));
        }

        FieldScore result = MiniMax(playground, true);

        return result.Index > 0
            ? (true, result.Index)
            : (false, 0);
    }

    private FieldScore MiniMax(Playground playground, bool isMaximizing)
    {
        PlaygroundState state = playground.GetState();

        // board is in final state, return score immediately
        // (since we are not aware of previous move (chosen field)
        //  we return only score part)
        if (state.State != GameState.NotComplete)
        {
            return state.State == GameState.Tie
                ? new FieldScore { Score = 0 }
                : _player.Equals(state.Player)
                    ? new FieldScore { Score = 1 }
                    : new FieldScore { Score = -1 };
        }

        Player currentPlayer = isMaximizing 
            ? _player 
            : _opponent;

        // calculate scores for each possible move
        // (NB! recursion is about to happen)
        IEnumerable<FieldScore> moves = playground.EmptyFields()
            .Select(
                f => new FieldScore
                {
                    Index = f.Index,
                    Score = MiniMax(playground.Turn(f.Index, currentPlayer), !isMaximizing).Score
                });

        // captain obvious to the service:
        // player - get the highest score (ORDER BY score DESC)
        // opponent - get the lowest score (ORDER BY score ASC)
        moves = isMaximizing 
            ? moves.OrderByDescending(m => m.Score) 
            : moves.OrderBy(m => m.Score);

        return moves.First();
    }

    private struct FieldScore
    {
        public int Index { get; set; }
        public int Score { get; set; }
    }
}

Usage

// instantiate players
var p1 = new Player('X'); // human
var p2 = new Player('O'); // computer

// create solver for computer
var s = new Solver(p2, p1);

// initialize playground
var playground = new Playground();

// *** repeat until done ***

// let human turn
// ...

// find the best turn for computer and turn
(var canTurn, var idx) = s.CalulateBestMove(playground);
if (!canTurn) 
{
    // nope...
}

playground = playground.Turn(idx, p2);
\$\endgroup\$
4
\$\begingroup\$

You wrote good comments and your implementations is clean, IMHO. I only have a couple of nitpicks.

1) This is counter-intuitive:

Player.IsBlank(null) == true
Player.Blank.Equals(null) == false

Maybe IsNullOrBlank would be a better name for the first method (since it is similar to String.IsNullOrEmpty).

2) There are some magic numbers here and there, for example:

if (_emptyFields > 4)

or

var fields = new Field[9];

which is not a big problem in itself, but it makes a task of increasing the size of playing field much harder (you would have to tweak all those numbers).

3) I feel like a tuple is not the best choice of type for WinningCoords. Some sort of IEnumerable will probably look and scale better.

\$\endgroup\$
  • \$\begingroup\$ it makes a task of increasing the size of playing field much harder To be fair, OP has hard-coded every victory condition (indexes), on top of which the indexes are a single sequence that wraps around the board line by line. The entire codebase isn't built for changing the dimensions of the playing field. \$\endgroup\$ – Flater Apr 12 '18 at 11:01
  • \$\begingroup\$ Thanks for spotting bug with IsBlank and Equals - I should fix it. Regarding magical numbers - indeed I too hate hardcoded numbers in code, I will move those to constants. Yet this particular playground and solver work only for Tic-Tac-Toe 3x3 (maybe it should be named better?). \$\endgroup\$ – Zdeněk Apr 13 '18 at 10:56
  • \$\begingroup\$ @Zdeněk, nah, I think it is fairly clear. It is indeed a 3x3 solver and you probably have no intention of ever scaling it to larger playing field. I guess my point was, that if you can make your code scale better with very minor refactoring, then you probably should. You know, it is open source after all, someone can pick it up where you left it off. :) \$\endgroup\$ – Nikita B Apr 13 '18 at 12:11
  • \$\begingroup\$ @NikitaB: I got finally time to get back to it and I'm actually thinking again about my Player.Equals method. Player.IsNullOrBlank(null) == true but Player.Blank.Equals(null) == false seems legit to me - I don't want to say that null is equal to instance of Player.Blank - if I later decided on this information, I could end up with NullReferenceException. (Why I got here: Player was struct in my first implementation, but then I decided to change it to class so only reference is copied when solving the game) ... What do you think? \$\endgroup\$ – Zdeněk Apr 16 '18 at 16:31
  • \$\begingroup\$ @Zdeněk, as long as method name reflects those semantics, I don't see any problems. Sounds good. \$\endgroup\$ – Nikita B Apr 17 '18 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.