#include<time.h>
#include<stdlib.h>
#include<iostream>
#include<limits.h>
#include <vector>
using namespace std;


enum player{EMPTY,CROSS,CIRCLE};

typedef struct{
	int rowIdx;
	int colIdx;
	int score;
}position;

class TicTacToe{

	private:
		int row;
		int col;
	public:
		TicTacToe(int r,int c)
		{
			row=r;
			col=c;
		}
		
	protected :
		virtual position FindnextMove()=0;
		virtual void SetPosition(position)=0;

		virtual int getSize()
                {
                        return row*col;
                }
                int getRow()
                {
                        return row;
                }
                virtual int getCol()
                {
                        return col;
                }
	
	public :
		virtual void start(player p=CIRCLE,int set=0)=0;
};
class AIGame : public TicTacToe{

int turn;
int **board;
player human;
player computer;
player win;
	public:
		AIGame(int row=3,int col=3):TicTacToe(row,col)
		{
			turn=0;
			board=new int*[getRow()];
			for(int i=0;i<getRow();i++)
			{
				board[i]=new int[getRow()];
				for(int j=0;j<getCol();j++)
				{
					board[i][j]=EMPTY;
				}	
			}
			human=CIRCLE;
			computer=CROSS;
			win=EMPTY;
		}
		virtual position FindnextMove()
		{
			return minMax(1,computer,INT_MIN,INT_MAX);
		}
		virtual void SetPosition(position loc)
		{

		}
		virtual void setSign(player p1)
		{
			
			if(p1==CROSS)
			{
				human=CROSS;
				computer=CIRCLE;
			}
		}
		virtual void start(player p=CIRCLE,int set=0)
		{
			int r,c,pos;
			setSign(p);	
			turn=set;
			int size=getSize();
			position temp;	
			int entry=1;
			display();	
			for(int i=0;i<getSize();i++)
			{
				if(turn)
				{	
					while(1)
					{
						cout<<"\nEnter position ( 1 - "<<getSize()<<" ) = ";
						cin>>pos;
							
						r=(pos-1)/(getRow());
						c=(pos-1)%(getCol());

						if(pos > 0 && pos <= getSize() && board[r][c]==EMPTY)
						{
							board[r][c]=human;
							turn=!turn;
							break;
						}
						else
						{
							cout<<"\nInvalid Input!!";
						}
					}
					
				}
				else
				{
					temp=FindnextMove();
					//cout<<"\nrow = "<<temp.rowIdx<<" col = "<<temp.colIdx<<"score "<<temp.score<<"\n"; 
					if(entry)
					{
						srand(time(NULL));
						for(int itr=0;itr<5;itr++)
						{
							r=rand()%getRow();
							c=rand()%getCol();
	
							if(board[r][c]!=human)
								break;
						}
						board[r][c]=computer;
					 entry=0;
					}
					else
					{

						board[temp.rowIdx][temp.colIdx]=computer;
					}
					turn=!turn;
				}
				
				system("clear");
				display();
				
				if(i>=4)
				{
					if(isGameOver(1))
						break;
				}
			}
			
			system("clear");
			display();
			if(win==human)
			{
				cout<<"\n\t  Human Wins !!\n\n";
			}
			else if(win==computer)
			{	
				cout<<"\n\t  Computer Wins !!\n\n";
			}
			else
			{
				cout<<"\n\t  Match Draw !!\n\n";
			}
		}	
	private:
		void display()
		{
        		cout<<"\n\t *****************\n";
			cout<<"\t    TIC TAC TOE";
        		cout<<"\n\t *****************\n";

			int iter=1;
        		cout<<"\n\t -----------------\n";
        		for(int i=0;i<getRow();i++)
        		{
                		cout<<"\t|";
                		for(int j=0;j<getCol();j++)
                		{
					if(board[i][j]==CROSS)
                        			cout<<"  X"<<"  |";
					else if(board[i][j]==CIRCLE)
                        			cout<<"  @"<<"  |";
					else
                        			cout<<"  "<<iter<<"  |";

					iter++;
                		}

                		cout<<"\n\t -----------------\n";
        		}	
		}

		int calculateScore()
		{
			int Totalscore=0;

			Totalscore+=helperCalc(1); // for calculating row score
			Totalscore+=helperCalc(0); // for calculating col score
			int comp=0,hum=0;

			for(int i=0;i<getCol();i++)
			{
				if(board[i][i]==human)
					hum++;
				else if(board[i][i]==computer)
					comp++;
	
			}

			Totalscore+=eval(hum,comp);
			comp=0;
			hum=0;

			for(int i=getCol()-1,j=0;i>=0;i--,j++)
			{
				if(board[j][i]==human)
					hum++;
				else if(board[j][i]==computer)
					comp++;
			}

			Totalscore+=eval(hum,comp);

			return Totalscore;
		}
		int eval(int hum,int comp)
		{
			if(hum==0 && comp > 0)
			{
				if(comp==1)
					return 1;
				else if(comp==2)
					return 10;
				else	
					return 100;
			}
			else if(comp==0 && hum > 0)
			{
				if(hum==1)
					return -1;
				else if(hum==2)
					return -10;
				else
					return -100;
				}
		  return 0;
		}
		int helperCalc(int flag)
		{
			int Totalscore=0,r,c;

			if(flag)
			{
				r=getRow();
				c=getCol();
			}
			else
			{
				r=getCol();
				c=getRow();
			}

			for(int i=0;i<r;i++)
			{
				int comp=0,hum=0;

				for(int j=0;j<c;j++)
				{
					if(flag)
					{
						if(board[i][j]==human)
							hum++;
						else if(board[i][j]==computer)
							comp++;
					}
					else
					{
						if(board[j][i]==human)
							hum++;
						else if(board[j][i]==computer)
							comp++;
					}
				}
						
				Totalscore+=eval(hum,comp);
			}

			return Totalscore;
		}
		position minMax(int level,player p,int alpha,int beta)
		{
			int bestrow=-1;
			int bestcol=-1;
			position currScore;

			vector<position> vec;
			findEmptyCells(vec);
			if(level==0 || (vec.size()==0))
			{
				currScore.score=calculateScore();
				currScore.rowIdx=-1;
				currScore.colIdx=-1;
				return currScore;
			}
			else
			{
				for (vector<position>::iterator it = vec.begin() ; it != vec.end(); ++it)
				{
					board[it->rowIdx][it->colIdx]=p;
					if(p==computer)
					{
						currScore=minMax(level-1,human,alpha,beta);
						
						if(currScore.score > alpha)
						{
							alpha=currScore.score;
							bestrow=it->rowIdx;
							bestcol=it->colIdx;
						}
					}
					else
					{
					
						currScore=minMax(level-1,computer,alpha,beta);
					
						if(currScore.score < beta)
						{
							beta=currScore.score;
							bestrow=it->rowIdx;
							//bestcol=currScore.colIdx;
							
							bestcol=it->colIdx;
						}
					}
					
					board[it->rowIdx][it->colIdx]=EMPTY;
					
					if(alpha >= beta)
						break;
			
				}
			}
			
			currScore.score= (p==computer) ? alpha : beta;
			currScore.rowIdx=bestrow;
			currScore.colIdx=bestcol;
			
			return currScore;
		}
		
		
		void findEmptyCells(vector<position> &vec)
		{
			if(isGameOver(0))
				return;

			for(int i=0;i<getRow();i++)
			{
				for(int j=0;j<getCol();j++)
				{
					if(board[i][j]==EMPTY)
					{
						position p;
						p.rowIdx=i;
						p.colIdx=j;
						vec.push_back(p);
					}
				}
			}		
		}

		bool checkPattern(player sign)
		{
			int cntr=0;
			int r,c;
			
			r=getRow();
			c=getCol();

			int checkFlg=1;

			for(int k=0;k<2;k++)
			{
				for(int i=0;i<r;i++)
				{
					cntr=0;
					for(int j=0;j<c;j++)
					{
						if(checkFlg)
						{	
							if(board[i][j]==sign)
							{		
								cntr++;
							}
							else
							{
								break;
							}
						}
						else
						{
							if(board[j][i]==sign)
                                                        {
                                                                cntr++;
                                                        }
                                                        else
                                                        {
                                                                break;
                                                        }

						}
					}
					if(cntr==3)
						return true;
				}
				if(r!=c)
				{
					int temp=r;
					r=c;
					c=temp;
				}
				checkFlg=0;
				cntr=0;
			}
			cntr=0;
			for(int i=0;i<getCol();i++)
                        {
                                if(board[i][i]==sign)
                                        cntr++;
                        }
			if(cntr==3)
				return true;

			cntr=0;

			for(int i=getCol()-1,j=0;i>=0;i--,j++)
                        {
                                if(board[j][i]==sign)
                                        cntr++;
                        }
			if(cntr==3)
				return true;
		
			return false;	
		}
		bool isGameOver(int checkFlg)
		{
			if(checkPattern(human))
			{
				if(checkFlg)
					win=human;

				return true;
			}
			else if(checkPattern(computer))
			{
				if(checkFlg)
					win=computer;

				return true;
			}

			return false;
		}
};

int main()
{

TicTacToe *play=new AIGame();
//player human=CROSS;
play->start(CROSS);
cout<<"\n";
return 1;
}