Download Tic Tac Toe Project
Introduction
This is kind of a fun project that I've been toying with for a little while now. I realize Tic Tac Toe is an extremely simple game and it might seem more interesting to write a program that played something like, for example, chess. But I found this project interesting and it required me to think through a couple of things that would be helpful in writing a more sophisticated gaming engine.
Playing Strategies
The most interesting part of the code for me is the part where the computer makes a move. Not only must the computer make a legal move, but the goal is to employ a heuristic where it can play at least as well as a human player. As you might guess, Tic Tac Toe does not require a very advanced algorithm to accomplish this. But, in thinking about the game, there is actually a slight strategy that can be used to increase the odds that you win the game.
Specifically, there are times when a move is possible that will result in two possible wins on the next move. In this case, the other player can block one win but not both and so the first player can win the game. For example, look at the screenshot above. It is O's turn to move but X has two winning paths that must be blocked. O can block one of them (top left or middle right) but not both and so X will win this game.
And so I tried to incorporate this tactic into the algorithm used in my code.
Looking at the Code
There's too much code to list it all in the article but I'll show some of the code that I find more interesting. Download the attached project for the complete game engine class along with a Win Forms application that uses the game engine to play the game.
Listing 1 shows the AutoMove() method from my TicTacToeEngine class. This method attempts to make a intelligent move on behalf of the current player.
Listing 1: Method to Make a Tic-Tac-Toe Move on Behalf of the Computer
/// <summary>
/// Uses heuristics to make the best move for the current player.
/// </summary>
public void AutoMove()
{
if (GameIsOver)
return;
// Can player win?
Random random = new Random();
WinPath pathToWin = WinPaths.Where(p => p.MovesToWin(Grid, CurrentPlayer) == 1).Random(random);
if (pathToWin != null)
{
var move = pathToWin.First(m => Grid[m.Row, m.Column] == TicTacToePlayer.None);
Move(move.Row, move.Column);
return;
}
// Do we need to block win from other player?
TicTacToePlayer otherPlayer = CurrentPlayer.GetOtherPlayer();
WinPath pathToLose = WinPaths.Where(p => p.MovesToWin(Grid, otherPlayer) == 1).Random(random);
if (pathToLose != null)
{
var move = pathToLose.First(m => Grid[m.Row, m.Column] == TicTacToePlayer.None);
Move(move.Row, move.Column);
return;
}
// Get additonal information about available moves
var movesAvailable = GetMoves(TicTacToePlayer.None);
Debug.Assert(movesAvailable.Count > 0);
// Score available moves according to the number of moves required to complete
// each potential win
foreach (var move in movesAvailable)
{
// Create grid to test this move
var grid = (TicTacToePlayer[,])Grid.Clone();
grid[move.Row, move.Column] = CurrentPlayer;
// Score move based on number of moves required for each potential win
move.UserData = (int)WinPaths.Sum(p => {
int count = p.MovesToWin(grid, CurrentPlayer);
return (count < 0) ? count : (GridSize - count);
});
}
// Make move with the highest score
int maxScore = movesAvailable.Max(m => m.UserData);
var mov = movesAvailable.Where(m => m.UserData == maxScore).Random(random);
Move(mov.Row, mov.Column);
return;
}
The first thing the code does is check to see if the game has ended, in which case no move can be made. Next, the computer looks to see if a win is possible. It does this by searching the WinPaths member. WinPaths contains a collection of winning paths. Each winning path is a collection of moves, or grid cells, where, if all cells are occupied by the same player, then that player will have won the game.
If a win is possible, nothing else matters and the algorithm will win the game. In the case where more than one winning move is possible, the method randomly selects one of them using my Random() extension method. I use this Random() method in several places to try and maximize the variations from game to game. You can read more about this and related methods in my article Extending LINQ with Random Operations.
If the game cannot be won on this move, the code next looks to see if a winning move from the other player must be blocked. If this is the case, that move is taken. Again, if more than one such move is available, one is randomly selected.
If no win is possible on this move and no win from the other player needs to be blocked, things get a little more interesting. The code starts by getting a list of all available moves (moves that have not already been taken) and rates each move to decide which one to take.
How to rate each possible move was not at all obvious to me. As I thought the game through, I saw a couple of things to consider. For example, you could look for the path that requires the smallest number of moves to win, but that's not always very smart. The other player can just do whatever they want to do until you have one move remaining and then just block you. Also, as mentioned before, I wanted the algorithm to look for cases where it creates multiple winning paths in the hopes of creating two wins that must be blocked.
The approach I took takes both conditions into consideration. For each move, a score is generated based on the number of moves that would then be required for a win (less moves needed results in a higher score). But this score includes all possible wins. So, for example, if one move would result in two paths requiring only one move to win, the score from the two paths are added together for an even higher score. The code then randomly picks a move from those moves with the highest score (in case there are more than one) and takes it.
Other Features
My TicTacToeEngine class offers a couple of options to give it more flexibility. For example, you can specify a different grid size if a 3x3 grid gets boring (however, it does require that the number of rows and columns are the same). Of course, it's easy to control which side the computer plays and who goes first from calling methods in the appropriate order.
The class also fires a number of events for things such as when the game grid has changed, when a player has moved, and when the game has ended. This makes it easy for an application to update the display appropriately. (My game engine class does not render anything.) Once the game has ended, there are several properties for determining which, if any, player won the game, and also the winning path (list of moves that won the game).
Conclusion
That's all there is to it. You can download the project if you'd like to take a closer look. The heuristic I employed for making a move seems reasonable but I still wonder if it could be better. If you see a better algorithm for that code, I'd love to hear about it.
End-User License
Use of this article and any related source code or other files is governed
by the terms and conditions of
.
Author Information
Jonathan Wood
I'm a software/website developer working out of the greater Salt Lake City area in Utah. I've developed many websites including Black Belt Coder, Insider Articles, and others.