Programming Forums > Projects > Existing Project Development

Indigno · Jan 8th, 2006, 8:17 AM

I've been working on a tic tac toe game for a week or two now. Right now I've got a random number AI system set up for it. I also have it set so that it has a 2/3 chance of blocking a human attempt at getting three in a row. But I'm having problems setting it to try to get its own side three in a row. I know that I could set every single scenario into it, but that might take a while. Right now I have my board set up like:

s1|s2|s3
----------
s4|s5|s6
----------
s7|s8|s9

there is a label on each of the squares, then one of those variables is assigned to it. This is in visual basic. How do I set it to simultaneously look out for me trying to get three in a row but also try to get three in a row itself?

coldDeath · Jan 8th, 2006, 8:35 AM

This is no hep whatsoever, but nevermind :-) :

(Toggle Plain Text)

if (two player cells are in a row)
{
   block_a_cell();
}
else
{
  if(two player cells are in a row && there is a space to go in the next cell)
  {
     move_in_a_cell();
   }
   else if (one player cell is on its own && there are two spaces)
   {
        move_in_a_cell();
   }
   else if (there are three empty spaces)
   {
        move_in_a_cell();
   }
   else
   {
      move_in_a_random_cell();
   }
}

Obviously thats far from perfect, and its not completed or even in VB. And there are much better ways than that, but thats just my idea :-)

Jessehk · Jan 8th, 2006, 9:47 AM

Now, take this with a grain of salt, because I have never done any AI before. This was my solution in C++ (which was about 800 lines :o )

I had methods like makeMove, and checkWin, which would call other (private) methods that would return the appropriate row or colum. I did that by going through each row, column, and diagonal, and if there were exactly 2 spaces taken up by the opponant, I returned it. After my makeMove() function had the correct row/column/diagonal, I simply went through it, looking for the empty spot (which I then filled with my player).

So, following that idea, my AI makeMove() function looks like this:

(Toggle Plain Text)

bool CBoard::makeMove()
{
	//int chances = rand() % 2;
	bool moveMade = false;
	int *spot;
	

	
	if(!moveMade)
	{
		spot = checkOffence();
		if(spot != NULL)
		{
			//std::cout << "spot[0] = " << spot[0] << std::endl;
			//std::cout << "spot[1] = " << spot[1] << std::endl;
			Board::board[spot[0]][spot[1]] = player;
			//std::cout << "offensive move made" << std::endl;
			moveMade = true;
			delete [] spot;
		}
	}
	

	if(!moveMade)
	{
		spot = checkDefence();
		if(spot != NULL)
		{
			Board::board[spot[0]][spot[1]] = player;
			//std::cout << "defensive move" << std::endl;
			moveMade = true;
			delete [] spot;
		}
	}
	
	if(!moveMade)
	{
		makeRandomMove();
		//std::cout << "random move" << std::endl;
	}
	
	return true;
}

So, as you can (hopefully) see, first I look for an offensive move, then I look for a defensive move, and then I make a random move. The methods my makeMove() calls are all private.

The problem with my solution is that at the beginning of the game, the AI will often make a random move in a bad position, such as on a center-spot of a column on the right or left side.

Therefore, I'd like to add to my makeMove() function to first check to see if they can make a move in the center, or corner, and then make a random move.

Like I said, this could well be (and probably is) a bad solution. But it's always helpful to look at things from different angles.

tempest · Jan 8th, 2006, 12:37 PM

Quote:

Originally Posted by coldDeath

This is no hep whatsoever, but nevermind :-) :

(Toggle Plain Text)

if (two player cells are in a row)
{
   block_a_cell();
}
else
{
  if(two player cells are in a row && there is a space to go in the next cell)
  {
     move_in_a_cell();
   }
   else if (one player cell is on its own && there are two spaces)
   {
        move_in_a_cell();
   }
   else if (there are three empty spaces)
   {
        move_in_a_cell();
   }
   else
   {
      move_in_a_random_cell();
   }
}

Obviously thats far from perfect, and its not completed or even in VB. And there are much better ways than that, but thats just my idea :-)

ColdDeath, you might want to note that your first if expression tests for something that if's inside of the else statement test for also -- making it impossible for the 1st 2nd level if inside of that else to be called.

UnKnown X · Jan 9th, 2006, 7:27 AM

The way I did it was to use a function like so (pseudo-code):

(Toggle Plain Text)

bool WinLose(char NaughtCross) // pass 'O' or 'X' to the function
{
    // perform checks to see if player/bot is winning depending on variable sent to function
    if (!winning)
        return false;
    else
    {
        // block enemy or extend its own
        return true;
    }
}

Indigno · Jan 9th, 2006, 10:20 AM

Well, I don't really understand C++ enough to even try to convert it into VB. Though i don't know if it's a good idea to make the computer attempt to go for the offensive before the defensive.

UnKnown X · Jan 9th, 2006, 11:44 AM

Yes, that's the best way. If it can win, why block the opponent?

If you implemented something like the function above, you could simply call it twice, first 'O' as the argument, then the 'X' if the first call returns false.

Edit: about the strategy, it depends on how offensive you mean. If the bot can win on its move, it should. Otherwise, I think it should play a little bit more defensive.

Also, you could try to do the Mini-Max algorithm, but it's a bit advanced.

nnxion · Jan 9th, 2006, 1:03 PM

The above could be pseudo-code for all you care. Thinking about what to do first is essentially what AI is about.

ZenMasterJG · Jan 10th, 2006, 1:40 AM

A Minimax tree is the "classic" way to do tic-tac-toe AI. Check out:
http://ai-depot.com/LogicGames/MiniMax.html

ai-depot.com is pretty cool

Jan 8th, 2006, 8:17 AM	#1
Indigno Professional Programmer Join Date: Dec 2005 Location: Anywhere non-productive Posts: 267 Rep Power: 0	AI for tic tac toe I've been working on a tic tac toe game for a week or two now. Right now I've got a random number AI system set up for it. I also have it set so that it has a 2/3 chance of blocking a human attempt at getting three in a row. But I'm having problems setting it to try to get its own side three in a row. I know that I could set every single scenario into it, but that might take a while. Right now I have my board set up like: s1\|s2\|s3 ---------- s4\|s5\|s6 ---------- s7\|s8\|s9 there is a label on each of the squares, then one of those variables is assigned to it. This is in visual basic. How do I set it to simultaneously look out for me trying to get three in a row but also try to get three in a row itself?

Jan 8th, 2006, 8:35 AM	#2
coldDeath Expert Programmer Join Date: Aug 2005 Location: UK Posts: 862 Rep Power: 4	This is no hep whatsoever, but nevermind :-) : (Toggle Plain Text) if (two player cells are in a row) { block_a_cell(); } else { if(two player cells are in a row && there is a space to go in the next cell) { move_in_a_cell(); } else if (one player cell is on its own && there are two spaces) { move_in_a_cell(); } else if (there are three empty spaces) { move_in_a_cell(); } else { move_in_a_random_cell(); } } if (two player cells are in a row) { block_a_cell(); } else { if(two player cells are in a row && there is a space to go in the next cell) { move_in_a_cell(); } else if (one player cell is on its own && there are two spaces) { move_in_a_cell(); } else if (there are three empty spaces) { move_in_a_cell(); } else { move_in_a_random_cell(); } } Obviously thats far from perfect, and its not completed or even in VB. And there are much better ways than that, but thats just my idea :-) __________________ Programming Tutorials - Linux Installation Guide - Learn Python - Learn C++ Got Slack? Join us at #programmingforums @ irc.freenode.net! My software never has bugs. It just develops random features.

Jan 8th, 2006, 9:47 AM	#3
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 644 Rep Power: 4	Now, take this with a grain of salt, because I have never done any AI before. This was my solution in C++ (which was about 800 lines :o ) I had methods like makeMove, and checkWin, which would call other (private) methods that would return the appropriate row or colum. I did that by going through each row, column, and diagonal, and if there were exactly 2 spaces taken up by the opponant, I returned it. After my makeMove() function had the correct row/column/diagonal, I simply went through it, looking for the empty spot (which I then filled with my player). So, following that idea, my AI makeMove() function looks like this: (Toggle Plain Text) bool CBoard::makeMove() { //int chances = rand() % 2; bool moveMade = false; int spot; if(!moveMade) { spot = checkOffence(); if(spot != NULL) { //std::cout << "spot[0] = " << spot[0] << std::endl; //std::cout << "spot[1] = " << spot[1] << std::endl; Board::board[spot[0]][spot[1]] = player; //std::cout << "offensive move made" << std::endl; moveMade = true; delete [] spot; } } if(!moveMade) { spot = checkDefence(); if(spot != NULL) { Board::board[spot[0]][spot[1]] = player; //std::cout << "defensive move" << std::endl; moveMade = true; delete [] spot; } } if(!moveMade) { makeRandomMove(); //std::cout << "random move" << std::endl; } return true; } bool CBoard::makeMove() { //int chances = rand() % 2; bool moveMade = false; int spot; if(!moveMade) { spot = checkOffence(); if(spot != NULL) { //std::cout << "spot[0] = " << spot[0] << std::endl; //std::cout << "spot[1] = " << spot[1] << std::endl; Board::board[spot[0]][spot[1]] = player; //std::cout << "offensive move made" << std::endl; moveMade = true; delete [] spot; } } if(!moveMade) { spot = checkDefence(); if(spot != NULL) { Board::board[spot[0]][spot[1]] = player; //std::cout << "defensive move" << std::endl; moveMade = true; delete [] spot; } } if(!moveMade) { makeRandomMove(); //std::cout << "random move" << std::endl; } return true; } So, as you can (hopefully) see, first I look for an offensive move, then I look for a defensive move, and then I make a random move. The methods my makeMove() calls are all private. The problem with my solution is that at the beginning of the game, the AI will often make a random move in a bad position, such as on a center-spot of a column on the right or left side. Therefore, I'd like to add to my makeMove() function to first check to see if they can make a move in the center, or corner, and then make a random move. Like I said, this could well be (and probably is) a bad solution. But it's always helpful to look at things from different angles. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Jan 9th, 2006, 7:27 AM	#5
UnKnown X Hobbyist Programmer Join Date: Dec 2005 Location: Sandvika, Norway Posts: 114 Rep Power: 0	The way I did it was to use a function like so (pseudo-code): (Toggle Plain Text) bool WinLose(char NaughtCross) // pass 'O' or 'X' to the function { // perform checks to see if player/bot is winning depending on variable sent to function if (!winning) return false; else { // block enemy or extend its own return true; } } bool WinLose(char NaughtCross) // pass 'O' or 'X' to the function { // perform checks to see if player/bot is winning depending on variable sent to function if (!winning) return false; else { // block enemy or extend its own return true; } }

Jan 9th, 2006, 1:03 PM	#8
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	The above could be pseudo-code for all you care. Thinking about what to do first is essentially what AI is about. __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Jan 9th, 2006, 10:20 AM	#6
Indigno Professional Programmer Join Date: Dec 2005 Location: Anywhere non-productive Posts: 267 Rep Power: 0	Well, I don't really understand C++ enough to even try to convert it into VB. Though i don't know if it's a good idea to make the computer attempt to go for the offensive before the defensive.

Jan 9th, 2006, 11:44 AM	#7
UnKnown X Hobbyist Programmer Join Date: Dec 2005 Location: Sandvika, Norway Posts: 114 Rep Power: 0	Yes, that's the best way. If it can win, why block the opponent? If you implemented something like the function above, you could simply call it twice, first 'O' as the argument, then the 'X' if the first call returns false. Edit: about the strategy, it depends on how offensive you mean. If the bot can win on its move, it should. Otherwise, I think it should play a little bit more defensive. Also, you could try to do the Mini-Max algorithm, but it's a bit advanced.

Jan 10th, 2006, 1:40 AM	#9
ZenMasterJG Hobbyist Programmer Join Date: Nov 2004 Location: Boston, MA Posts: 148 Rep Power: 4	A Minimax tree is the "classic" way to do tic-tac-toe AI. Check out: http://ai-depot.com/LogicGames/MiniMax.html ai-depot.com is pretty cool

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Projects > Existing Project Development

AI for tic tac toe