59
Posted January 26, 2011 by Spyros in C/C++ Programming
 
 

How to Code a Tic Tac Toe Game in C++ Including Artificial Intelligence Opponent

tic_tac_toe
tic_tac_toe

This post is going to be a bit longer than my usual posts. Some years ago, i wrote a small tic tac toe game in c++ (using visual studio as my IDE). I was mainly focusing on creating an artificial intelligent opponent for that game and wanted to actually create a minimax type algorithm. Therefore, i decided to code this code, as a means to create a rival whom i wouldn’t be able to beat (or at least, it would be hard to).

Before even starting this post, i must say that i have included the source code of my game for those of you who want to take a look at it. You can find it in this link :

Download Tic Tac Toe Game Source Code

Interestingly, the opponent that i’ve created is pretty good, can’t be beaten easily (i think there is only way or such). Creating a game like tic tac toe is actually pretty simple, but what is pretty important is the way that the artificial intelligence algorithm works. As i’ve mentioned, i’ve used a minimax variant. Take a look at this comment at my source code :

/////////////////////////////////////////////////////////////////////
// 3*x2 + x1 – ( 3*O2 + O1 )
// x2 = number of rows,columns or diagonals with 2 Xs and zero Os
// x1 = number of rows,columns or diagonals with 1 X and zero Os
// O2 = number of rows,columns or diagonals with 2 Os and zero Xs
// O1 = number of rows,columns or diagonals with 1 Os and zero Xs
//
// X represents cpu = 1
// O represents human = 2
//
// Heuristic function for MinMax Algo is here
/////////////////////////////////////////////////////////////////////

A minimax algorithm is about creating a function that evaluates a certain position of the game. The idea is that we include two players for evaluating the position. The first player is represented by X (the cpu), and the actual human player is represented with O.

A position is evaluated in a simple way. Each of the two players gets a score representing his current position in the game. Suppose that we have a grid like :

| O | O |   |

|     | X |    |

|      |     |    |

X for cpu, O for human and now is the CPU’s turn. Our algorithm has to correctly evaluate the position and add its X to the position 3 of the tic tac toe grid. The idea now is to evaluate every possible position. As you see, there are 5 possible positions for the computer to place its mark. Let’s evaluate each one, according to the algorithm above :

Placing X at Position 3 => 3*x2 + x1 – ( 3*O2 + O1 ) => 3*1 + 2 – (3*0 + 1) = 4

Placing X at Position 4 => 3*x2 + x1 – ( 3*O2 + O1 ) => 3*1 + 1 – (3*1 ) = 1

Placing X at Position 6 => 3*x2 + x1 – ( 3*O2 + O1 ) => 3*1 + 1 – (3*1 + 1) = 0

Placing X at Position 7 => 3*x2 + x1 – ( 3*O2 + O1 ) => 3*1 + 2 – (3*1) = 2

Placing X at Position 8 => 3*x2 + x1 – ( 3*O2 + O1 ) => 3*0 + 3 – (3*1 + 1) = -1

Placing X at Position 9 => 3*x2 + x1 – ( 3*O2 + O1 ) => 3*0 + 3 + (3*1 + 1) = -1

Take a look at the evaluations. Placing X at position 3 is the one that produces the best score and is indeed the best move that we could make ! Actually, any other move would result in our loss, so the algorithm evaluates the position correctly and the cpu makes the best move to defend itself.

Now that we understood how the algorithm works, let’s take a close look at the actual c++ code. After some standard introductory text, we enter the game loop :

	Triliza = new CMyTriliza();
	while (1)
	{
		Triliza->VerifyFirstPlayer();
		Triliza->TrilizaLoop();

		if (!Triliza->PlayAgain())
			break;
	}

Simply, there is a loop that verifies who the first player is (computer or user) and then starts the actual Tic Tac Toe loop. In the end, if the player decides not to play anymore, we just exit the loop and main(). Let’s take a look at the main tic tac toe loop function :


void CMyTriliza::TrilizaLoop()
{
	if (DoIPlayFirst)
	{
		while (NumberOfMovesPlayed<=8)
		{
			MakeCPUMove();  // CPU plays first here..
			if (IsFormed)
				break;
			if (NumberOfMovesPlayed!=9)
				MakeHumanMove();
			if (IsFormed)
				break;
		}
		if (!IsFormed)
			cout << "\\nNobody wins..That's OK,i'll win next time..\\n";
	}
	else
	{
		while (NumberOfMovesPlayed<=8)
		{
			MakeHumanMove();  // Human plays first here..
			if (IsFormed)
				break;
			if (NumberOfMovesPlayed!=9)
				MakeCPUMove();
			if (IsFormed)
				break;
		}
		if (!IsFormed)
			cout <<"\\nNobody wins..How can i win if i don't play first ?\\n";
	}
}

As long as 9 moves have not been played, the game still goes on. If you check the MakeCPUMove function, you will notice that it does what we described beforehand. It begins to check and evaluate each possible way that the computer can play, in order to decide what is best. Everything should be pretty straightforward here. The most important function, though, is the evaluation function :

int CMyTriliza::EvaluatePosition()
{
	if (GetMarkValue(3,0))
		return 30;
	else if (GetMarkValue(0,3))
		return 30;
	else if (CheckForPitFalls())
		return -30;
	else
	{
		int X2 = GetMarkValue(2,0);  // determine x2 number
		int X1 = GetMarkValue(1,0);  // determine x1 number
		int O2 = GetMarkValue(0,2);  // determine O2 number
		int O1 = GetMarkValue(0,1);  // determine O1 number
		return 3*X2 + X1 - (3*O2 + O1);
	}
}

GetMarkValue(int Xs, int Os) is a function that simply checks how many rows, columns and diagonals contain a specified number of Xs and Os. As we saw in detail above, this is needed for the minimax algorithm. CheckForPitFalls() is just a function that fixes some of the things that the main minimax algorithm cannot properly handle. This serves as a way to make the cpu a better player.

Hope that everything here makes sense. Don’t hesitate to drop a comment in order to ask anything about this code. I would be really glad to listen to your critics, advices and questions.


articificial intelligence tic tac toe c++ game code a game in c++ create a game in c++ minimax algorithm tic tac toe in c++

Spyros

 


More articles by »