Sign in to follow this  

Tic Tac Toe- Minimax Problem [Solved]

This topic is 4381 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

Hi , before you just brush this topic away , i would like you guys to know , i had put the same topic up , two days ago , but i felt i had to push myself a little before asking for help and i did. I did find some problems related to my evaluation funtion and the function which calculated game win. After which i decided to carry on. But the game wasnt performing as i wanted it too.I had to throw pruning out and settle with a normal minimax, even which isnt performing well. I have stared at the code for quite a long time in these past two days.But i have hit a wall now , and i could use some help! I would appreciate it if any of you could run this through your compiler and tell me where i am going wrong. Some problems i ve come across are : 1)The best value is not chosen, the max depth i start off with is 8 , so first move from player and one from computer must evaluate the poistion to 1. But it evaluates to 0. 2)The game crashes for some inputs, i cant seem to trace the roots of it. One possible combination is : 0,0...0,2 ..2,0. Ie when the player is about to win.

//////// Defines

#define BLANK 0
#define X	  1
#define O    -1
#define INF   5000

int node_count=0;

//////// Includes
#include <iostream>
#include <vector>
#include <conio.h>

using namespace std;
using std::vector;




//game functions
void GameInitialize(int Tboard[3][3]);
bool BoardFull(int Tboard[3][3]);
bool GameWon(int Rboard[3][3],int &value);
void UserMove(int Rboard[3][3],int value);
void CompMove(int Rboard[3][3],int value);
void DrawBoard(int Rboard[3][3]);
void MoveContents(int Orig[3][3],int Copy[3][3]);





//Ai functions
int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count);
int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count,int alpha,int beta);
vector <int> GenerateMoves(int board[3][3]);
int Evaluate(int position[3][3],int turn);
int MaxScore(int value);

//Debug/Temp function's

void ApplyMove(int position[3][3],int start,int end,int turn);



void main()
{
int Lcount=0;
int board[3][3];
int val=0;
GameInitialize(board);	
DrawBoard(board);
while(Lcount<9 && !GameWon(board,val)&& !(BoardFull(board)))
{
	UserMove(board,O);
	Lcount++;
	DrawBoard(board);
	if(Lcount==9)
	continue;	
	CompMove(board,X);
	Lcount++;
	DrawBoard(board);
} 	

if(Lcount==9)
{
	if(!GameWon(board,val))
	cout<<"It was a Tie"<<endl;
	else
	cout<<"The game was won by "<<val<<endl;
}

if(GameWon(board,val))
{

cout<<"--The game was won by Extra if-- "<<val<<endl;
DrawBoard(board);
cout<<"Value of Lcount :"<<Lcount<<endl;
getch();
}

}


//game functions

void GameInitialize(int Tboard[3][3])
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			Tboard[i][j]=BLANK;
}


bool BoardFull(int Tboard[3][3])
{
int count=0;

for(int i=0;i<3;i++)
	for(int j=0;j<3;j++)
		if(Tboard[i][j]==0)
			count++;

	if(count>0)
	{
	//	cout<<"Bord is not full"<<endl;
		return false;
		
	}
	
		return true;
}

void UserMove(int Rboard[3][3],int value)
{
	int r,c;
	cout<<"Where do you want to enter R/C :";
	cin>>r>>c;
	Rboard[r][c]=value;
}



bool GameWon(int Rboard[3][3],int &value)
{
	if(Rboard[0][0]==Rboard[0][1] && Rboard[0][1]==Rboard[0][2])
		if(Rboard[0][0]!=0)
		{
		value=Rboard[0][0];
		return true;
		}

	if(Rboard[1][0]==Rboard[1][1] && Rboard[1][1]==Rboard[1][2])
		if(Rboard[1][0]!=0)
		{

		value=Rboard[1][0];
		return true;
		}

	if(Rboard[2][0]==Rboard[2][1] && Rboard[2][1]==Rboard[2][2])
		if(Rboard[2][0]!=0)
		{

		value=Rboard[2][0];
		return true;
		}
	
	if(Rboard[0][0]==Rboard[1][0] && Rboard[1][0]==Rboard[2][0])
		if(Rboard[0][0]!=0)
		{

		value=Rboard[0][0];
		return true;
		}
	
	if(Rboard[0][1]==Rboard[1][1] && Rboard[1][1]==Rboard[2][1])
		if(Rboard[0][1]!=0)
		{

		value=Rboard[0][1];
		return true;
		}

	if(Rboard[0][2]==Rboard[1][2] && Rboard[1][2]==Rboard[2][2])
		if(Rboard[0][2]!=0)
		{


		value=Rboard[0][2];
		return true;
		}

	if(Rboard[0][0]==Rboard[1][1] && Rboard[1][1]==Rboard[2][2])
		if(Rboard[0][0]!=0)
		{
		value=Rboard[0][0];
		return true;
		}

	if(Rboard[0][2]==Rboard[1][1] && Rboard[1][1]==Rboard[2][0])
		if(Rboard[0][2]!=0)
		{
		value=Rboard[0][2];
		return true;
		}
	
	return false;
}

void DrawBoard(int Rboard[3][3])
{
for(int i=0;i<3;i++)
	for(int j=0;j<3;j++)
	{
	switch(Rboard[i][j])
	{
	case 0:
		cout<<"-"<<" ";
		break;
	case 1:
		cout<<"X"<<" ";
		break;
	case -1:
		cout<<"O"<<" ";
		break;
	
	}
	if(j==2)
		cout<<endl;
	}
}


int MaxScore(int value)
{
	if(value==1)
		return -5000;
	if(value==-1)
		return 5000;
}


//Note :Early function used to push one value which was calculated
//		as row*width+colum , and extracted by division and modulus
//		operation 

void ApplyMove(int position[3][3],int row,int col,int turn)
{
	position[row][col]=turn;
}
 

void MoveContents(int Orig[3][3],int Copy[3][3])
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			Copy[i][j]=Orig[i][j];
}




//////////Ai Functions

void CompMove(int Rboard[3][3],int value)
{
int the_score=0;
int the_move[1][2];
int depth=0;
int max_depth=8;
int count=0;


the_score=MiniMax(Rboard,depth,max_depth,the_move,value,count);
ApplyMove(Rboard,the_move[0][0],the_move[0][1],value);

cout<<"The nodes analyzed are  "<<node_count<<endl;
cout<<"Value of count is  "<<count<<endl;
cout<<"Move chosen is  "<<the_move[0][0]<<" and "<<the_move[0][1]<<endl;
cout<<"The best score is  "<<the_score<<endl;

}

int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count)
{

	return MiniMax(position,depth,max_depth,chosen_move,turn,count,-INF,INF);

}


int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count,int alpha,int beta)
{

int local_score=0;
int local_position[3][3];
int local_best_score=0;
int local_best_move[1][2];
int local_the_move[1][2];


int temp;

if(depth==max_depth || GameWon(position,temp) || BoardFull(position))
{
	local_best_score=Evaluate(position,turn);
	count++;
}

else
{
	vector <int> moves_list ;
	moves_list= GenerateMoves(position);
	node_count+=moves_list.size();
	
	for(int i=0;i<moves_list.size();i=i+2)
	{	

		MoveContents(position,local_position);
		ApplyMove(local_position,moves_list[i],moves_list[i+1],turn);
		local_score=MiniMax(local_position,depth+1,max_depth,local_the_move,-turn,count,alpha,beta);

/*		
		if(i>2)
		{
		last_move_r=moves_list[i-2];
		last_move_c=moves_list[1-1];
		}
*/
		if((turn==1) && (local_score>=local_best_score))
		{
		local_best_move[0][0]=moves_list[i];
		local_best_move[0][1]=moves_list[i+1];
		local_best_score=local_score;
		}

		//looking to minimize
		if((turn==-1) && (local_score <=local_best_score))
		{
		local_best_move[0][0]=moves_list[i];
		local_best_move[0][1]=moves_list[i+1];
		local_best_score=local_score;				
		}
	}		
}

chosen_move[0][0]=local_best_move[0][0];
chosen_move[0][1]=local_best_move[0][1];

/*if(depth==0)
{
cout<<"Parent was"<<endl;
DrawBoard(position);
cout<<"last chosen moves are "<<last_move_r<<" and "<<last_move_c<<endl;
cout<<"The chosen moves are "<<chosen_move[0][0]<<" and "<<chosen_move[0][1]<<endl;
cout<<"Local best score after is "<<local_best_score<<endl;
}*/

return local_best_score;
}


//Note :Early function used to push one value which was calculated
//		as row*width+colum , and extracted by division and modulus
//		operation

vector <int> GenerateMoves(int board[3][3])
{
vector <int> moves;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(board[i][j]==0)
			{
			moves.push_back(i);
			moves.push_back(j);
			}

	return moves;
	
}




int Evaluate(int position[3][3],int turn)
{
	int winner;
	int temp;

	if(GameWon(position,winner))
	{
		if(winner==1)
		{
			return 1;
		}
		if(winner==-1)
		{
			return -1;
		}
	}

	return 0;
}




[Edited by - Nokturnal on December 20, 2005 11:01:42 AM]

Share this post


Link to post
Share on other sites
The first problem I see, is that your MoveContents() function does not do what you think. When you call MoveContents(), it creates a copy of the parameters you pass to it for the function to work on. You should pass these parameters using a reference. That way, the function will act upon the original copies of the data. If you are still having problems after that, post back!


[edit]: On second thoughts, it would be a lot easier for you to pass the board as a singularly dimensioned array, instead of your 2D one. In your source code you do mention having tried this, so I suggest you go back to that method, then you can pass the board using a pointer. I.e.: void MoveContents(int* from,int* to);

Share this post


Link to post
Share on other sites
Hi tomcant , thanks for the suggestion. I was actually following a java code as a example. In java any thing which is a object is passed by reference. So i though is such a thing possible in c++ ? I wrote a small code to demonstrate this and it works. Thus the function is performing well. It is accepting the arguements as references. Try running this code through you compiler



#include <iostream>
using namespace std;

void MoveContents(int Orig[3][3],int Copy[3][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
Copy[i][j]=Orig[i][j];
}


void main()
{
int Oboard[3][3];
int Cboard[3][3];

for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
Oboard[i][j]=10;

MoveContents(Oboard,Cboard);

for(int k=0;k<3;k++)
for(int l=0;l<3;l++)
cout<<Cboard[k][l]<<" ";

}






I did manage to correct one mistake, i was not initializing the best score as per the node.Here is the corrected code.It plays a pretty strong game of tic tac toe.It never looses.


//////// Defines

#define BLANK 0
#define X 1
#define O -1
#define INF 5000

int node_count=0;

//////// Includes
#include <iostream>
#include <vector>
#include <conio.h>

using namespace std;
using std::vector;




//game functions
void GameInitialize(int Tboard[3][3]);
bool BoardFull(int Tboard[3][3]);
bool GameWon(int Rboard[3][3],int &value);
void UserMove(int Rboard[3][3],int value);
void CompMove(int Rboard[3][3],int value);
void DrawBoard(int Rboard[3][3]);
void MoveContents(int Orig[3][3],int Copy[3][3]);





//Ai functions
int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count);
int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count,int alpha,int beta);
vector <int> GenerateMoves(int board[3][3]);
int Evaluate(int position[3][3],int turn);
int MaxScore(int value);

//Debug/Temp function's

void ApplyMove(int position[3][3],int start,int end,int turn);



void main()
{
int Lcount=0;
int board[3][3];
int val=0;
GameInitialize(board);
DrawBoard(board);
while(Lcount<9 && !GameWon(board,val)&& !(BoardFull(board)))
{
UserMove(board,O);
Lcount++;
DrawBoard(board);
if(GameWon(board,val))
continue;
if(Lcount==9)
continue;
CompMove(board,X);
Lcount++;
DrawBoard(board);
}

if(Lcount==9)
{
if(!GameWon(board,val))
cout<<"It was a Tie"<<endl;
else
cout<<"The game was won by "<<val<<endl;
}

if(GameWon(board,val))
{

cout<<"--The game was won by Extra if-- "<<val<<endl;
DrawBoard(board);
cout<<"Value of Lcount :"<<Lcount<<endl;
getch();
}

}


//game functions

void GameInitialize(int Tboard[3][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
Tboard[i][j]=BLANK;
/*
Tboard[0][0]=-1;
Tboard[0][2]=-1;

Tboard[0][1]=1;
Tboard[2][2]=1;
*/

}


bool BoardFull(int Tboard[3][3])
{
int count=0;

for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(Tboard[i][j]==0)
count++;

if(count>0)
{
// cout<<"Bord is not full"<<endl;
return false;

}

return true;
}

void UserMove(int Rboard[3][3],int value)
{
int r,c;
cout<<"Where do you want to enter R/C :";
cin>>r>>c;
Rboard[r][c]=value;
}



bool GameWon(int Rboard[3][3],int &value)
{
if(Rboard[0][0]==Rboard[0][1] && Rboard[0][1]==Rboard[0][2])
if(Rboard[0][0]!=0)
{
value=Rboard[0][0];
return true;
}

if(Rboard[1][0]==Rboard[1][1] && Rboard[1][1]==Rboard[1][2])
if(Rboard[1][0]!=0)
{

value=Rboard[1][0];
return true;
}

if(Rboard[2][0]==Rboard[2][1] && Rboard[2][1]==Rboard[2][2])
if(Rboard[2][0]!=0)
{

value=Rboard[2][0];
return true;
}

if(Rboard[0][0]==Rboard[1][0] && Rboard[1][0]==Rboard[2][0])
if(Rboard[0][0]!=0)
{

value=Rboard[0][0];
return true;
}

if(Rboard[0][1]==Rboard[1][1] && Rboard[1][1]==Rboard[2][1])
if(Rboard[0][1]!=0)
{

value=Rboard[0][1];
return true;
}

if(Rboard[0][2]==Rboard[1][2] && Rboard[1][2]==Rboard[2][2])
if(Rboard[0][2]!=0)
{


value=Rboard[0][2];
return true;
}

if(Rboard[0][0]==Rboard[1][1] && Rboard[1][1]==Rboard[2][2])
if(Rboard[0][0]!=0)
{
value=Rboard[0][0];
return true;
}

if(Rboard[0][2]==Rboard[1][1] && Rboard[1][1]==Rboard[2][0])
if(Rboard[0][2]!=0)
{
value=Rboard[0][2];
return true;
}

return false;
}

void DrawBoard(int Rboard[3][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
switch(Rboard[i][j])
{
case 0:
cout<<"-"<<" ";
break;
case 1:
cout<<"X"<<" ";
break;
case -1:
cout<<"O"<<" ";
break;

}
if(j==2)
cout<<endl;
}
}


int MaxScore(int value)
{
if(value==1)
return -5000;
if(value==-1)
return 5000;
}


//Note :Early function used to push one value which was calculated
// as row*width+colum , and extracted by division and modulus
// operation

void ApplyMove(int position[3][3],int row,int col,int turn)
{
position[row][col]=turn;
}


void MoveContents(int Orig[3][3],int Copy[3][3])
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
Copy[i][j]=Orig[i][j];
}




//////////Ai Functions

void CompMove(int Rboard[3][3],int value)
{
int the_score=0;
int the_move[1][2];
int depth=0;
int max_depth=20;
int count=0;


the_score=MiniMax(Rboard,depth,max_depth,the_move,value,count);
ApplyMove(Rboard,the_move[0][0],the_move[0][1],value);

cout<<"The nodes analyzed are "<<node_count<<endl;
cout<<"Value of count is "<<count<<endl;
cout<<"Move chosen is "<<the_move[0][0]<<" and "<<the_move[0][1]<<endl;
cout<<"The best score is "<<the_score<<endl;

}

int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count)
{

return MiniMax(position,depth,max_depth,chosen_move,turn,count,-INF,INF);

}


int MiniMax(int position[3][3],int depth,int max_depth,int chosen_move[1][2],int turn,int &count,int alpha,int beta)
{

int the_score=0;
int new_position[3][3];
int best_score=0;
int best_move[1][2];
int the_move[1][2];
int temp=0;

if(depth==max_depth || GameWon(position,temp) || (BoardFull(position)==1))
{

best_score=Evaluate(position,turn);
count++;
// cout<<"Hit Eval for : "<<endl;
// DrawBoard(position);
// cout<<"Value evaled was "<<best_score<<endl;
// getch();

return best_score;
}

else
{
// cout<<"---------- In Else Part---------"<<endl;
vector <int> moves_list ;
moves_list= GenerateMoves(position);
node_count+=moves_list.size();

// cout<<"the node thus is "<<endl;
// DrawBoard(position);
// for(int j=0;j<moves_list.size();j=j+2)
// cout<<"Possible move is "<<moves_list[j]<<" and "<<moves_list[j+1]<<endl;
// getch();

best_score=MaxScore(turn);

for(int i=0;i<moves_list.size();i=i+2)
{

// cout<<"Parent node thus is "<<endl;
// DrawBoard(position);
// cout<<"Move is "<<moves_list[i]<<" and "<<moves_list[i+1]<<endl;


MoveContents(position,new_position);
ApplyMove(new_position,moves_list[i],moves_list[i+1],turn);

// cout<<"New Position becomes "<<endl;
// DrawBoard(new_position);
// getch();

the_score=MiniMax(new_position,depth+1,max_depth,the_move,-turn,count,alpha,beta);

if((turn==1) && (the_score >=best_score))
{
best_move[0][0]=moves_list[i];
best_move[0][1]=moves_list[i+1];
best_score=the_score;
}

//looking to minimize
if((turn==-1) && (the_score <=best_score))
{
best_move[0][0]=moves_list[i];
best_move[0][1]=moves_list[i+1];
best_score=the_score;
}
}
}

chosen_move[0][0]=best_move[0][0];
chosen_move[0][1]=best_move[0][1];


return best_score;
}


//Note :Early function used to push one value which was calculated
// as row*width+colum , and extracted by division and modulus
// operation

vector <int> GenerateMoves(int board[3][3])
{
vector <int> moves;

for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(board[i][j]==0)
{
moves.push_back(i);
moves.push_back(j);
}

return moves;

}




int Evaluate(int position[3][3],int turn)
{
int winner;
int temp;

if(GameWon(position,winner))
{
if(winner==1)
{
return 1;
}
if(winner==-1)
{
return -1;
}
}

return 0;
}




I still have a concern though, when the game starts out, after user makes a move, and its computers turn. the value of the best move is 0 ,where as it should be 1 if am following the algorithm correctly.
Well , almost close to slam dunk this one! :)

Share this post


Link to post
Share on other sites
Hmmm, ok. I still think you are making it more complicated than it needs to be. In my tic-tac-toe engine, I just have a single 1D array for the board representation, and this works fine. This makes everything a little clearer and easier to understand. I can show you the code if you like...?

Share this post


Link to post
Share on other sites
In part i am using 2D representation as i ll be using the same structure for my checkers game , so i thought if it would be better to work on a simple game as tic tac toe to get the hang of result.

Sure , i would love to go through your code!

Ps: i ve updated the code above. A small problem remains!

Share this post


Link to post
Share on other sites
I have written a checkers game too, where I still use a 1D array. Is there any specific reason as to why you can't use a 1D array? If not, then it's probably your best bet to try it out. I could give you some helpful pointers on how to use them in this way, if you like.

Here is my TTT engine source:
main.cpp
#include "ttt.h"
#include <cstdio>

void printBoard(Board const &b) {
for(int i=0;i<9;++i) {
printf("%c "," OX -"[b.board[i]]);
if(!((i+1)%3))
putchar('\n');
}
}

int main() {
printf("Tic Tac Toe - by Tom Cant\n\n");

Board b; //everything happens from here
int h_x,h_y; //human move information

while(b.state()&PLAYING) {
printBoard(b);
scanf("%d %d",&h_x,&h_y);
if(h_x>=0 && h_x<=2 && h_y>=0 && h_y<=2) {
if(b.board[h_x*3+h_y]&empty) {
b.board[h_x*3+h_y]=O;
printf("\n");
if(b.state()&PLAYING)
b.board[b.think(7,X)]=X;
} else printf("\nInvalid move!\n");
} else printf("\nInvalid move!\n");
printf("\n");
}

//print the final game position
printBoard(b);
getchar();
getchar();
}


ttt.h
#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
};

//I use these values to detect
//if a side won on their turn.
static const int lines[8*3] = {
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 {
//the game board is stored
//as an array of 9 elements.
Player board[9];

Board() {
for(int i=0;i<9;++i)
board[i]=empty;
}

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

//this function is used by `minimax()' to
//determine the current state of play.
int state() {
if(check_for_win(X))
return C_WIN; //computer won!
if(check_for_win(O))
return H_WIN; //human won!
for(int i=0;i<9;++i)
if(board[i]&empty)
return PLAYING;
return DRAW;
}

//this function is what kicks off the
//tree generating process.
int think(int depth,Player p) {
int best=-100,m;

for(int i=0;i<9;++i) {
if(board[i]&empty) {
board[i]=p;
int val=-minimax(depth-1,p&O?X:O);
board[i]=empty;
if(val>best) {
best=val;
m=i;
}
}
}

return m;
}

//this is the tree generating function.
//it is very similiar to `think()' by
//definition, but it is different enough
//that it is best to keep them seperate.
int minimax(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<=0)
return 0;

int best=-100;

for(int i=0;i<9;++i) {
if(board[i]&empty) {
board[i]=p;
int val=-minimax(depth-1,p&O?X:O);
board[i]=empty;
if(val>best)
best=val;
}
}

return best;
}
};

#endif

Share this post


Link to post
Share on other sites
Wow , it will take me a while to go through this. I ve pm'ed you regarding the same.

Cheers!

Edit : realized the balance will stay 0 at the start regardless. Its finally over :)

[Edited by - Nokturnal on December 20, 2005 11:43:20 AM]

Share this post


Link to post
Share on other sites

This topic is 4381 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this