Jump to content
  • Advertisement
Sign in to follow this  
NUCLEAR RABBIT

Tic Tac Toe Help!

This topic is 4453 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I just finished creating my tic tac toe game (C++), and im now trying to create AI, so that the comp is more of a challenge. The problem is, i've never worked with AI before, so i dont really have a good idea of how to do this kind of thing. The solution i thought of was this
if(gBoard[0] == 'O' && gBoard[1] == 'O' && gBoard[2] != 'X' && gBoard[2] != 'O') {
			gBoard[2] = 'O';
			done = true;
		}
the problem is, id have to do this for every poissible move in tic tac toe!!! Please, can somebody help me! The Game Source(with 1 ex. of the AI i thought of):

// Brandon : 7/26/06 - 7/26/06
// Tic Tac Toe Clone


#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

void WelcomeScreen(); // welcomes the player
void GetPmove(vector<char>& gBoard); // gets player move and check if its valid
void Drawboard(vector<char>& gBoard); // draws out the tic tac toe board
void GetCmove(vector<char>& gBoard); // gets computers move and checks if its valid
void CheckWin(vector<char>& gBoard, bool& RDone); // check if player or comp wins
void wait(); // waites for the user to press enter before exiting the game

int main()
{
	bool done = false;
	srand(time(0));

	vector<char> Board;
	Board.push_back('0');
	Board.push_back('1');
	Board.push_back('2');
	Board.push_back('3');
	Board.push_back('4');
	Board.push_back('5');
	Board.push_back('6');
	Board.push_back('7');
	Board.push_back('8');

	WelcomeScreen();

	while(!done) {
		Drawboard(Board);
		GetPmove(Board);
		CheckWin(Board, done);
		GetCmove(Board);
		Drawboard(Board);
		CheckWin(Board, done);
	}

	return 0;
}

void GetPmove(vector<char>& gBoard)
{
	int move = 0;
	bool done = false;

	while(!done) {
		cout << "\n\t\t\t\tMove: ";
		cin >> move;

		if(gBoard[move] == 'X') {
			cout << "\n\t\t\t\tYou've already moved there.\n";
			done = false;
		}
		else if(gBoard[move] == 'O') {
			cout << "\n\t\t\t\tYour Opponent has already Moved there.\n";
			done = false;
		}
		else {
			gBoard[move] = 'X';
			done = true;
		}
	}
}

void GetCmove(vector<char>& gBoard)
{
	int CMove = 0;
	bool done = false;

	while(!done) {
		CMove = rand() % 8;

		if(gBoard[0] == 'O' && gBoard[1] == 'O' && gBoard[2] != 'X' && gBoard[2] != 'O') {
			gBoard[2] = 'O';
			done = true;
		}
		else if(gBoard[0] == 'O' && gBoard[2] == 'O' && gBoard[1] != 'X' && gBoard[1] != 'O') {
			gBoard[1] = 'O';
			done = true;
		}
		else if(gBoard[1] == 'O' && gBoard[2] == 'O' && gBoard[0] != 'X' && gBoard[0] != 'O') {
			gBoard[0] = 'O';
			done = true;
		}

		if(gBoard[CMove] == 'X' || gBoard[CMove] == 'O')
			done = false;
		else {
			gBoard[CMove] = 'O';
			done = true;
		}
	}
}

void Drawboard(vector<char>& gBoard)
{
	system("cls");
	
	cout << "\n\n\n\n\n\t\t\tThe Game Board! Good Luck!\n\n";
	cout << "\t\t\t\t" << gBoard[0] << " | " << gBoard[1] << " | " << gBoard[2] << endl;
	cout << "\t\t\t\t" << "=========" << endl;
	cout << "\t\t\t\t" << gBoard[3] << " | " << gBoard[4] << " | " << gBoard[5] << endl;
	cout << "\t\t\t\t" << "=========" << endl;
	cout << "\t\t\t\t" << gBoard[6] << " | " << gBoard[7] << " | " << gBoard[8] << endl;
}

void CheckWin(vector<char>& gBoard, bool& RDone)
{
	if(gBoard[0] == 'X' && gBoard[1] == 'X' && gBoard[2] == 'X' ||
	   gBoard[0] == 'X' && gBoard[3] == 'X' && gBoard[6] == 'X' ||
	   gBoard[0] == 'X' && gBoard[4] == 'X' && gBoard[8] == 'X' ||
	   gBoard[1] == 'X' && gBoard[4] == 'X' && gBoard[7] == 'X' ||
	   gBoard[2] == 'X' && gBoard[5] == 'X' && gBoard[8] == 'X' ||
	   gBoard[2] == 'X' && gBoard[4] == 'X' && gBoard[6] == 'X' ||
	   gBoard[3] == 'X' && gBoard[4] == 'X' && gBoard[5] == 'X' ||
	   gBoard[6] == 'X' && gBoard[7] == 'X' && gBoard[8] == 'X') {
	   cout << "\n\t\t\t      OMG! YOU WON!\n\n";
	   RDone = true;
	   wait();
	}

	if(gBoard[0] == 'O' && gBoard[1] == 'O' && gBoard[2] == 'O' ||
	   gBoard[0] == 'O' && gBoard[3] == 'O' && gBoard[6] == 'O' ||
	   gBoard[0] == 'O' && gBoard[4] == 'O' && gBoard[8] == 'O' ||
	   gBoard[1] == 'O' && gBoard[4] == 'O' && gBoard[7] == 'O' ||
	   gBoard[2] == 'O' && gBoard[5] == 'O' && gBoard[8] == 'O' ||
	   gBoard[2] == 'O' && gBoard[4] == 'O' && gBoard[6] == 'O' ||
	   gBoard[3] == 'O' && gBoard[4] == 'O' && gBoard[5] == 'O' ||
	   gBoard[6] == 'O' && gBoard[7] == 'O' && gBoard[8] == 'O') {
	   cout << "\n\t\t\t      ROFL! YOU LOST, DUMBASS!\n\n";
	   RDone = true;
	   wait();
	}
}

void WelcomeScreen()
{
	cout << "\n\n\t\t\t  Welcome to Tic Tac Toe!\n"
		 << "\t\t\tProgrammed by: Brandon Wall\n\n"
		 << "\t\t\t\t X | X | O \n"
		 << "\t\t\t\t===========\n"
		 << "\t\t\t\t X | X | O \n"
		 << "\t\t\t\t===========\n"
		 << "\t\t\t\t O |   | O \n\n"
		 << "\t\t\t    Press Enter to Play.";
	cin.get();
}

void wait()
{
	cout << "\n\t\t           Press Enter to Exit.";
	cin.get();
}

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
I havent done this kinda programming either,
but off the top of my head, I would think that you could simplify gameboard checking by:
rather than write a check for each row on the board,
you could write a single rowcheck/colcheck function, that takes 3 pointers to board positions
then make a little table of rows, cols for it to check


function linecheck(int a, int b, int c){
if(gBoard[a] == 'O' && gBoard == 'O' && gBoard[c] != 'X' && gBoard[c] != 'O') {
gBoard[c] = 'O';
done = true;
}
}

checktable = {
{0,1,2},
{0,2,1},
{1,2,0},
{3,4,5},
{3,5,4},
{4,5,3},
etc...
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
P.S.

the traditional way of doing tictac is basically to use a tree algorithm called... minimax to basically chart out every possible future gameboard and every possible future move then do the one that eventually forces the player to lose.
personally... i think thats not so much fun, and a more 'greedy algorithm'(shortsighted) approach might be interesting (thats how a human plays, after all) more realistic and fun...

they way you're doing it now...
basically the robot puts his piece on the first row that he is forced to block
what about strategy before that point?
how about... you check all rows/cols, and assigne a point value to possible moves?
adding a piece to a row/col that contains 2 enemies very high
contains just 1 enemy, medium
empty, low
then for each empty slot on the board, check the rows/cols that go thru it and add up the points to assigne that move a value
then pick the move that gives the highest?

Share this post


Link to post
Share on other sites
To go about setting up AI for something like Tic-Tac-Toe think about what a real person would do. First they would see if they can win on this move, if they can they make that move. Then they see if the opponent can win on their next move, if so they block that. If nothing else they take the best square they can.

To accomplish this what I did was I set up a function to check the board for a winner. It took a reference to a vector(or array in your case) of boxes that made up the board and checked it against every single winning combination (don't worry there are only 8) and returned a char: 'H' for human win, 'C' for computer win, 'T' for tie, or 'N' for nobody.

The winner function looked a little like this.


char winner(int &board[9])
{
//Every combination of winning moves, snipped because I'm lazy
int winningmoves[8][3]= {{0,1,2},{3,4,5}...{0,4,8},{2,4,6}};

//Go through all the winning move combinations
//Check to see if all 3 boxes of the board are the same
//and that they aren't empty
//If they are somebody has won
//Check to see who it is and return it

for(int i=0;i<8;i++)
{
if((board[winningmoves[0]]==board[winningmoves[1]) &&
(board[winningmoves[1]]==board[winningmoves[2]]) &&
(board[winningmoves[0] != EMPTY))
{
if(board[winningmoves[0]]=='C')
return 'C';
else { return 'H'}
}
//Check to see if the whole board is occupied, if it is it returns Tie as
//default, if any boxes are empty it returns Nobody
for(int i=0;i<9;i++)
{ if(board==EMPTY)
return 'N';
}

return 'T'
}



Ok, now to the actual AI part, remember are 3 step plan for AI?
1. See if we can win
2. See if we can block opponent from winning
3. Take best move available

First to see if we can win we loop through every box in the grid and we occupy it a Computer piece. Then we check to see if there is a winner. If we won with that move that's the move we take.


for(int i=0;i<9;i++)
{
if(board==EMPTY)
{
board==COMPUTER;
if(winner(board)=='C')
{ return i;
}
else {board==EMPTY;}
}
}



It's that easy! If there hasn't been move returned yet we go through all the boxes again this time placing a human piece in there and seeing if the human wins, if so we move there to block it.


for(int i=0;i<9;i++)
{
if(board==EMPTY)
{
board=HUMAN;
if(winner(board)=='H')
{
board=EMPTY;
return i;
}
else{
board=EMPTY;
}
}
}



It's pretty much the same thing as last time only we change which piece we put in each time. Next if the computer can't win or block a move we just pick the best available move, you could, if you wanted to here put in more in depth AI to try and "trap" the opponent by getting in one of those situations where you can win two different ways but for the sake of simplicity I'm going to just pick the best move available.

Now how do you pick the best move? Simple, you make an array of the best moves and run through them. If that box is empty you take it. If not you move on.


//Best moves in order are: Center, Corners, Middle boxes?(don't know what to //call them).
int bestmoves[9]={4,0,2,6,8,1,3,5,7};

for(int i=0;i<9;i++)
{
if(board[bestmoves]==EMPTY)
{
return bestmoves;
}
}



Hope that helps! Of course, I just typed this all up now so I'm not guaranteing(sp?) that the code is perfect but the idea is still there. You'll have to modify the code for your program no doubt to change how you mark boxes empty and whatnot, but whatever.

Share this post


Link to post
Share on other sites
What wkiffer just described is pretty much minimax.

Quote:
you could, if you wanted to here put in more in depth AI to try and "trap" the opponent by getting in one of those situations where you can win two different ways but for the sake of simplicity I'm going to just pick the best move available.

It would be easier to "trap" the opponent, as you put it, since the AI doesn't know anything about how many moves away from the root we are. If we search 3 moves ahead and there happens to be a win on the third move, the AI will return that move, regardless of whether or not we can win on this turn. If we do take the move number into account, you can force the AI to pick the "immediate win" move.

Here is a simple Tic-Tac-Toe engine I wrote about 10 months ago or so (maybe it will help, I don't know):
#ifndef _TTT_H_
#define _TTT_H_

enum Player{
O=1, X=2, empty=4
};

enum{
PLAYING=1, C_WIN=2, H_WIN=4, DRAW=8
};

static const int lines[24]={
0,1,2, 3,4,5, 6,7,8, 0,3,6,
1,4,7, 2,5,8, 0,4,8, 2,4,6
};

struct Board{
Player board[9];

Board(){
for(int i=0;i&lt;9;++i)
board=empty;
}

bool check_for_win(Player p){
for(int i=1,d=0;i&lt;=24;++i){
if(board[lines[i-1]]&p){
if(!(++d%3))
return true;
} else d=0;
if(!(i%3))
d=0;
} return false;
}

int state(){
if(check_for_win(X))
return C_WIN;
if(check_for_win(O))
return H_WIN;
for(int i=0;i&lt;9;++i)
if(board&#8709;)
return PLAYING;
return DRAW;
}

int think(int depth,Player p){
int best=-100,alpha=-100,beta=+100,eval=-100,m;

for(int i=0;i&lt;9;++i){
if(board&#8709;){
board=p;
eval=-alphabeta(-beta,-alpha,depth-1,p&O?X:O);
board=empty;
if(alpha&lt;eval){
alpha=eval;
m=i;
}
}
}

return m;
}

int alphabeta(int alpha,int beta,int depth,Player p){
switch(state()){
case C_WIN:
return p&O?-100:+100;
case H_WIN:
return p&O?+100:-100;
case DRAW:
return 0;
}

if(depth&lt;=0)
return 0;

int best=-100,eval=-100;

for(int i=0;i&lt;9;++i){
if(board&#8709;){
board=p;
eval=-alphabeta(-beta,-alpha,depth-1,p&O?X:O);
board=empty;
if(alpha&lt;eval){
alpha=eval;
if(alpha&gt;=beta)
break;
}
}
}

return alpha;
}
};

#endif



[edit]: Ooops! That is not a good example, since it uses a variation of the minimax algorithm called AlphaBeta. Here is another example that actually uses minimax (it also makes use of bitboards, so just ask if there is something needed explaining):

ttt.h
#ifndef _TTT_H_
#define _TTT_H_

#include <iostream>
using namespace std;

#define O 0
#define X 1

#define HWIN 1
#define CWIN 2
#define DRAW 4
#define PLAYING 8

struct Board{
short m_bits[2];
unsigned move_number;

Board():move_number(0){clear_board();}
void clear_board(){m_bits[O]=m_bits[X]=0;}

void place(int s,int c){
m_bits[c]|=1<<s;
++move_number;
}

void remove(int s,int c){
m_bits[c]^=1<<s;
--move_number;
}

int state();
};

ostream& operator<<(ostream &o,Board const &b);

#endif


ttt.cpp
#include "ttt.h"

int Board::state(){
static const short wins[]={
0x007,0x038,0x1C0,0x049,
0x092,0x124,0x111,0x054
};

for(int i=0;i<8;++i){
if((m_bits[O]&wins) == wins)
return HWIN;
if((m_bits[X]&wins) == wins)
return CWIN;
}

if((m_bits[O]|m_bits[X]) == 0x1FF)
return DRAW;
return PLAYING;
}

ostream& operator<<(ostream &o,Board const &b){
for(int i=0;i<9;++i){
if(b.m_bits[X] & 1<<i)
o<<'x';
else if(b.m_bits[O] & 1<<i)
o<<'o';
else o<<'-';

if((i+1)%3==0)
o<<"\n";
}

return o;
}


search.h
#ifndef _SEARCH_H_
#define _SEARCH_H_

#include "ttt.h"

int think(Board&,int,int);
int minimax(Board&,int,int);

#endif


search.cpp
#include "search.h"

int think(Board &b,int stm,int depth){
int best=-100,val;
int best_move=-1;

for(int i=0;i<9;++i){
if((b.m_bits[O]|b.m_bits[X]) & 1<<i)
continue;

b.place(i,stm);
val=-minimax(b,stm^1,depth-1);
b.remove(i,stm);

if(val>best){
best=val;
best_move=i;
}
}

return best_move;
}

int minimax(Board &b,int stm,int depth){
switch(b.state()){
case HWIN: return stm?-100+b.move_number:+100-b.move_number;
case CWIN: return stm?+100-b.move_number:-100+b.move_number;
case DRAW: return 0;
}

if(depth<=0)
return 0;

int best=-100,val;
for(int i=0;i<9;++i){
if((b.m_bits[O]|b.m_bits[X]) & 1<<i)
continue;

b.place(i,stm);
val=-minimax(b,stm^1,depth-1);
b.remove(i,stm);

if(val>best)
best=val;
}

return best;
}


main.cpp
#include "search.h"

#define INFO_AUTHOR "Tic Tac Toe - Bitboard Version, by Tom Cant\n\n"

int main(){
Board b;
cout<<INFO_AUTHOR;
cout<<b<<endl;

int s;
while(b.state()&PLAYING){
cin>>s;
b.place(s-1,O);
cout<<b<<endl;

b.place(think(b,X,9),X);
cout<<b<<endl;
}

cin.ignore();
cin.get();
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
...
There is more to life than MiniMax and unbeatable TicTac AI's
...

how about a probabilistic AI?
where the distribution of possible moves is based on recording what kinds of moves the player has made in previous games?
This should produce a fun opponent, who starts out dumb and gradually gets smarter as it 'learns' to imitate the player.

make sure you account for both local and global symmetry situations when comparing a possible move to the player's past moves

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
There is more to life than MiniMax and unbeatable TicTac AI's

It is a good starting place though. Everyone has to start somewhere... I bet you couldn't write unbeatable Tic-Tac-Toe without any prior knowledge of minimax.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by tomcant
Quote:
Original post by Anonymous Poster
There is more to life than MiniMax and unbeatable TicTac AI's

It is a good starting place though. Everyone has to start somewhere... I bet you couldn't write unbeatable Tic-Tac-Toe without any prior knowledge of minimax.


You're missing my point.
I'm trying to say that Minimax is Not a good starting point.
That something like a probabalistic AI is a simpler and better starting point compared to minimax.

In fact, UnBeatable is not even a good goal for TicTac AI. It is Not Fun to play a game where the AI is unbeatable.

Share this post


Link to post
Share on other sites
As far as I know, there's no such thing as an "unbeatable" tic tac toe AI. The only way to win is if the other player is an idiot and doesn't block a possible win, which is unlikely, or you trap him, which is also very iffy. If both players are good and watch out for that kind of stuff, any attempt at a sneak attack or a trap will result in a cat's game. Tic Tac Toe is the worst possible game to argue AI tactics because the game is SO simple and there's really no strategy per se.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Actually, in TicTac an ideal player can always force a Draw game. Thus that player cannot be beaten. - UnBeatable


unless you consider both players in a draw to have lost... then i guess both are beaten, but that doesnt make sense...


Yes it is true, TicTac is a very simple game, thus MiniMax is overkill, it takes any vestige of strategy away and replaces it with essentially a dictionary rulebook (ableit, one recalculated every turn).
This is why I'm advocating something simple, like a probabilistic 'imitation learning' AI, at least that would be beatable and have some varied intereactions durcing the course of games as it adapted.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!