# Tic Tac Toe- Minimax Problem [Solved]

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

## 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[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[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[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[j]=Orig[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,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;
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;
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[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 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!

: 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 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[j]=Orig[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[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   5000int node_count=0;//////// Includes#include <iostream>#include <vector>#include <conio.h>using namespace std;using std::vector;//game functionsvoid 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 functionsint 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'svoid 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 functionsvoid GameInitialize(int Tboard[3][3]){	for(int i=0;i<3;i++)		for(int j=0;j<3;j++)			Tboard[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[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[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[j]=Orig[j];}//////////Ai Functionsvoid 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<<" and "<<moves_list[i+1]<<endl;				MoveContents(position,new_position);		ApplyMove(new_position,moves_list,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;		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;		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//		operationvector <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[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 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 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 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]);    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=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&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&empty) {        board=p;        int val=-minimax(depth-1,p&O?X:O);        board=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&empty) {        board=p;        int val=-minimax(depth-1,p&O?X:O);        board=empty;                if(val>best)          best=val;      }    }        return best;  }};#endif

##### 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]

1. 1
Rutin
26
2. 2
3. 3
4. 4
5. 5

• 9
• 13
• 19
• 14
• 9
• ### Forum Statistics

• Total Topics
632940
• Total Posts
3009329
• ### Who's Online (See full list)

There are no registered users currently online

×