#include <iostream>/*Author: capn_midnightDate: 11/10/04*/using namespace std;//Important IDs and Constants//Each one is specifically chosen for complimentary features//	AI=-PL, PL=-AI, PL!=EMPTY, AI!=EMPTY//  A completion evaluates |3|//  A near completion evaluates to |2|//  Lines are evaluated by summation of the values in that line//  Lines that evaluate to |1| or |0| or not important,//     they are either empty, have only one token, have//     two opposing tokens, or two opposing tokens + 1 token.//     Neither of these cases help us to choose a winning move.const int AI=-1;const int EMPTY=0;const int PL=1;//  Wins and Losses for a branch point are averaged to give the//     branch point an aggregate value. The branch with the highest//     aggregate value will be chosen. This favors branches with the//     most wins, fewest losses, and fewest branches (which will also//     mean shortest tree depth). Shortest tree depth is desirable//     because long trees usually lead to full boards, and full boards//     usually lead to ties, not wins.const int WIN=1;const int TIE=0;const int LOSS=-1;//  Since a player's move is represented by a number, a token//     must be associated with that value.char AI_TOK='O';char PL_TOK='X';//  All calculations generally return values between -3 and 3, and mostly return//     positive values. Therefore, a very large negative number is special.const int NONE=-9999;//  The grid. We only need one, because we are using the recursion stack instead//     of writing a stack.int grid[9];//What do you think it is?void initGrid(){	for(int i=0;i<9;i++)		grid=0;}//2D grid coordinates to 1D array indexint xy_i(int x, int y){	return y*3+x;}//Rows run horizontally, increasing down the y axisint findEmptyInRow(int y){	for(int x=0;x<3;x++){		int i=xy_i(x,y);		if(grid==EMPTY)			return i;	}	return NONE;}//Cols run vertically, increasing right of the x axisint findEmptyInCol(int x){	for(int y=0;y<3;y++){		int i=xy_i(x,y);		if(grid==EMPTY)			return i;	}	return NONE;}//Diagonals are annoying, but they can be handledint findEmptyInDiag(int d){	for(int v=0;v<3;v++){		int i;		if(d==0)			i=xy_i(v, v);		else			i=xy_i(v, 2-v);		cout<<d<<" "<<i<<endl;		if(grid==EMPTY)			return i;	}	return NONE;}//looks for a line that evaluates to +-2, and then finds the blank spot in it.//Lines that do evaluate to +-2 will definitely have an open space.//Proof:// ___ : 0// X_O : 0// X__ : 1// XXO : 1// XX_ : 2// XXX : 3// So, the only time where adding a piece in the ONLY blank spot is when the// line evaluates to 2int findWinFor(int side){	int dt1=0;	int dt2=0;	for(int y=0;y<3;y++){		int rt=0;		int ct=0;		for(int x=0;x<3;x++){			int ri=xy_i(x,y);			int ci=xy_i(y,x);			rt+=grid[ri];			ct+=grid[ci];		}		if(rt/side==2)			return findEmptyInRow(y);		if(ct/side==2)			return findEmptyInCol(y);		int di1=xy_i(y,y);		int di2=xy_i(y,2-y);		dt1+=grid[di1];		dt2+=grid[di2];	}	if(dt1/side==2)		return findEmptyInDiag(0);	if(dt2/side==2)		return findEmptyInDiag(1);	return NONE;}//If your enemy has a win condition, then that should be your block conditionint findBlockFor(int side){	return findWinFor(side*-1);}//Evaluates all of the lines, trying to find a line that evaluates to |3|//if line_evaluation/side == -3, that means either it was a row of X's when// we were checking for O, or it was a row of O's when we were checking for// X (loss). if line_evaluations/side == 3, that means either it was a row of X's when// we were checking for X, or it was a row of O's when we were checking for// O (win). Any other case, we call a tie, and anything called a tie is only a tie// when the board is full.int boardState(int side){	int dt1=0;	int dt2=0;	for(int y=0;y<3;y++){		int rt=0;		int ct=0;		for(int x=0;x<3;x++){			int ri=xy_i(x,y);			int ci=xy_i(y,x);			rt+=grid[ri];			ct+=grid[ci];		}		if(rt/side==3)			return WIN;		else if(rt/side==-3)			return LOSS;		if(ct/side==3)			return WIN;		else if(ct/side==-3)			return LOSS;		int di1=xy_i(y,y);		int di2=xy_i(y,2-y);		dt1+=grid[di1];		dt2+=grid[di2];	}	if(dt1/side==3)		return WIN;	else if(dt1/side==-3)		return LOSS;	if(dt2/side==3)		return WIN;	else if(dt2/side==-3)		return LOSS;	return TIE;}//Finding the winner is just a matter of checking the board state// for a player. If the AI won, then it won, if the AI lost, then// the Player won. If neither of these are the case, then there// was no winner.int findWinner(){	int b=boardState(AI);	if(b==WIN) return AI;	if(b==LOSS) return PL;	return NONE;}//A useful little function. 0 means the board is full, 1 means there// is only one move left. Other values aren't important.int countBlanks(){	int t=0;	for(int i=0;i<9;i++) if(grid==EMPTY) t++;	return t;}//duhbool isFull(){	return countBlanks()==0;}//if there is more than one blanks spot, then there cannot be// a "last move" yet, so the function returns "NONE". If there is// only one blank spot, then returning the index of the first// blank found will return the index of the only blank found.int findLastMove(){	if(countBlanks()==1){		for(int i=0;i<9;i++) if(grid==EMPTY) return i;	}	return NONE;}//The workhorse function. It recursively calls itself.//  each board that is not an end state board (a win, a loss,//  or a full board tie) is a node in a greater tree of//  plays. Each node has a certain number of branches, as//  well as an aggregate value. The aggregate value of a branch//  is the arithmetic mean of the branches' aggregate values.//  Leaf nodes are end state boards, and have aggregate values//  equal to wether or not they are a win, lose, or tie.float calcValue(int side){	int n=0;	float t=0;	if(isFull() && findWinner()==NONE) return TIE;	if(findWinner()==AI) return WIN;	if(findWinner()==PL) return LOSS;	for(int i=0;i<9;i++){		if(grid==EMPTY){			grid=side;			n++;			t+=calcValue(-side);			grid=EMPTY;		}	}	return t/(float)n;}//The branch with the greatest aggregate value is the strongest//  branch, favoring the most wins, the least losses and the//  fewest branches. Fewer branches generally means a shorter tree.//  A long tree is undesirable because it leads to a full board,//  and full boards usually end in a tie.int getPlay(){	float max_val=-99999.0f;	int max_index=-1;	for(int a=0;a<9;a++){		if(grid[a]==EMPTY){			grid[a]=AI;			float val=calcValue(PL);			if(val>max_val){				max_val=val;				max_index=a;			}			grid[a]=EMPTY;		}	}	return max_index;}//I wonder what this does. I totally forget... :)void printBoard(){	for(int y=0;y<3;y++){		for(int x=0;x<3;x++){			int i=xy_i(x,y);			if(grid==EMPTY)   cout<<"-"<<i<<"-";			else if(grid==PL) cout<<" "<<PL_TOK<<" ";			else if(grid==AI) cout<<" "<<AI_TOK<<" ";			if(x<2) cout<<"|";		}		if(y<2) cout<<"\n---+---+---\n";	}	cout<<endl;}//gets the input from the user, and makes the play if it is a valid playvoid userPlay(){	int i=-1;	while(i<0 || i>8){		printBoard();		cout<<"Enter index of your move. (1-9) :>";		cin>>i;		if(grid!=EMPTY) i=-1;	}	grid=PL;}//runs the AI playint aiPlay(){	int i=findWinFor(AI);	if(i!=NONE){		grid=AI;		return i;	}	i=findBlockFor(AI);	if(i!=NONE){		grid=AI;		return i;	}	i=findLastMove();	if(i!=NONE){		grid=AI;		return i;	}	i=getPlay();	grid=AI;	return i;}//manages the turns, and game initialization.int main(){	bool done=false;	char c;	while(!done){		initGrid();		int ti=0;		int turn=0;		cout<<"Would you like to go first or second? (1/2) :>";		cin>>c;		if(c=='2') ti=1;		cout<<"Would you like to be X or O? (X/O) :>";		cin>>c;		if(c=='O' || c=='o'){			PL_TOK='O';			AI_TOK='X';		}		while(!isFull() && findWinner()==NONE){			if(turn%2==ti)				userPlay();			else				cout<<"AI Played at index "<<aiPlay()<<endl;			turn++;		}		if(findWinner()==PL)			cout<<"You Win!"<<endl;		else if(findWinner()==AI)			cout<<"You Lose!"<<endl;		else			cout<<"It's a tie!"<<endl;		cout<<"Would you like to play again? (Y/N) :>";		cin>>c;		if(c=='N' || c=='n') done=true;	}	cout<<"Good bye!"<<endl;	return 0;}

	/*	*-----*-----*-----*-----*	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	*-----*-----*-----*-----*	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	*-----*-----*-----*-----*	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	*-----*-----*-----*-----*	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	|     |     |     |     |	*-----*-----*-----*-----*		*/