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);
