Follow-Up Post Tictactoe now with AI

Question

A month ago I finished and posted my first version of my Tic-Tac-Toe, I received a lot of good feedback and refactored it to more closely suit the MVP design pattern.

I've done some further clean-ups and refactoring in the code now but most importantly I have implemented a very primitive AI, that works "fairly well", my goal with the AI was NOT to create an AI with perfect play, this has been covered many times before as Tictactoe is a solved game, my goal was to create an AI that would mimick human play more closely. I think the implementation is decent but the code is a mess, it was my first attempt ever at coding a weak AI and it ended up with me having to add quite a large amount of extra methods for searching and sorting the grid just for the AI to work.

Anyhow, any feedback is appreciated, not restricted to the AI only, I have posted the (almost) complete code below:

Grid.cs

    class Grid
    {
        const int MAX_CELLS = 3;                
        public Cell[,] Cells { get; set; }
        private Cell[,] cells = new Cell[MAX_CELLS, MAX_CELLS];
        public Cell this[int index, int index2]
        {
            get
            {
                return cells[index, index2];
            }
            set 
            {
                cells[index, index2] = value;
            }
        }
        public Outcome Outcome { get; private set; }        

        public Grid(IGameViewer viewer)
        {
            Outcome = Outcome.None;

            for (int x = 0; x < MAX_CELLS; x++)
            {
                for (int y = 0; y < MAX_CELLS; y++)
                {
                    this[x, y] = new Cell(viewer, new Position(x, y));
                }
            }
        }

        public bool CheckOutcome(Position coords, Player player)
        {
            //Check for player wins first
            var corners = new Position[] { new Position(0,0), new Position(2,0), new Position(0,2), new Position(2,2) };
            var middle = new Position(1,1);
            var checkDiagonals = false;

            //If the cell is at the corner or the middle we have to check for diagonal wins too
            if (corners.Any(e => e.Equals(coords)) || middle.Equals(coords)) { checkDiagonals = true; }

            if (player.PlayerWon(this[coords.X, coords.Y], this, checkDiagonals))
            {
                switch (player.marker)
                {
                    case Mark.Cross:
                        Outcome = Outcome.CrossWin;
                        break;
                    case Mark.Nought:
                        Outcome = Outcome.NoughtWin;
                        break;
                }

                return true;
            }

            //Now we can check for draws
            if (this.GetEmptyCells().Length == 0)
            {
                Outcome = Outcome.Draw;
                return true;
            }

            //If execution reaches this point then no one has won, return false
            return false;
        }

        public List<Cell[]> GetEmptyLines()
        {
            var selection = new List<Cell[]>();

            for (int i = 0; i < this.cells.GetLength(0); i++)
            {
                var rows = new List<Cell[]>() { this.HorizontalRelatives(cells[i, i]), this.VerticalRelatives(cells[i, i]) };

                if (i == 1)
                {
                    rows.Add(this.DiagonalRelatives(cells[i, i]));
                    rows.Add(this.DiagonalRelatives2(cells[i, i]));
                }

                selection.AddRange(rows.FindAll(array => array.Length.Equals(3)));
            }

            return selection;
        }

        public Cell[] GetEmptyCells()
        {
            List<Cell> emptyCells = new List<Cell>();

            foreach (Cell cell in cells)
            {
                if (cell.Mark == Mark.Empty)
                {
                    emptyCells.Add(cell);
                }
            }

            return emptyCells.ToArray();
        }

        public Position IndexOf(Cell cell)
        {
            for (int x = 0; x < cells.GetLength(0); x++)
            {
                for (int y = 0; y < cells.GetLength(1); y++)
                {
                    if (cells[x, y].Equals(cell))
                    {
                        return new Position(x, y);
                    }
                }
            }

            //If code reaches this point, then it didn't find anything, return -1
            return new Position(-1, -1);
        }

        public Cell[] DiagonalRelatives(Cell cell)
        {
            var relatives = new List<Cell>();

            for (int x = 0; x < 3; x++)
            {
                if (cells[x, x].Mark.Equals(cell.Mark)) 
                { 
                    relatives.Add(cells[x, x]); 
                }
            }

            return relatives.ToArray();
        }

        public Cell[] DiagonalRelatives2(Cell cell)
        {
            var relatives = new List<Cell>();

            for (int x = 0; x < 3; x++)
            {
                if (cells[x, 2 - x].Mark.Equals(cell.Mark)) { relatives.Add(cells[x, 2 - x]); }
            }

            return relatives.ToArray();
        }

        public Cell[] HorizontalRelatives(Cell cell)
        {
            var relatives = new List<Cell>();
            int rowNum = this.IndexOf(cell).Y;

            for (int x = 0; x < 3; x++)
            {
                //Find row of cell
                if (cells[x, rowNum].Mark.Equals(cell.Mark)) { relatives.Add(cells[x, rowNum]); }
            }

            return relatives.ToArray();
        }

        public Cell[] VerticalRelatives(Cell cell)
        {
            var relatives = new List<Cell>();
            int colNum = this.IndexOf(cell).X;

            for (int y = 0; y < 3; y++)
            {
                //Find row of cell
                if (cells[colNum, y].Mark.Equals(cell.Mark)) { relatives.Add(cells[colNum, y]); }
            }

            return relatives.ToArray();
        }

        public Cell[] Where(Predicate<Cell> cellSelector)
        {
            var results = new List<Cell>();

            foreach (var cell in cells)
            {
                if (cellSelector.Invoke(cell))
                {
                    results.Add(cell);
                }
            }

            return results.ToArray();
        }

        public Cell Find(Predicate<Cell> cellSelector)
        {
            foreach (var cell in cells)
            {
                if (cellSelector.Invoke(cell))
                {
                    return cell;
                }
            }

            //If it doesn't find any cell that matches predicate conditions then return null
            return null;
        }

        public void Reset()
        {
            foreach (Cell cell in cells)
            {
                cell.Reset();
            }
        }

        public IEnumerator<Cell> GetEnumerator()
        {
            foreach (Cell cell in cells)
            {
                yield return cell;
            }
        }
    }

Position.cs

struct Position
    {
        public readonly int X;
        public readonly int Y;

        public Position(int x, int y) 
        {
            this.X = x;
            this.Y = y;
        }
    }

GameController.cs

    class GameController : IGamePresenter 
    {

        public Player[] Players { get; private set; }
        public event GameEndHandler GameEnd;
        public event PlayedEventHandler Played;
        public Grid Grid { get; private set; }

        public GameController(IGameViewer viewer) 
        { 
            Grid = new Grid(viewer);
            Players = new Player[2];
            Players[0] = new Player(Mark.Cross); // Always set to human 
            Players[1] = new AIPlayer(Mark.Nought, this); // Set to AI            
        }

        void IGamePresenter.PlayerChoice(Player player, Position position) 
        {
            //This is so the AI can start playing again when a new round is started
            (Players[1] as AIPlayer).DisallowPlay = false;

            // Presenter -> Model, place marker at coords
            Grid[position.X, position.Y].Mark = player.marker;

            // Model -> Presenter, if grid reaches an outcome end the game
            if (Grid.CheckOutcome(position, player)) 
            { 
                GameEnd(Grid.Outcome); 
            }

            //Raise Played Event
            Played(Grid[position.X, position.Y], player);  
        }

        void IGamePresenter.RestartGame() 
        {
            // Reset grid
            Grid.Reset();

            // Reset AIPlayer
            (Players[1] as AIPlayer).Reset();
        }
    }

Player.cs

class Player
    {
        public readonly Mark marker;
        public int Score { get; set; }

        public Player(Mark marker)
        {
            this.marker = marker;
        }

        public bool PlayerWon(Cell cell, Grid grid, bool checkDiagonals) 
        {
            return (grid.HorizontalRelatives(cell).Length == 3 || grid.VerticalRelatives(cell).Length == 3) ? true 
                    : (checkDiagonals) ?
                        (grid.DiagonalRelatives(cell).Length == 3 || grid.DiagonalRelatives2(cell).Length == 3) ? true : false 
                    : false;
        }
    }

AIPlayer.cs

   class AIPlayer : Player
    {
        private readonly IGamePresenter presenter;
        private readonly DecisionMaker decisionMaker;
        public int Turn { get; set; } // We aren't using this right now but it's good for state-based AIs
        public bool DisallowPlay { get; set; }

        public AIPlayer(Mark marker, IGamePresenter presenter) : base(marker)
        {
            this.presenter = presenter;
            decisionMaker = new DecisionMaker();
            Turn = new int();
            presenter.Played += DoTurn;
            presenter.GameEnd += new GameEndHandler(x => DisallowPlay = true); // Disable play for AI after game has been won
        }

        private void DoTurn(Cell cell, Player player)
        {
            //This check is necessary, otherwise we'll cause an infinite loop
            if (player is AIPlayer || DisallowPlay) 
            { 
                return;
            }

            var decision = decisionMaker.GetDecision(presenter.Grid, this);

            Turn++;
            Task.Delay(250).Wait(); // This is just a cosmetic thing, so it'll look like the AI needs some "thinking time"
            presenter.PlayerChoice(this, decision);
        }

        public void Reset()
        {
            Turn = 0;
            decisionMaker.Reset();
        }
    }
}

class Decision
    {
        public readonly Position Position;
        public readonly int Priority;

        public Decision(int priority, Position position)
        {
            Priority = priority;
            Position = position;
        }
    }

/// <summary>
    /// This is a very simple strategy that will first and foremost try to win and secondly try to force a draw.
    /// </summary>
    class BasicAlgorithm : IDecisionAlgorithm
    {
        private static Position[] corners = new Position[] { new Position(0, 0), new Position(2, 2) };
        private static Position[] corners2 = new Position[] { new Position(0, 2), new Position(2, 0) };
        private static Position middle = new Position(1, 1);
        private List<int> horizontalWin = new List<int>() { 0, 1, 2 };
        private List<int> verticalWin = new List<int>() { 0, 1, 2 };
        private bool diagonalWin = true;
        private bool diagonalWin2 = true;

        Position IDecisionAlgorithm.Invoke(Grid grid, AIPlayer player) 
        {
            var strategies = new Decision[] { StrategyOne(grid, player), StrategyTwo(grid, player) };

            return 
                (strategies[0].Priority == strategies[1].Priority) ? 
                    strategies[new Random().Next(1)].Position 
              : (strategies[0].Priority > strategies[1].Priority) ? 
                    strategies[0].Position : strategies[1].Position;
        }

        void IDecisionAlgorithm.Reset()
        {
            horizontalWin = new List<int>() { 0, 1, 2 };
            verticalWin = new List<int>() { 0, 1, 2 };
            diagonalWin = true;
            diagonalWin2 = true;
        }

        /// <summary>
        /// Tries to win the game, through horizontal, vertical diagonal lines. Priority returned will range from 0(no priority) to 
        /// 3 (absolute action).
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="player"></param>
        /// <returns>Decision</returns>
        private Decision StrategyOne(Grid grid, AIPlayer player)
        {
            // Start by analyzing board state to identify what wins that are possible
            foreach (Cell cell in grid)
            {
                if (cell.Mark.Equals(Mark.Cross))
                {
                    horizontalWin.RemoveAll(n => n.Equals(cell.Position.Y));
                    verticalWin.RemoveAll(n => n.Equals(cell.Position.X));

                    //If opponent has his marker in the middle then all diagonal wins are impossible
                    if (cell.Position.Equals(middle) && cell.Mark.Equals(Mark.Cross))
                    {
                        diagonalWin = false;
                        diagonalWin2 = false;

                    }
                    // For other cells different rules apply, as there are 3 horizontal and diagonal wins each
                    else if (cell.Mark.Equals(Mark.Cross))
                    {
                        if (corners.Contains(cell.Position)) // Check if diagonal win is possible
                        {
                            diagonalWin = false;
                        }

                        if (corners2.Contains(cell.Position))
                        {
                            diagonalWin2 = false;
                        }
                    }
                }
            }

            //Check if any type of win is possible
            if (horizontalWin.Count == 0 && verticalWin.Count == 0 && !diagonalWin && !diagonalWin2)
            {
                // In this case winning is impossible so we should then always return lowest priority from this strategy
                return new Decision(0, new Position());
            }

            //Now calculate which type of win to prioritize, starting by checking where we already have marks placed
            var friendlyCells = grid.Where(cell => cell.Mark.Equals(player.marker));

            //If we don't have any friendly marks placed then we will have to base our decision on any row where a win is possible
            if (friendlyCells.Length < 1)
            {
                //Get all empty rows
                var options = grid.GetEmptyLines();
                var rnd = new Random();

                //Since these are all equally viable options just randomize our choice between them all with priority 1.
                var decision = options[rnd.Next(options.Count)];
                // Each array will always contain 3 cells so cleaner with a static number here
                return new Decision(1, decision[rnd.Next(2)].Position); 
            } 
            else // Okay if we have friendly cells then we need to how many and assign each a unique priority
            {
                var options = new List<Tuple<int, Position>>();

                foreach (var cell in friendlyCells)
                {
                    var horizontalNeighbours = grid.HorizontalRelatives(cell);
                    var verticalNeighbours = grid.VerticalRelatives(cell);
                    var diagonalNeighbours = grid.DiagonalRelatives(cell);
                    var diagonalNeighbours2 = grid.DiagonalRelatives2(cell);

                    //Now check if a win can be achieved in Y-axis
                    if (horizontalWin.Contains(cell.Position.Y))
                    {
                        // Okay since horizontal wins are OK at this point then just find the cell and add it to the list
                        // The priority is calculated as if (number of neighbours == 2) then priority = 3 else priority = 1.
                        options.Add(Tuple.Create((horizontalNeighbours.Length == 2) ? 3 : 1, grid.Find(
                            (entry) => 
                                entry.Position.Y.Equals(cell.Position.Y) && 
                                entry.Mark.Equals(Mark.Empty))
                                .Position)); 
                    }

                    //Same thing here but X-axis instead
                    if (verticalWin.Contains(cell.Position.X))
                    {
                        options.Add(Tuple.Create((verticalNeighbours.Length == 2) ? 3 : 1, grid.Find(
                            (entry) =>
                                entry.Position.X.Equals(cell.Position.X) &&
                                entry.Mark.Equals(Mark.Empty))
                                .Position)); 
                    }

                    if (diagonalWin && corners.Any(pos => pos.Equals(cell.Position)) || diagonalWin && cell.Position.Equals(middle)) //Only check for diagonal wins if cell is in a corner
                    {
                        options.Add(Tuple.Create((diagonalNeighbours.Length == 2) ? 3 : 1, grid.Find(
                            (entry) => 
                            corners.Any(pos => pos.Equals(entry.Position)) && entry.Mark.Equals(Mark.Empty) || 
                            entry.Position.Equals(middle) && entry.Mark.Equals(Mark.Empty)).Position));
                    }

                    if (diagonalWin2 && corners2.Any(pos => pos.Equals(cell.Position)) || diagonalWin2 && cell.Position.Equals(middle)) 
                    {
                        options.Add(Tuple.Create((diagonalNeighbours2.Length == 2) ? 3 : 1, grid.Find(
                            (entry) =>
                            corners2.Any(pos => pos.Equals(entry.Position)) && entry.Mark.Equals(Mark.Empty) ||
                            entry.Position.Equals(middle) && entry.Mark.Equals(Mark.Empty)).Position));
                    }
                }

                //If it doesn't find any neighbouring cells that can win just place marker on an empty valid space
                if (options.Count < 1)
                {
                    var emptyRows = grid.GetEmptyLines();
                    var rnd = new Random();

                    //Since these are all equally viable options just randomize our choice between them all with priority 1.
                    var decision = emptyRows[rnd.Next(options.Count)];
                    // Each array will always contain 3 cells so cleaner with a static number here
                    return new Decision(1, decision[rnd.Next(2)].Position); 
                }

                //Sort dictionary by key value
                var sortedOptions = options.OrderByDescending(entry => entry.Item1);

                //Okay now first check if we have more than one entry with the same priority
                if (sortedOptions.Where(entry => entry.Item1.Equals(sortedOptions.First().Item1)).Count() > 1)
                {
                    var selection = sortedOptions.Where(entry => entry.Item1.Equals(sortedOptions.First().Item1)).ToList();
                    return new Decision(sortedOptions.First().Item1, selection[new Random().Next(selection.Count)].Item2);
                } 
                else 
                {
                    return new Decision(sortedOptions.First().Item1, sortedOptions.First().Item2);
                }
            }
        }

        /// <summary>
        /// Will attempt to force a draw by analyzing board state and opponent mark placements and attempting to block them.
        /// Priority can never exceed 2 so a high-probability win will always take precedent over this strategy.
        /// </summary>
        /// <param name="board"></param>
        /// <param name="player"></param>
        /// <returns>Decision</returns>
        private Decision StrategyTwo(Grid grid, AIPlayer player)
        {
            //Start by getting each X-marked cell
            var unfriendlyCells = new List<Tuple<int,Cell>>();
            var emptyCells = grid.GetEmptyCells();

            foreach (var cell in grid)
            {
                if (cell.Mark.Equals(Mark.Cross))
                {
                    unfriendlyCells.Add(Tuple.Create(1, cell)); //Set these to priority 1 by default
                }
            }

            var prioritizedOptions = new List<Tuple<int,Position>>();

            //Now get all relatives + empty cells of those X-marked cells
            foreach (var option in unfriendlyCells)
            {
                int horizontalNeighbours = grid.HorizontalRelatives(option.Item2).Length;
                var emptyHorizontalCells = emptyCells.Where(entry => entry.Position.Y.Equals(option.Item2.Position.Y));
                int verticalNeighbours = grid.VerticalRelatives(option.Item2).Length;
                var emptyVerticalCells = emptyCells.Where(entry => entry.Position.X.Equals(option.Item2.Position.X));
                int diagonalNeighbours = grid.DiagonalRelatives(option.Item2).Length;
                var emptyDiagonalCells = emptyCells.Where(entry => corners.Any(corner => corner.Equals(entry.Position)));
                int diagonalNeighbours2 = grid.DiagonalRelatives2(option.Item2).Length;
                var emptyDiagonalCells2 = emptyCells.Where(entry => corners2.Any(corner => corner.Equals(entry.Position)));

                if(horizontalNeighbours > 1 && emptyHorizontalCells.Count() == 1) 
                {
                    //If we have 1 neighbouring X-cell + 1 empty cell then we must block them off with the highest priority
                    prioritizedOptions.Add(Tuple.Create(2, emptyHorizontalCells.First().Position));
                }

                if (verticalNeighbours > 1 && emptyVerticalCells.Count() == 1)
                {
                    prioritizedOptions.Add(Tuple.Create(2, emptyVerticalCells.First().Position));
                }

                if (diagonalNeighbours > 1 && emptyDiagonalCells.Count() == 1)
                {
                    prioritizedOptions.Add(Tuple.Create(2, emptyDiagonalCells.First().Position));
                }

                if (diagonalNeighbours2 > 1 && emptyDiagonalCells2.Count() == 1)
                {
                    prioritizedOptions.Add(Tuple.Create(2, emptyDiagonalCells2.First().Position));
                }
            }

            /*For now if there's more than one prioritized block entry then we just randomly choose one, later on we should use
             * extra analysis to determine if one block can succesfully block out two axises. */

            if (prioritizedOptions.Count < 1)
            {
                //If there are no priority 2 options then filter out all empty cells that are within the same axis as a X-marked cell
                var options = emptyCells.Where(
                    (entry) => 
                        unfriendlyCells.Any(cell => cell.Item2.Position.X.Equals(entry.Position.X)) ||
                        unfriendlyCells.Any(cell => cell.Item2.Position.Y.Equals(entry.Position.Y))).ToArray();

                //Randomly return one of them
                return new Decision(1, options[new Random().Next(options.Length)].Position);
            } 
            else
            {
                return new Decision(2, prioritizedOptions[new Random().Next(prioritizedOptions.Count)].Item2);
            }
        }
    }

Answer 1

Fields

I see a property Cells but it is never used either in Grid or any other class (as far as I can tell).

Order your class members like this:

• Constants
• Fields
• Properties
• Methods

This makes it easier for people to read the code and have an expectation of where they can find what.

Naming

index and index2 aren't very descriptive names. Consider naming them according to their purpose: row and column.

Your method CheckOutcome returns a bool which is cleared up in the comments inside the method that true means someone won and false nobody won. The current method name would suggest a void return type, perhaps returning a control-variable (like -1 or true/false for errors) or an exception. If you change it to, for example, HasWinner then the intent is immediately more clear.

You have a property called DisallowPlay, which is the inversion of AllowPlay. People find it easier to read the positive version and things like AllowPlay = true make more sense than DisallowedPlay = false.

I would change DiagonalWin and DiagonalWin2 to DiagonalWinLeftTop and DiagonalWinRightTop (or similar values). That way you know what diagonal it is exactly.

Magic values

Magic values are values that look like they're placed there randomly. Consider adding context to make this immediately clear.

For example:

var corners = new Position[] { new Position(0,0), new Position(2,0), new Position(0,2), new Position(2,2) };

could become

int boundary = MAX_CELLS - 1;
var corners = new Position[] { new Position(0,0), new Position(boundary ,0), new Position(0, boundary ), new Position(boundary , boundary) };

Added benefit: now it's also easier to provide support for bigger playfields, you just have to manipulate the MAX_CELLS constant.

Consistency

I prefer == over .Equals(). It gives me less the feeling as if the code is all cluttered which makes me feel all happy and fluffy. You use == everywhere as well, so unless you overloaded the operator (which I can't tell), I would change

cells[x, y].Equals(cell)

to

cells[x, y] == cell

404 values

-1 is a common way to express "not found" when you're expecting an integer but using the same approach to fill a referency type's fields is not the intention. How is the programmer supposed to know if he should check position.x? Or position.y? Maybe both?

In rare cases, returning null is an appropriate solution. I would say that this is one of them (method: public Position IndexOf(Cell cell)).

I notice there is never any check done to see if the cell is invalid so I assume you just work with them and let the program flow iterate over it like a valid position. I don't know how the code works in depth but keep in mind that this means some properties might not get initialized because they get skipped somewhere which in turn can cause a NullReferenceException elsewhere where they get read.

Initialization

This is not needed:

Turn = new int();

Threading

I'm not very experienced with multithreading but unless I'm mistaking, you're putting the UI thread to sleep here:

Task.Delay(250).Wait();

It's still a low value so it wouldn't matter too much but should you go to higher values I would add some sort of visual feedback so the user can distinguish between the AI "thinking" and the program crashing.

Random

You're creating a Random object inside a method. This is a dangerous approach because it uses a time-based seed so if there are 2 very close method calls, there will not have enough time passed. Consider creating an instance once on class level and calling .Next() on that field.

You're actually using several Random instances throughout your code so they can all benefit from this.

---

Conclusion

Overall the code seems pretty nice. There's still quite a bit of duplication and I think abstracting a few concepts in classes and interfaces might be a solution to remove some duplication, but overall it is good. The main remarks are style-wise.

Answer 2

Grid -> public Cell this[int index, int index2]

I'm not pro but I think that:

• you should create function for checking if index is validate - you use same ugly condition twice.
• you could not check if index is correct at all... Does it matter if you get ArgumentOutOfRangeException or default IndexOutFoRangeException?

Thanks to this change you can remove 15 lines of code.