TicTacToeUsing AI(Minimax Algorithm & alpha-beta)
Made By Md.Saiful Islam
*********************************************************************************************************/
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <set>
#include <cmath>
#include <windows.h>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <vector>
#include <iomanip>
using namespace std;
#ifdef __GNUC__
typedef long long ll;typedef unsigned long long ull;
#else
typedef __int64 ll; typedef unsigned __int64 ull;
#endif
#define inf 1000000
#define SIZE 10001
#define pi (2*acos(0.0))
#define forn(i,n) for (i=0;i<n;i++)
#define forr(i,n) for (i=n-1;i>=0;i--)
#define forab(i,p,k) for (i=p; i<=k;i++)
#define FOREACH(it,x) for(__typeof((x).begin()) it=(x.begin()); it!=(x).end(); ++it)
#define bug(x) cout<< "->" <<#x<<": "<<x<<endl
#define Sort(x) sort(x.begin(),x.end())
#define Reverse(x) reverse(x.begin(),x.end())
#define mp(a,b) make_pair(a,b)
#define zero(x,with) memset(x,with,sizeof(x))
#define copy(c,r) memcpy(c,r,sizeof(r))
#define sz(x) (int)x.size()
#define length(x) (int)x.length()
#define all(x) x.begin(),x.end()
#define pb push_back
#define popcount(i) __builtin_popcount(i)
#define gcd(a,b) __gcd(a,b)
#define fs first
#define sc second
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
#define maxi(v) *max_element(all(v))
#define mini(v) *min_element(all(v))
#define CS c_str()
#define clr clear()
#define err 1e-9
#define even(a) ((a)%2==0)
#define odd(a) ((a)%2==1)
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<double>vd;
typedef vector<ll>vll;
typedef vector<string> vs;
typedef vector<vi>vvi;
typedef vector<vll>vvll;
typedef vector<vd>vvd;
typedef vector<pii>vpii;
typedef map<string,int> msi;
typedef map<int,int>mii;
typedef map<pii,int>mpi;
template<class T> inline T gcd(T a,T b) {if(!b) return a; else return gcd(b,a%b);}
template<class T> void b_sort(vector<T>& VT) {for(int i=VT.sz;i>0;i--)for(int j=1;j<i;j++)if(VT[j]<VT[j-1]) swap(VT[j],VT[j-1]);}
template<class T> inline T sqr(T x){return x*x;}
template<class T> inline bool isprime(T n){if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
template<class T> inline T mod(T n,T m) {return (n%m+m)%m;} //For Positive Negative No.
template<class T> string tostring(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
int toint(string s){int r=0;istringstream sin(s);sin>>r;return r;}
ll toll(string s){ll r=0;istringstream sin(s); sin>>r; return r;}
template<class T> void debug(const T& e){cout<<e<<endl;}
template<class T1,class T2> void debug(const T1& e1,const T2& e2){cout<<e1<<"\t"<<e2<<endl;}
template<class T1,class T2,class T3> void debug(const T1& e1,const T2& e2,const T3& e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
template<class T1,class T2,class T3,class T4> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
template<class T1,class T2,class T3,class T4,class T5> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4,const T5& e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
template<class T> void debug(vector<T>& e){int i;forn(i,sz(e)) cout<<e[i]<<" ";cout<<endl;}
template<class T> void debug(vector< basic_string<T> >& e){int i,j;forn(i,sz(e)) {forn(j,sz(e[i])) cout<<e[i][j];cout<<endl;} cout<<endl;}
template<class T> void debug(vector< vector<T> >& e,int row,int col){int i,j;forn(i,row) {forn(j,col) cout<<e[i][j]<<"\t";cout<<endl;} cout<<endl;}
template<class T> void debug(T e[SIZE][SIZE],int row,int col){int i,j;forn(i,row) {forn(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
inline bool iseq(double x,double y){if(fabs(x-y)<err)return true;return false;}
template<typename T>inline T bigmod(T b,T p,T m){if(!p)return 1;else if(!(p%2)){T x=bigmod(b,p/2,m);return x*x;}else return ((b%m)*bigmod(b,p-1,m))%m;}
static enum {START, PLAYING, QUIT, OWIN, XWIN, DRAW} state;
ll Pow(ll B,ll P){ ll R=1; while(P>0) {if(P%2==1) R=(R*B);P/=2;B=(B*B);}return R;} //compute b^p
typedef struct
{
string name;
char symbol;
int draw_num,move,game_win;
bool selected,win;
} player;
player player1, player2, currentPlayer;
string gameType,prevGameType;
char gameBoard[9] = {0},PlaySymbol;
int playMove,len;
void mainDisplayWindow()
{
cout << "\n================================================================================" << endl;
cout << " TicTacToe game Using AI Minimax Algorithm - Saiful Saif " << endl;
cout << "================================================================================" << endl;
}
void playingOption();
void getMove();
void resetPlayerName() { player1.name.erase();player2.name.erase();}
void resetWinner() { player1.win = 0; player2.win = 0; }
void initPlayerMove() { player1.move = -1; player2.move = -1; }
void resetState() { state = PLAYING;}
void resetGameBoard() { for(int i = 0; i < 9; ++i) gameBoard[i] = 0; }
void UpdateDisplay() {mainDisplayWindow(); playingOption(); }
bool worngSymbol() { return (PlaySymbol != 'X' && PlaySymbol != 'O'); }
bool wrong_selection() { return !(playMove > 0 && playMove < 10); }
bool game_over() { return (state == XWIN || state == OWIN || state == DRAW); }
int MiniMax(char board[9], player _player);
int MinMove(char board[9], player _player);
int MaxMove(char board[9], player _player);
void getPlayerName()
{
if(gameType == "human vs computer")
{
cout << "\nplease enter your name: ";
cin >> player1.name;
len = sz(player1.name);
if(len == 0) getPlayerName();
player2.name = "the computer";
}
else if(gameType == "human vs human")
{
len = sz(player1.name);
while(len == 0)
{
cout << "\nplayer1 please enter your name: ";
cin >> player1.name;
len = sz(player1.name);
}
len = sz(player2.name);
while(len == 0)
{
cout << "player2 please enter your name: ";
cin >> player2.name;
len = sz(player2.name);
}
}
}
void getPlayerSymbol()
{
int x,selection;
if(gameType == "human vs computer")
{
x = rand();
selection = x % 2;
cout << x << endl;
if(selection == 0)
{
if(rand() % 2 == 0) player2.symbol = 'X';
else player2.symbol = 'O';
PlaySymbol = player2.symbol;
player2.selected = 1;
cout << player2.name << " will play \'" << player2.symbol << "\'" << endl;
}
else if(selection == 1)
{
cout << player1.name << " please enter your symbol (X, O): ";
cin >> player1.symbol;
player1.symbol = toupper(player1.symbol);
PlaySymbol = player1.symbol;
player1.selected = 1;
}
}
else if(gameType == "human vs human")
{
int Set = rand() % 2;
string playerName = "";
if(Set == 0)
{
playerName = player1.name;
player1.selected = 1;
}
else if(Set == 1)
{
playerName = player2.name;
player2.selected = 1;
}
cout << "\n" << playerName << " Please enter your symbol (X, O): ";
if(Set == 0)
{
cin >> player1.symbol;
player1.symbol = toupper(player1.symbol);
PlaySymbol = player1.symbol;
}
else
{
cin >> player2.symbol;
player2.symbol = toupper(player2.symbol);
PlaySymbol = player2.symbol;
}
}
if(!cin.good() || worngSymbol())
{
cout << "Please use symbol X or O" << endl;
getPlayerSymbol();
}
if(!player2.selected)
{
if(player1.symbol == 'X') player2.symbol = 'O'; else player2.symbol = 'X';
if(player1.symbol == 'O') player2.symbol = 'X'; else player2.symbol = 'O';
}
else if(!player1.selected)
{
if(player2.symbol == 'X') player1.symbol = 'O'; else player1.symbol = 'X';
if(player2.symbol == 'O') player1.symbol = 'X'; else player1.symbol = 'O';
}
state = PLAYING;
}
void playingOption()
{
int choice;
cout << " 1 - Play a game against the computer" << endl;
cout << " 2 - Continue with the same player" << endl;
cout << " 3 - Play against another player" << endl;
cout << " 4 - Quit from the game" << endl;
cout << "\n Selection: ";
cin >> choice;
if(!cin.good())
{
cout << "Please enter integers(1 - 4) for the selection" << endl;
UpdateDisplay();
}
switch(choice)
{
case 1:
gameType = "human vs computer"; break;
case 2:
if(gameType == "") UpdateDisplay(); break;
case 3:
gameType = "human vs human"; break;
case 4:
state = QUIT; break;
default:
cout << "Invalid Selection." << endl; UpdateDisplay();
}
if(choice > 0 && choice < 4)
{
if(prevGameType != "" && gameType != prevGameType)
{
resetPlayerName();
getPlayerName(); getPlayerSymbol();
}
len = sz(gameType);
if(len > 0) prevGameType = gameType;
}
}
bool free_square()
{
if(player1.move != -1 && player2.move == -1) return gameBoard[player1.move - 1] == 0;
else if(player2.move != -1) return gameBoard[player2.move - 1] == 0;
return 0;
}
void verify_move()
{
if(wrong_selection() || !free_square())
{
cout << "Invalid Move." << endl;
if(player2.move == -1)
{
player1.selected = 1;
player2.selected = 0;
}
else
{
player1.selected = 0;
player2.selected = 1;
}
system("pause");
if(gameType == "human vs computer")
{
player1.selected = 1;
player2.selected = 0;
}
getMove();
}
}
void getMove()
{
if(gameType == "human vs human")
{
if(player1.selected)
{
cout << player1.name << " please enter your move (1 - 9): ";
cin >> player1.move;
playMove = player1.move;
PlaySymbol = player1.symbol;
player1.selected = 0;
player2.selected = 1;
currentPlayer = player1;
}
else if(player2.selected)
{
cout << player2.name << " please enter your move (1 - 9): ";
cin >> player2.move;
playMove = player2.move;
PlaySymbol = player2.symbol;
player1.selected = 1;
player2.selected = 0;
currentPlayer = player2;
}
}
else if(gameType == "human vs computer")
{
if(player1.selected)
{
cout << "\n" << player1.name << " please enter your move (1 - 9): ";
cin >> player1.move;
playMove = player1.move;
PlaySymbol = player1.symbol;
currentPlayer = player1;
player1.selected = 0;
player2.selected = 1;
}
else if(player2.selected)
{
player2.move = MiniMax(gameBoard, player2);
playMove = player2.move;
PlaySymbol = player2.symbol;
currentPlayer = player2;
player1.selected = 1;
player2.selected = 0;
resetState();
}
}
verify_move();
if(game_over()) { return; }
}
void winnerSearch()
{
if(state == XWIN && player1.symbol == 'X') player1.win = 1;
else if(state == OWIN && player1.symbol == 'O') player1.win = 1;
else if(state == XWIN && player2.symbol == 'X') player2.win = 1;
else if(state == OWIN && player2.symbol == 'O') player2.win = 1;
}
void updateGameBoard()
{
if(state == PLAYING)
{
if(player1.move != -1 && player2.move == -1) { gameBoard[player1.move - 1] = player1.symbol; }
else if(player2.move != -1) { gameBoard[player2.move - 1] = player2.symbol; }
}
}
void displayResult()
{
if(player1.win) { cout << player1.name << " has won the game!!!!!!!!!!!!!! :(( " << endl; }
else if(player2.win) { cout << player2.name << " has won the game !!!!!!!!!!!!! :(( " << endl; }
else if(player1.win == 0 && player2.win == 0) { cout << "Ohhh......... No winner, Game draw !!!!!!" << endl;}
}
void display_board() {
cout << endl;
cout << " " << gameBoard[0] << " | " << gameBoard[1] << " | " << gameBoard[2] << endl;
cout << "-----------" << endl;
cout << " " << gameBoard[3] << " | " << gameBoard[4] << " | " << gameBoard[5] << endl;
cout << "-----------" << endl;
cout << " " << gameBoard[6] << " | " << gameBoard[7] << " | " << gameBoard[8] << endl;
cout << endl;
cin.sync();
}
void display_game_progress()
{
cout << "\n\nboard position after " << currentPlayer.name << "\'s move" << endl;
display_board();
}
void check_game_state(char gameBoard[9])
{
if ((gameBoard[0] == PlaySymbol && gameBoard[1] == PlaySymbol && gameBoard[2] == PlaySymbol) ||
(gameBoard[3] == PlaySymbol && gameBoard[4] == PlaySymbol && gameBoard[5] == PlaySymbol) ||
(gameBoard[6] == PlaySymbol && gameBoard[7] == PlaySymbol && gameBoard[8] == PlaySymbol) ||
(gameBoard[0] == PlaySymbol && gameBoard[3] == PlaySymbol && gameBoard[6] == PlaySymbol) ||
(gameBoard[1] == PlaySymbol && gameBoard[4] == PlaySymbol && gameBoard[7] == PlaySymbol) ||
(gameBoard[2] == PlaySymbol && gameBoard[5] == PlaySymbol && gameBoard[8] == PlaySymbol) ||
(gameBoard[0] == PlaySymbol && gameBoard[4] == PlaySymbol && gameBoard[8] == PlaySymbol) ||
(gameBoard[2] == PlaySymbol && gameBoard[4] == PlaySymbol && gameBoard[6] == PlaySymbol))
{
if(PlaySymbol == 'X') state = XWIN;
else if(PlaySymbol == 'O') state = OWIN;
}
else
{
int i;
state = DRAW;
for(i = 0; i < 9; ++i)
{
if(gameBoard[i] == 0)
{
state = PLAYING;
break;
}
}
}
}
void updateGamePosition()
{
updateGameBoard();
display_game_progress();
check_game_state(gameBoard);
}
void generateMoves(char board[9], list<int> &moveList)
{
for(int i = 0; i < 9; ++i)
if( board[i] == 0 ) moveList.push_back(i);
}
int evaluate_position(char board[9], player _player)
{
check_game_state(board);
if( game_over() )
if((state == XWIN && _player.symbol == 'X') || (state == OWIN && _player.symbol == 'O')) return +inf;
else if((state == XWIN && _player.symbol == 'O') ||(state == OWIN && _player.symbol == 'X'))return -inf;
else if(state == DRAW) return 0;
return -1;
}
int MiniMax(char board[9], player _player)
{
int maxValue = -inf, index = 0,val;
list<int> moveList;
char bestMove[9] = {0};
generateMoves(board, moveList);
while( !moveList.empty() )
{
board[moveList.front()] = _player.symbol;
PlaySymbol = _player.symbol;
val = MinMove(board, _player);
if(val > maxValue)
{
maxValue = val; index = 0;
bestMove[index] = moveList.front() + 1;
}
else if(val == maxValue) bestMove[++index] = moveList.front() + 1;
board[moveList.front()] = 0;
moveList.pop_front();
}
if(index > 0) index = rand() % index;
return bestMove[index];
}
int MinMove(char board[9], player _player)
{
int positionValue,maxValue,val;
list<int> moveList;
positionValue = evaluate_position(board, _player);
maxValue = +inf;
if(positionValue != -1) return positionValue;
generateMoves(board, moveList);
while( !moveList.empty() )
{
if(_player.symbol == 'X') PlaySymbol = 'O'; else PlaySymbol = 'X';
board[moveList.front()] = PlaySymbol;
val = MaxMove(board, _player);
if(val < maxValue) maxValue = val;
board[moveList.front()] = 0;
moveList.pop_front();
}
return maxValue;
}
int MaxMove(char board[9], player _player)
{
int positionValue,maxValue,val;
list<int> moveList;
positionValue = evaluate_position(board, _player);
maxValue = -inf;
if(positionValue != -1) return positionValue;
generateMoves(board, moveList);
while( !moveList.empty() )
{
if(_player.symbol == 'X') PlaySymbol = 'X'; else PlaySymbol = 'O';
board[moveList.front()] = PlaySymbol;
val = MinMove(board, _player);
if(val > maxValue) maxValue = val;
board[moveList.front()] = 0;
moveList.pop_front();
}
return maxValue;
}
int main()
{
mainDisplayWindow();
playingOption();
if(state != QUIT)
{
getPlayerName();
getPlayerSymbol();
while(state != QUIT)
{
while(state == PLAYING)
{
initPlayerMove();
getMove();
updateGamePosition();
}
if( game_over() )
{
winnerSearch();
displayResult();
resetState();
resetGameBoard();
mainDisplayWindow();
}
playingOption();
}
}
return 0;
}
No comments:
Post a Comment