15,798,673 members
Articles / Artificial Intelligence

# Tic Tac Toe Using AI –The Easy Way

Rate me:
27 Jan 2019CPOL7 min read 17.2K   535   13   8
A simple invincible implementation of Tic Tac Toe

## 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:

C#
```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.

C#
```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.

C#
```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.

C#
```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.

C#
```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.

C#
```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.

C#
```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.

C#
```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.

C#
```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:

 Total Wins For X 364 Total Wins For O 0 Total Draws 125 Total Games 489 Total Moves 2673

## 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

• 27th January, 2019: Initial version

Written By
Student
Wales
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 [My vote of 2] Using AI? Civilised Barbarian29-Jan-19 4:03 Civilised Barbarian 29-Jan-19 4:03
 Re: [My vote of 2] Using AI? George Swan29-Jan-19 5:32 George Swan 29-Jan-19 5:32
 Re: [My vote of 2] Using AI? Civilised Barbarian29-Jan-19 7:11 Civilised Barbarian 29-Jan-19 7:11
 Re: [My vote of 2] Using AI? Member 819653429-Jan-19 9:01 Member 8196534 29-Jan-19 9:01
 Re: [My vote of 2] Using AI? George Swan29-Jan-19 11:41 George Swan 29-Jan-19 11:41
 Re: [My vote of 2] Using AI? Civilised Barbarian29-Jan-19 13:06 Civilised Barbarian 29-Jan-19 13:06
 Re: [My vote of 2] Using AI? George Swan29-Jan-19 17:00 George Swan 29-Jan-19 17:00
 The reason that I mentioned AI in the title was to differentiate the application from those that simply allowed two people to play against each other. I wished to indicate, in a succinct manner, that the application mimicked the actions and reactions of a human player. It did not seem to me to be unreasonable to describe that sort of behaviour as ‘using artificial intelligence’.
 Re: [My vote of 2] Using AI? George Swan29-Jan-19 21:15 George Swan 29-Jan-19 21:15
 Last Visit: 31-Dec-99 19:00     Last Update: 10-Dec-23 14:53 Refresh 1