need help with simple C++ TicTacToe game with AI

[flupke1]

Hi there,

I'm a Dutch student (and a complete newbie to programming) working on an assignment for school. The assignment is to program a basic tic tac toe game (using visual C++ 6.0 or 2003 .NET) for one player against the computer. I have to use basic programming, only loops and basic functions etc. I don't need to have a great looking GUI. I only have to get the game working.

I'm stuck on two problems:

1: Got a bug in the main function when the program is running and it's a tie.

2: I can't seem to find the solution to build a AI computer player.

Got the game working for 2 players so far, but can anybody please help me with the bug (when it's a tie) or to get the computer player working???

I would be very gratefull!

tnx Flupke

p.s. here's my code for so far:

#include <iostream>
using namespace std;

char board[9] = { '1', '2', '3', '4', '5', '6', '7', '8', '9'};
void drawBoard();

bool checkWinner();
void movePlayer(bool);
void moveComputer(bool);
bool possibleMove(int);

void main()
    {
    bool player = false;		/* true = X , false = O */
	int i= 0;

	drawBoard();

	while(!checkWinner())
		if ( i==0 || i==2  || i==4 || i==6 || i==8 )
		{
			i++;
			{
			if(player == true)
			    player = false;
			else
		        player = true;
		        movePlayer(player);
			}
		}
	    else if ( i==1 || i == 3  || i==5 || i==7 )
		{
			i++;
			{
			if(player == true)
			    player = false;
			else
		        player = true;
		        moveComputer(player);
			}
		}
		else
		cout << " It's a TIE !!! " << endl;
		cin.get();

    
    if(player == true)
		cout << "Player one WINS !!!" << endl;
	else
		cout << "The computer WINS !!!" << endl;
    }
    

void drawBoard()
    {
   		cout << "\n " << board[0] << " | " << board[1] << " | " << board[2] << endl
         << " ---------" << endl
         << " " << board[3] << " | " << board[4] << " | " << board[5] << endl
         << " ---------" << endl
         << " " << board[6] << " | " << board[7] << " | " << board[8] << endl;
    }

bool checkWinner()
    {
			if(board[0] == board[1] && board[2] == board[0] )
	        	return true;
		    
			else if(board[3] == board[4] && board[5] == board[3])
	        	return true;

			else if(board[6] == board[7] && board[8] == board[6])
	        	return true;

			else if(board[0] == board[3] && board[6] == board[0])
	        	return true;

			else if(board[1] == board[4] && board[7] == board[1])
	        	return true;

			else if(board[2] == board[5] && board[8] == board[2])
	        	return true;

			else if(board[0] == board[4] && board[8] == board[0])
	        	return true;

			else if(board[2] == board[4] && board[6] == board[2])
	        	return true;
			else
				return false;
    }

void movePlayer(bool whichPlayer)
	{
        int place;
        cout << "\n Player one, make your move: ";
        cin >> place;
        if(possibleMove(place))
            {
				if(whichPlayer == true)
				board[place-1] = 'X';
				else
				board[place-1] = 'O';
            }
        else
            movePlayer(whichPlayer);
            drawBoard();
    }
   
void moveComputer(bool whichPlayer)
	{
        int place;
        cout << "\n Computer, make your move: ";
        cin >> place;
        if(possibleMove(place))
            {
				if(whichPlayer == true)
				board[place-1] = 'X';
				else
				board[place-1] = 'O';
            }
        else
            moveComputer(whichPlayer);
            drawBoard();
    }

bool possibleMove(int place)
    {
		if(board[place-1] == 'X' || board[place-1] == 'O')
        return false;
        else
        return true;
    }

[John]

I made a great tutorial on on tic-tac-toe [but in Java] the idea is pretty much the same.

I haven't looked at your code yet, but I will as I am very interested. However, it will take me a while to understand your code, and in the meantime you could make some headway. So...

To figure out who's turn it is, I have a variable increment each time a move is made. The variable [say i] starts off at 0 and if

if ( i % 2 = 0 )
// X goes
else
// O goes

to check if it is a tie, just check if i == 9, if it is 9 than there are no more moves that can be made -- the game is a tie and the game is over. Display a message and your done.

As for the AI, you just need a whole bunch of else if's [you can look at my code in the Java tutorial section for how I implemented it AI, I'm sure you can understand what is going on -- the syntax is very similar]

[John]

Ok, I've taken a look at your code and played with it for a little bit. Here is what I've come up with for the AI.

The AI code will be placed in the moveComputer() method/function. What you want to do is check every possibility. When the computer checks, it wants to check these in order: Offensive moves, Defensive moves, Random move. An example of an offensive move (assuming the computer is O) would be

if(board[0] == 'O' && board[1] == 'O' && board[0] != " ") {
board[2] == 'O';
}

It checks to see if there are two O's in places 0 and 1, if there are, the computer will place an O in place 2 and win the game. There are 24 offensive "moves" all which are shown in my other tutorial. A defensive move would be similar:

else if(board[0] == 'X' && board[1] == 'X' && board[0] != " ") {
board[2] == 'O';
}

The computer would obviously want to win the game before he blocked you from winning the game so all offensive moves need to be placed before the defensive moves or it wouldn't make much sense [unless you want easy/hard modes]

And in the event there are no win possibilities [2 X's or O's in a row] for either player, the computer would then pick a random place to go [I'm sure there is a function in C++ to compute a random number between 0 and 8 inclusive] and of course you would have to make sure that the random number generated == ' ' and not 'X' or 'O'

else {
//random placement
}
//drawboard
//x's turn

As for the tie, I don't see any bug?

[flupke1]

tnx for the tips.

i hope i'll get it done.

flupke

[flupke1]

Hi guys,

here is an (late) update of my tic tac toe project. have been kinda busy with work and my finals at school, so i haven't done much the past weeks.

i did implement the ai as in the example you (sidewinder) gave me, thanks again for the tip, it works great if you ask me.
but my teacher at school doesn't agree with me that it works fine.

he said i should look at a minimax (minmax) function. so i have to start all over with the ai thing

I've been searching on the net for a lot of hours, but i can't seem to find any usefull tips or examples. The only useful thing i found was on wiki, with some math-formulas that go way beyond my brain-capacity.

does anybody know how a minimax function works?

flip

p.s. 1 the reason my teacher said it wasn't good enough is that there were way to much lines of code, which will (according to him) create errors easily.

p.s. 2 the bug when it's a tie is still a bug. but it only occurs once i a while and it's certainly not the biggest problem at the moment.

[CygnetGames]

Minimax: yes, I know all about this. I've just recently completed a university course about AI, and minimax featured heavily in it. Minimax is the algorithm that traditional AIs used to use. It is the algorithm that all the chess computers, like Deep Blue, use. (Although Deep Blue uses a highly optimised version of minimax, with lots of additions to make it more efficient.)

Basically, there are two parts to minimax:
1) Representing the game as a tree.
2) Searching the tree to find the best strategy for playing the game.

1) Representing the game as a tree
(This is hard to explain without being able to draw things on paper, but i'll try)
The game consists of 2 players who make moves.
Each time a player makes a move, he has a number of different choices of which move to make.
Nodes of the tree are times when a player makes a move.
Arcs of the tree are choices of moves that the player can make.

So the root of the tree will represent the first move made by the first player. Lets say that the human player always goes first - just switch the words around if the computer goes first.
When the human makes his first move, he can choose to put a 'O' in any of the 9 squares. So in the tree, there will be 9 arcs coming from the root node.
Each arc corresponds to the human putting his 'O' in a different square on the board.

Now, the computer plays.
At the end of each arc coming from the root node, there is a node where the computer takes its turn.
There are only 8 possible moves the computer can take (as one square has been taken by the human).
So from each node on the second level of the tree, there are 8 arcs corresponding to each of the 8 moves that the computer can make.

Then on the third level of the tree, there are 7 arcs coming from each node, corresponding to the 7 different moves that the human can make on his second move.

If we continue this process, we get a (huge) tree showing all the possible ways that the game can go. If you follow one single path from the root of the tree down to a leaf, this represents a series of moves human->computer->human->computer->... which is one game that could be played. The tree contains all possible games that could ever be played.
The root of the tree corresponds to the start of the game, and the leaves of the tree correspond to ways the game could end.
So the task of the AI program is to find a path through this tree that starts at the root and ends at a leaf where the computer has won.
This is the task: At every node in the tree where it is the computer's move, the AI program has to be able to say which of the arcs to go down (i.e. which move to make in the game), so that it is guaranteed to end up at a leaf where the computer has won.

2) Searching the tree
To do this searching, we need to put some numbers into the tree.
We have a function called a payoff function that tells us how good each node is in the tree. Since nodes in the tree correspond to states that the game can be in when someone makes a move, the payoff function also tells us how good each possible state is that the board can be in.
We start at the leaves of the tree.
At a leaf, we can say who has won: human or computer.
If the computer has won, the payoff function for that leaf is 10 points.
If the human has won, the payoff function for that leaf is -10 points.
If it was a draw, the payoff function for that leaf is 0 points.
(The numbers are arbitary for tic-tac-toe. They mean more in other games. All that matters here is that winning has a higher payoff than drawing, which has a higher payoff than losing)

Now that each leaf has a payoff value, we can start to move these payoff values up the tree, to work out the payoff value of every node in the tree.
Now you see what the algorithm is called minimax.
Imagine a leaf node. We know its payoff value (it is either 10 or 0).
Someone made a move to get to this leaf node (either the human or the computer).
Let's say the human made the move that got to this leaf node.
Now look at the parent of the leaf node. It is a node where the human made a move, and it has lots of leaf nodes coming off it. (Let's say it has 3 leaf nodes coming off it.)
We know the payoffs at each of these leaf nodes.
We know that the human is going to take this move that is best for him (we assume the human player is perfect and makes no mistakes).
Because the human will choose the move that is best for him, and our payoff function is showing which moves are best for us (the computer), the human will choose the move with the lowest payoff.
In contrast, when we come to a node where the computer makes a move, we will choose the move with the highest payoff.
For this reason, some people call the human player min and the computer player max. This is one reason for the name minimax.

So to work out the payoff of the node where the human made a move, we look at the payoff values of all of its children and pick the lowest value.
To work out the payoff of a node where the computer makes a move, we look at all of its children and pick the highest value.
Using this method of picking the highest value for our moves and the lowest value for the human's moves, we can start at the leaves and work out the payoff values for each node on the second-to-last level of the tree.
When we know all the payoff values on the second-to-last level, we can use these to work out all the payoffs on the third-to-last level.
Repeating this process, we can climb all the way up the tree until we have reached the root.

Once we reach the root node, we will finally know if the computer can ever win against a perfect human opponent. Incidentally, in tic-tac-toe, you should end up with a payoff of 0 for the root. This means that two perfect players playing against each other will always draw.

Now, when you have this tree built, and you have propagated all the leaf payoff values up the tree, can your AI program start to play the game.

As the game is played, the program keeps track of where it is in the tree. When the human makes a move, the program moves it's pointer down the branch corresponding to the move that the human made.
When the computer has to make a move, it looks at the node it is currently at in the tree.
The possible moves it can make are branches coming from this node.
The nodes at the end of these brances all have their payoff values calculated.
So the choice is simple: choose the move with the highest payoff value.
Remember that the payoff value shows how good the move is for the computer, so obviously we choose the move with the highest value.

__________________________________________________ ___

And there you have it: minimax. I really hope that made some sense.

I tried to google for some pages explaining it with pictures, and I found this. It might be some use to you, and it has some code.
The wikipedia page has a lot of scary maths on, bit it has one diagram of a tree about halfway down the page at the right, which might be useful.

So now you have two choices.
1) Implement the minimax algorithm in all its glory.
2) Run the algorithm yourself on paper to build the tree and propagate the values, then build your algorithm around these values.

Although it seems like there are a mind-blowing number of nodes in the tree for tic-tac-toe, a lot of them are symmetrical.
An initial move in the top left corner is the same as an initial move in the top right corner, for example.
By thinking about these symmetries, it is very possible to draw out the whole tree on a piece of paper. (Make sure it's a big piece though - I would get an A2 size piece.)

Ok, so good luck with it.
If you have any questions about minimax or AI in general, either post or PM me. If you post something and I don't reply to it, just PM me to say that you've posted something and i'll check it out.

I would completely understand if you decided not to implement minimax - it's not a trivial job to code, but it's not terrible either.
If you've had any experience with graphs then it shouldn't be too bad. The hardest part is getting your head around how to code a graph and how to travel up and down it.
Propagating the values is really simple - to do it on paper is really easy.
And choosing which move to take is even simpler. On paper it's blatantly obvious, in a computer it's nearly obvious.

Ok, enough typing already! I'm going to eat pizza. Good luck with it.

[Gibsy]

Thnx for this excellent explanation Cygnet. Hope you enjoyed your pizza. I searched the web for minimax but i only found pseudo-code for it. Do you know where I can find code of a working game, using minimax? I allready tried to program it myself, but I keep on having problems with building up the tree and how to 'travel' through it. As you said: on paper it's blatantly obvious...

My goal is to build the game Mancala in ActionScript/Flash, but any game in any language that applies minimax will do as an example for me.

Thanks!
Gibsy

BTW: I hope ActionScript allows recursive functions since I need that here...

[CygnetGames]

The pizza was good, thanks

Actionscript does indeed support recursive functions. I found a short article about it.

I managed to find a tutorial with code about minimax (you might want to ignore that parts about Alpha-Beta and other optimisations), and a full tic-tac-toe game that uses minimax, but they are both written in C. They should help you to understand how to use trees though.

Mancala is a good game to make. I have a wooden version of it, and minimax seems an appropriate way to solve the game. Complicated games like chess struggle with minimax, and you need to use loads of optimisations to make it good enough to beat humans. But Mancala seems to be just simple enough that minimax would work and just complicated enough that it's worth implementing minimax to solve it.

Sorry I couldn't find you any actionscript code, but the C examples should at least point you in the right direction. It's much more rewarding to write your own code anyway.
If you have any questions about trees (or indeed AI), post them here and i'll see what I can do to help.
The most important thing about trees is to know what information you are storing at each node, and how to get from a node to it's children (you may also need to get from a node to it's parent). Once you know these things inside out, the algorithms involving the tree should be easier to work out.

Also, if you get your game finished and want to publish it, my website is always looking for new games (see link in my signature).

[flupke1]

First of all, thanks a lot for all the info about minimax. It seriously does make sense to me, until I came to the point of implementing it in c++...

My father always told me the dutch expression: "Je bent niet zo dom als dat je er uit ziet" which means something like, You're not really stupid, you only look stupid. But I really think I'm stupid, especially when it comes to programming. I really hate this, because I went to this school because I always wanted to learn programming languages so I could make my own progs, games etc etc. But at the moment I don't think this will ever happen... :'(

I've already got my grade at school, but with an onther function than minimax. I told my teacher that minimax was too Pro for me. The course was basic programming, but minimax goes a lot further. Altough I've got my grade, I really want to know how I can realise the minimax implementation in my game i've posted earlier.

So my teacher was right after all. In the beginning of the semester he said that I was too stupid to become a good programmer. He said that I would never manage to see the simple logic in programming languages. So I will never be a lucky man and become a good programmer. :'(

Allright, enough with this crap, I have a last (stupid) question
I've looked at the minimax algorithm in the c# file of the 'full tic-tac-toe game', it looks easier than I thought would be.

Untill I tried to translate it to C++... I'll skip the part of trying to translate a piece of code from c# to c++, because that was about 4 hours an the only thing I got was more and more errors....

I've attached the c# code file at the end of the post. I hope that anyone can help me translating a piece of code like this to C++???

Again, MANY THANKS, because without your help I probably wouldn't got a grade after all.

Flupke


// returns best move for the current computer player
int MiniMax(char _board[9], player _player) {
int best_val = -INFINITY, index = 0;
std::list<int> move_list;
char best_moves[9] = {0};
generate_moves(_board, move_list);
while(!move_list.empty()) {
_board[move_list.front()] = _player.symbol;
cSymbol = _player.symbol;
int val = MinMove(_board, _player);
if(val > best_val) {
best_val = val;
index = 0;
best_moves[index] = move_list.front() + 1;
} else if(val == best_val) {
best_moves[++index] = move_list.front() + 1;
}
_board[move_list.front()] = 0;
move_list.pop_front();
}
if(index > 0) {
index = rand() % index;
}
return best_moves[index];
}

// finds best move for 'min player'
int MinMove(char _board[9], player _player) {
int pos_value = evaluate_position(_board, _player);
if(pos_value != -1) {
return pos_value;
}
int best_val = +INFINITY;
std::list<int> move_list;
generate_moves(_board, move_list);
while(!move_list.empty()) {
_player.symbol == 'X' ? cSymbol = 'O' : cSymbol = 'X';
_board[move_list.front()] = cSymbol;
int val = MaxMove(_board, _player);
if(val < best_val) {
best_val = val;
}
_board[move_list.front()] = 0;
move_list.pop_front();
}
return best_val;
}

// finds best move for 'max player'
int MaxMove(char _board[9], player _player) {
int pos_value = evaluate_position(_board, _player);
if(pos_value != -1) {
return pos_value;
}
int best_val = -INFINITY;
std::list<int> move_list;
generate_moves(_board, move_list);
while(!move_list.empty()) {
_player.symbol == 'X' ? cSymbol = 'X' : cSymbol = 'O';
_board[move_list.front()] = cSymbol;
int val = MinMove(_board, _player);
if(val > best_val) {
best_val = val;
}
_board[move_list.front()] = 0;
move_list.pop_front();
}
return best_val;
}

[saurav]

Does the following help a bit?
In any case, can anyone help me make it shorter?
Can we impart artificial intelligence to player 2?

#include<iostream>
using namespace std;
char board[9] ={'1','2','3','4','5','6','7','8','9'};

void drawboard()
{cout << "\n " << board[0] << " | " << board[1] << " | " << board[2] << endl;
 cout<< " ---------" << endl;
 cout<< board[3] << " | " << board[4] << " | " << board[5] << endl;
cout<< " ---------" << endl;
cout<< board[6] << " | " << board[7] << " | " << board[8] << endl;}

int winning(char f[])
{
if(board[0] == board[1] && board[2] == board[0] )
	        	return 1;
		    
			else if(board[3] == board[4] && board[5] == board[3])
	        	return 1;

			else if(board[6] == board[7] && board[8] == board[6])
	        	return 1;

			else if(board[0] == board[3] && board[6] == board[0])
	        	return 1;

			else if(board[1] == board[4] && board[7] == board[1])
	        	return 1;

			else if(board[2] == board[5] && board[8] == board[2])
	        	return 1;

			else if(board[0] == board[4] && board[8] == board[0])
	        	return 1;

			else if(board[2] == board[4] && board[6] == board[2])
	        	return 1;
			else
				return 0;
}



int main()
{
char c[2] ={'x','o'};
int move;
int player=2;
for(int i=0;i<=9;i++){
if(i<9&&winning(board)==0)
{
drawboard();
if(player ==1) player =2;
else player =1;
cout<<"player"<<player<<" please move"<<endl;
cin>>move;
board[move-1]=c[player-1];
{if(winning(board) == 1)
{cout<<"player"<<player<<" wins."<<endl;
 return 0;
}}}

else if(i==9&&winning(board)==0)
cout<<"Tie"<<endl;

else
cin.get();
}
}