//////// 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;
}
Tic Tac Toe- Minimax Problem [Solved]
December 19, 2005 04:47 PM
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.
[Edited by - Nokturnal on December 20, 2005 11:01:42 AM]
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
138
December 20, 2005 07:25 AM
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);
[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);
______Tom
December 20, 2005 08:34 AM
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
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.
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! :)
#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! :)
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
138
December 20, 2005 08:47 AM
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...?
______Tom
December 20, 2005 08:49 AM
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!
Sure , i would love to go through your code!
Ps: i ve updated the code above. A small problem remains!
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
138
December 20, 2005 08:58 AM
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
ttt.h
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
______Tom
December 20, 2005 09:43 AM
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]
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]
"I think there is a world market for maybe five computers." -- Thomas Watson, Chairman of IBM, 1943
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
