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

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.

Would you please check my code here:http://www.cplusplus.com/forum/beginner/44450/

and tell me how should I incorporate this function there?

Nisheeth, please register yourself at the forum and make your question there. We can discuss much better in the forum instead of the post’s comments.

hello

Thank you for this code ….I have an question please help me:

If i want to change this code for the 15*15 Tic Tac Toe ,I must compute the X4,X3,X2,X1,O4,O3,O2,O1???

thanks alot

@zahra, this makes things more complicated and would probably need a whole new strategy and other algorithmic approaches.

Hi

Thanks for your attention

Your code has a small problem:

If the human Opponent selects the same that Computer Opponent selects,the value of that cell change from O to X!

I solve this problem with a While:

void CMyTriliza::MakeHumanMove()

{

if (IsATrilizaFormed())

{

IsFormed = true;

cout <9 || move<1)

{

cout <> move;

while(TrilizaMarks[move-1]==’1′)

{

cout<>move;

}

}

TrilizaMarks[move-1] = 2;

NumberOfMovesPlayed++;

}

DrawTriliza();

}

oh…my Previous comment failed….my While Loop is this:

while(TrilizaMarks[move-1]==’1′)

{

cout<>move;

}

@zahra : Thanx for the correction. I actually don’t have the needed workspace to reproduce that now, but thank you for pointing out I guess there may be some small bugs there, this program was mainly meant to be a demonstration of creating a simple game, so it may indeed have some minor(hope not major :P) problems.

Thanks for idea. I make this working about your idea. rc=direction

For rc=5 i try little different strategy. Sorry for greeks.

void selectmove(int mat[][rc]){

int ret=0;

int val[2*rc+2]; int isfoul[2*rc+2];

for(int i=0;i<rc;++i){

for(int j=0;j<rc;++j){

if(mat[i][j]==0)ret=1;

}/* Υπάρχει ελεύθερο τετράγωνο. */

}

/*ΠΛΗΡΟΦΟΡΙΕΣ: κρατάμε το άθροισμα κάθε τρίλιζας

και τον αριθμό κενών τετραγώνων που διαθέτει.

*/

if(ret==1){/* Αρχικοποίηση */

for(int i=0;i<(2*rc+2);++i){

val[i]=0; isfoul[i]=0;

}/* Συλλογή */

for(int i=0;i<rc;++i){

for(int j=0;j<rc;++j){

val[i]+=mat[j][i];

if(mat[j][i]!=0)isfoul[i]++;

val[rc+i]+=mat[i][j];

if(mat[i][j]!=0)isfoul[rc+i]++;

}

val[2*rc]+=mat[i][i];

if(mat[i][i]!=0)isfoul[2*rc]++;

val[2*rc+1]+=mat[(rc-1)-i][i];

if(mat[(rc-1)-i][i]!=0)isfoul[2*rc+1]++;

}/* αξιολόγηση – στρατηγική */

for(int i=0;i<(2*rc+2);++i){

/*cout<<"\n val["<<i<<"]="<<val[i];*/

if(val[i]==(rc-2))val[i]+=2;

if(val[i]==(rc-1))val[i]*=rc;

if(val[i]==(1-rc))val[i]*=(-2*rc);

if(val[i]==(2-rc))val[i]*=(2-rc);

if(val[i]==(3-rc))val[i]*=(-rc);

if(isfoul[i]==rc)val[i]=-rc;

if(isfoul[i]==(rc-1))val[i]-=1;

if(isfoul[i]==(rc-2))val[i]+=1;

/*cout<<"\n val["<<i<<"]="<<val[i];*/

}

/*Random κανονικοποίηση για αποφυγή ισοψηφίας.

Η mx κρατάει τον δείκτη της τρίλιζας μέγιστης αξιολόγησης.

Στην περίπτωση ισοψηφίας είναι η τελευταία που βρήκε.

Περιπτώσεις ισοψηφίας ή random παραβίασης της στρατηγικής

εμφανίζονται στις πρώτες κινήσεις, όπου οι θέσεις δεν έχουν

ακόμα ουσιαστική αξιολόγηση. Σε τρίλιζα μικρότερης διάστασης

αυτό εξαλείφεται.

*/

int mx=0;/* Μέγιστη τιμή λίστας */

for(int k=0;kmx)mx=val[k];

}

for(int k=0;k=mx){

val[k]*=(3+(rc*(rand()/(RAND_MAX+0.1))));

}

}

mx=0;

for(int k=0;k<(2*rc+2);++k){

/*cout<<"\n val["<<k<<"]="<=mx)mx=val[k];

}

/*ΕΚΤΕΛΕΣΗ ΚΙΝΗΣΗΣ

Εκτελείται random διαδικασία ώστε να αντισρέφεται η φορά

με την οποία γεμίζει η κάθε τρίλιζα.

ΠΡΟΣΟΧΗ: αν η λίστα φτάσει ως εδώ με όλα τα στοιχεία αρνητικά

θα παραμείνει z=-1 και θα προκύψει σφάλμα κατάτμησης.

Επίσης, αν σταλεί να γεμίσει τρίλιζα που δεν έχει κενά

τετράγωνα, δεν θα κάνει τίποτα και θα κάνει πάσα στον παίκτη.

Στο συγκεκριμμένο παιχνίδι αυτές οι περιπτώσεις διαχειρίζονται

στο προηγούμενο στάδιο αξιολόγηση – στρατηγική.

*/

int z=-1;

for(int i=0;i<(2*rc+2);++i){

if(val[i]==mx)z=i;

}

if(z<rc){/* έλεγχος στήλης */

int rnd=3+rc*(rand()/(RAND_MAX+0.1));

if(rnd<rc){

for(int i=0;i=0;–i){

if(mat[i][z]==0)mat[i][z]=-1; break;

}

}

}

if(z>=rc and z<(2*rc)){/* έλεγχος γραμμής */

int rnd=3+rc*(rand()/(RAND_MAX+0.1));

if(rnd<rc){

for(int i=0;i=0;–i){

if(mat[z-rc][i]==0)mat[z-rc][i]=-1; break;

}

}

}

if(z==(2*rc)){/* 1η διαγώνιος */

int rnd=3+rc*(rand()/(RAND_MAX+0.1));

if(rnd=0;–j){

if(mat[j][j]==0)mat[j][j]=-1;break;

}

}else{

for(int j=0;j<rc;++j){

if(mat[j][j]==0)mat[j][j]=-1;break;

}

}

}

if(z==(2*rc+1)){/* 2η διαγώνιος */

int rnd=3+rc*(rand()/(RAND_MAX+0.1));

if(rnd=0;–j){

if(mat[(rc-1)-j][j]==0)mat[(rc-1)-j][j]=-1;break;

}

}else{

for(int j=0;j<rc;++j){

if(mat[(rc-1)-j][j]==0)mat[(rc-1)-j][j]=-1;break;

}

}

}

}return;

}

Thank you Theodore for the interesting extension. I am sorry for deleting the greek comment, but it would really make no sense to the other readers. Feel free to write anything in english if you like, though

Hi, i’m doing a project for school on this exact thing, and i was completely lost on how to create the ai untill i stumbled across this website. Would it be ok if i used some of your algorithm in my project?

@Reece, this code is open source, so you can use it however you want. Just make sure that your school is ok with that.

hi,can any body explain to me how find the “3*x2 + x1 – ( 3*O2 + O1 )” ?

why “x2″ multiply to “3″…? and so?…..

@mehran : it’s just an implementation of a heuristic minimax algorithm. You can create your own as well. It’s just a way to measure performance.

if we would like to make pc an invincible (wins always) player, we should add some if statements inside checkforpitfall function or what else?

thx i am looking forward you to reply.

@Eric, you cannot make it win always because even if the computer plays the best moves every time, there is also the human opponent who, if plays best, they can force a draw.

Even if cpu plays first, there is no way cpu win or draw always?

Generally implementing tic tac toe with other techniques/algorithms referencing to artificial intelligence,

is it possible cpu win or draw always?

thx

can any one create a tic tac toe code of just ten lines? the smallest ever??????

what if i create a massive nested loop that goes through every possible move after say two moves

have already being made. Everytime it hits a win or lose condition it adds subtracts one point to the very first of the hypothosised moves. Therefore it will always evaluate the best next move.

@james51r, it can be done for tic-tac-toe but it cannot be extended to games like chess where bruteforcing only is not an option.

hello ! d code z really helpful but i need a small favour frm u sir…here player one is d computer and player two is d end user….can u gimme d code in which both d players are d end users ???

hey man i was just wondering if the meanings of you’re source is actually calculation because im not sure of the ai

Hey,Spyros in this code how did you figure out the algorithm given above..??..In a comment above, you said it’s a way to compare “performance”….here what does this performance mean..and why is it so….did you use any other algorithm to deduce this algorithm????/PLEASE HELP

@Mathew : Hello, the algorithm is heuristic by nature, meaning that it tries to find the best response by measuring performance that is tied to the application. It can be wrong in some cases, especially when the complexity rises, but for simple applications like tic tac toe, it works pretty well. The idea is that we are creating a way to evaluate the tic tac toe board in a given position, as we would in a chess game. For instance, if in a chess game a player is short of a bishop, this would remove points from him and add points to his opponent. It’s the same idea here. If a player ‘owns’ a diagonal, row or column with 2 marks, he gets more points than if he just had a single mark. This serves as a static evaluation of the position, which is rather strong for a simple tic tac toe game. Hope this explains it a bit better

it didn’t run at codeblock ,and where is the”stdafx.h” header file ar is not used in the program

hey spyros……..please explain in detail how u deduce that formula……….why it is like (3 *x2 +x1)-(3*o2-o1) but not like (2* x2+x1)-(2*o2-o1)

It could be 2 instead of 3, as you propose. This value is pretty much giving a weight on the situation. Think about it like soccer scores. A draw gives 1 point and a win gives 3 points. In the same manner, 2 marks are significantly better than 1 mark. Therefore, a 3 depicts a *closer to win* situation.

kk……..now i understand this completely.This formula is not optimal one there are various cases in which its fails………………like one of them is computer never win by using this formula

correct one i will write after designing efficient one………….

Pretty neat code and pretty good AI.But I found a way to beat it.Type 5,6,4.After you choose 5, the AI will choose 9.Then you choose 6 and the AI will choose 7 (I tried it several times and it always chooses 7) and then obviously you choose 4.There you go.

@TheRealNeo : I cannot try that at the computer i am now, but if that works,way to go Haven’t found a way to beat it before

i want to write a code for a tic tac toe game using a 5 by 5 matrix please help me

i wrote a tic tac toe game with my Ti-84+ graphing calculator. The language is very simple. i just kept track of the board on a list. It wouldnt be very hard to just copy and change the code. the computer just keeps track of your moves and it knows what to do in certain scenerios. now when the computer goes first against you, it randomly creates a winning scenerio and carries out that scenerio until you make a move that the computer didnt see. then it just creates a new scenerio. the board stored on the list just has different values for the x’s and o’s and empty spaces.