Tic Tac Toe Using AI –The Easy Way

• Download source - 288 KB

Introduction

Some of the apps that use AI to play Tic Tac Toe against an opponent are incredibly complicated. This piece describes a simple strategy-based approach without using recursive algorithms or a complex database of stored moves. It should be stated, at this stage, that ‘using AI’ refers to the sample application’s ability to mimic the actions and responses of a human player, in contrast to apps that simply allow two people to play against each other. It’s not an exercise in machine learning. It’s more of an example of how to use the chain of responsibility pattern to implement a structured response to moves made by a human opponent.

The Basic Strategy

The idea here is to divide the nine square matrix that forms the board into a series of eight lines. Each line has three squares. If any one player occupies all three of the squares in a line, they win the game. So the lines consist of the 3 rows, 3 columns and two diagonals that make up the board matrix. The AI appraises the state of the lines before making its move.

Appraising a Line

The appraisal needs to be done in a systematic manner. The first thing to check for is a potentially winning line. That’s a line where the AI has already occupied 2 of the 3 squares and the third square is empty. The next thing, if no win is found, is to see if the opponent can win on the following move. The move made in response to this situation is a forced move in the sense that the game is lost if the move is not played. There’s another forced move that’s not quite as obvious and that’s where the opponent has the opportunity to open up 2 winning lines on their next move. The situation where there are two winning lines is called a fork.

Preventing Forks

In the example above, there is a potential fork involving the line with the squares from column 0 and the line with the squares from row 2. A potential fork involves two lines that share a common square, in this case it’s at index 6 in the squares array. Both lines are occupied by the same player but each line has only a single square occupied and that square is not the shared square. When this situation is detected, there is a potential fork. The defence is to block one of the two lines.

Above is a double fork involving lines Column 0 Row 2 and Column 2 Row 0. The defence is the same as for a single fork – block one of the lines. But here, PlayerX must not take a corner square. So a fork prevention move should look to take the centre square in the line’s three square array before choosing another square. When the AI has checked for winning lines and potential forks and has found none, it is in a position to play a strategic move.

Strategic Moves

All squares on the board are not of equal value. The centre square is the most powerful square as it is shared between four lines. The next most powerful are the four corner squares, these squares are shared by three lines. It could be said that the centre square has an impact value of 4 and the corner squares have an impact value of 3. But this assumes that all the lines that share those squares are active. This is not always the case. A line that’s already occupied by both players is effectively redundant, so the square’s presence in that line should not count towards the square’s impact value. Adopting the strategy of taking the square with the highest impact value will always result in the AI occupying the centre square, if it’s available, or a corner square if it’s not. This is essential in order tp avoid the losing scenario show below.

PlayerO has failed to take a corner square after PlayerX took the centre and has lost the game.

Implementing the Strategy in Code

The trick here is to use the chain of responsibility pattern to avoid multiple and nested if then else statements in the method that returns the AI’s (PlayerX) move. So that the method becomes:

public Move MoveX(IBoard board)
       {
           this.board = board;
           moveHandler.ReSet(board);
           Move result = moveHandler.
                HandleXWin().
                HandleOWinOnNext().
                HandlePossibleFork().
                HandleStrategicMove().Result;
           return result;
       }

The MoveHandler methods in the chain each return the instance of the MoveHandler class. This arrangement enables consecutive methods to be called using the format shown above. All the methods follow a similar pattern as can be seen in the HandleXWin method.

public MoveHandler HandleXWin()
    {
        if (IsHandled) return this;

        if (gameScorer.BestScoreX == Constants.WinOnNextMove)
        {
            //this is a winning Line it has 2 X and 0 O
            lineService.TryFindEmptySquare(gameScorer.BestLineX, out int index);
            Result.Index = index;
            Result.MoveResult= GameState.Xwin;
            IsHandled = true;
        }
        return this;
    }

It first checks to see if the move has already been handled and returns the MoveHandler instance if it has. If the move is unhandled and it can handle the move, the Result variable, which is of type Move, has its Index property set to the index of the move, its MoveResult property set to the resulting GameState and the IsHandled bool is set to true. The method ends by returning the instance of the MoveHandler. The Result variable’s value is returned after the last method in the chain has been called.

public enum GameState
{
    InPlay,
    Xwin,
    Owin,
    Draw,
    SearchCompleted//debugging
}
public struct Move
{
   public int Index;
   public  GameState MoveResult;
}

Using Helper Classes

The methods in the chain are reduced to a few lines of code by employing helper class.

public MoveHandler HandleOWinOnNext()
  {
      if (IsHandled) return this;
      if (gameScorer.BestScoreO == Constants.WinOnNextMove)
      {
          //O could win on its next move if the line is not blocked now
          lineService.TryFindEmptySquare(gameScorer.BestLineO, out int index);
          Result.Index = index;
           IsHandled = true;
      }
      return this;
  }

  public MoveHandler HandleStrategicMove()
  {
      if (IsHandled) return this;
      int index = gameScorer.GetBestImpactSquare();
      Result.Index = index;
      IsHandled = true;
      return this;
  }
  public MoveHandler HandlePossibleFork()
  {
      if (IsHandled) return this;
      if (lineService.TrySelectAntiForkSquare(board, out int index))
      {
          Result.Index = index;
          IsHandled = true;
      }
      return this;
  }

The GameScorer helper class updates the impact values of empty squares.

private void UpdateImpactScores()
   {
       ResetImpactScores();
       foreach (var line in lines)
       {
           if (!line.IsLineBlocked )
           {
               UpdateImpactScoresForLine(line);
           }
       }
   }
   private void UpdateImpactScoresForLine(Line line)
   {
       for (int i = 0; i < 3; i++)
       {
           if (line.Squares[i].IsEmpty)
           {
               ImpactScores[line.Squares[i].BoardIndex] += 1;
           }
       }
   }

The LineService class looks for potential forks.

public bool TrySelectAntiForkSquare(IBoard board, out int result)
 {
     int[,] cornerLines = board.CornerLines;
     for (int i = 0; i < cornerLines.GetLength(0); i++)
     {
         if (board.Lines[cornerLines[i, 0]].OScore == 1
             && board.Lines[cornerLines[i, 1]].OScore == 1
             && board[cornerLines[i, 2]].Content != 'O')
         {

             return  TryFindEmptySquare(board.Lines[cornerLines[i, 0]],out result);
         }
     }
     result = -1;
     return false;
 }

The cornerLines variable is a three column int array, the first and second columns contain the index numbers for the two lines that make up the corner and the third column has the index number of the shared square.

The Content Changed Event

The Square class raises a SquareContentChangedEvent when its contents change. The Line class uses the event to update its own properties.

public class Line
{
    public Square[] Squares = new Square[3];
    public int Ocount { get; private set; }
    public int Xcount { get; private set; }
    public int XScore { get; set; }
    public int OScore { get; set; }
    public bool IsLineOblocked => Xcount > 0;
    public bool IsLineXblocked => Ocount > 0;
    public bool IsLineBlocked => IsLineOblocked && IsLineXblocked;
    public Line(Square c0, Square c1, Square c2)
    {
        Squares[0] = c0;
        Squares[1] = c1;
        Squares[2] = c2;
        foreach (var square in Squares)
        {
            square.SquareContentChangedEvent += SquareChangedEventHandler;
        }
        Update();
    }

    private void SquareChangedEventHandler(object sender, System.EventArgs e)
    {
        Update();
    }

    public void Update()
    {
        Xcount = 0;
        Ocount = 0;
        foreach (var square in Squares)
        {
            if (square.Content == 'X') Xcount++;
            if (square.Content == 'O') Ocount++;
        }
        XScore = IsLineXblocked ? 0 : Xcount ;
        OScore = IsLineOblocked ? 0 : Ocount ;
    }
}

The Game Engine

The game is progressed in the Play method of the Game class.

private Move Play()
  {
      inputOutputService.ShowBoard(board);
      char firstPlayer = inputOutputService.GetIsYes(Constants.PromptGoFirst) ? 'O' : 'X';
      char[] Players = firstPlayer == 'O' ? new char[] { 'O', 'X' } : new char[] { 'X', 'O' };
      int moveNumber = 0;
      Move move;
      move.MoveResult = GameState.InPlay;
      move.Index = -1;
      while (move.MoveResult == GameState.InPlay)
      {
          char player = Players[moveNumber % 2];
          move = player == 'X' ? MoveX(board) : MoveO();

          board[move.Index].Content = player;
          moveNumber++;
          if (player == 'X')
          {
              inputOutputService.ShowBoard(board);
          }
          if (move.MoveResult == GameState.InPlay && moveHandler.IsGameADraw())
          {
              move.MoveResult = GameState.Draw;
          }
      }
      inputOutputService.OutputGameResult(move, board);
      return move;
  }

The game continues so long as the GameState variable of the Move struct that’s returned after every move has a value of InPlay.

Infallibility Testing

For the app to be considered infallible, the AI must be able to handle all the possible move sequences for its opponent, PlayerO. There are 9 ways of making the first move and for each of the first moves, there are 7 ways of playing the third move, (playerO’s second move), and so on. A recursive algorithm should be able to implement this scenario.

private GameState PlayRecursiveMove(IBoard board, int depth, bool isPlayerO)
 {
     var unoccupiedSquares = board.GetUnOccupiedSquaresIndexes().ToList();
     IBoard newBoard;
     GameState result = GameState.InPlay;
     if (isPlayerO)
     {
         for (int i = 0; i < unoccupiedSquares.Count; i++)
         {
             result = GameState.InPlay;
             newBoard = board.Clone();
             newBoard[unoccupiedSquares[i]].Content = 'O';
             //debugging aid, stores move sequence
             moves[depth] = unoccupiedSquares[i];
             if (newBoard.Lines.Any((l) => l.OScore == Constants.WinningScore
                                          && result == GameState.InPlay))
             {
                 inputOutputSerice.ShowBoard(newBoard);
                 OWinCount++;
                 totalMoves += unoccupiedSquares.Count + 1;
                 result = GameState.Owin;
             }
             if (newBoard.GetOccupiedSquaresCount() == Constants.TotalSquares
                                          && result == GameState.InPlay)
             {
                 DrawCount++;
                 totalMoves += Constants.TotalSquares;
                 result = GameState.Draw;

             }
             if (result == GameState.InPlay)
             {
                 result = PlayRecursiveMove(newBoard, depth + 1, false);
             }
         }
         return GameState.SearchCompleted;
     }
     #region PlayerX
     newBoard = board.Clone();
     var move = MoveX(newBoard);
     newBoard[move.Index].Content = 'X';
     moves[depth] = move.Index;
     if (newBoard.Lines.Any((l) => l.XScore == Constants.WinningScore))
     {
         XWinCount++;
         totalMoves += unoccupiedSquares.Count + 1;
         return GameState.Xwin;
     }
     if (newBoard.GetOccupiedSquaresCount() == Constants.TotalSquares)
     {
         totalMoves += Constants.TotalSquares;
         DrawCount++;
         return GameState.Draw;
     }

     return PlayRecursiveMove(newBoard, depth + 1, true);
     #endregion
 }

Firstly, the method iterates through a list of every empty square that’s available. It plays a move for PlayerO to the current square in the iteration and checks for a result. If there is no result, the method is called again with the IsplayerO bool set to false. This results in the AI making its move at the next level down in the recursion. If there is no result, the method is called again, this time with IsPlayerO being set to true and a new iteration is started at the new level. When a result is found on the AI’s move, the method returns to the previous level and the next square in the iteration is selected as a move for PlayerO. Similarly, when a result is found on PlayerO’s turn, the next square in the iteration is selected. This continues until the iteration completes and the method returns to the previous level. The AI does nothing with the returned result other than to pass it up to the previous level. The next level up is PlayerO’s turn and the sequence is repeated until all the combination of moves has been exhausted. Here are the results:

Conclusion

It’s possible to play a very strong game of tic tac toe without the need for recursion or a database of stored moves.

History

• 27^th January, 2019: Initial version