#include<iostream>
using namespace std;
int tmpQP[3][3]; //表示棋盘数据的临时数组，其中的元素0表示该格为空，1表示计算机放下的子，-1表示人放下的子。
const int MAX_NUM=1000; //扩展生成状态节点的最大数目
const int NO_BLANK=-1001; //表示没有空格
const int TREE_DEPTH=2; //搜索树的最大深度，如果增加此值可以提高计算机的“智力”，
const int NIL=1001; //表示空
static int s_count; //用来表示当前分析的节点的下标
struct State//该结构表示棋盘的某个状态，也可看做搜索树中的一个节点
{
int QP[3][3]; //棋盘格局
int e_fun; //当前状态的评估函数值
int child[9]; //儿女节点的下标
int parent; //双亲节点的下标
int bestChild; //最优节点（评估函数值最大）的儿女节点下标
}States[MAX_NUM]; //用来保存搜索树中状态节点的数组
void Init() //初始化函数，当前的棋盘格局总是保存在States[0]中
{
s_count=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
States[0].QP[i][j]=0;
States[0].parent=NIL;
}
void PrintQP() //打印当棋盘格局的函数
{
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
cout<<'\t'<<States[0].QP[i][j]<<'\t';
cout<<endl;
}
}
int IsWin(State s) //有人赢了吗？返回0表示没有人赢，返回-1表示人赢了，返回1表示计算机赢了
{
for(int i=0;i<3;i++)
{
if(s.QP[i][0]==1&&s.QP[i][1]==1&&s.QP[i][2]==1)return 1;
if(s.QP[i][0]==-1&&s.QP[i][1]==-1&&s.QP[i][2]==-1)return -1;
}
for(i=0;i<3;i++)
{
if(s.QP[0][i]==1&&s.QP[1][i]==1&&s.QP[2][i]==1)return 1;
if(s.QP[0][i]==-1&&s.QP[1][i]==-1&&s.QP[2][i]==-1)return -1;
}
if((s.QP[0][0]==1&&s.QP[1][1]==1&&s.QP[2][2]==1)||(s.QP[2][0]==1&&s.QP[1][1]==1&&s.QP[0][2]==1))return 1;
if((s.QP[0][0]==-1&&s.QP[1][1]==-1&&s.QP[2][2]==-1)||(s.QP[2][0]==-1&&s.QP[1][1]==-1&&s.QP[0][2]==-1))return -1;
return 0;
}
int e_fun(State s)//评估函数
{
bool flag=true;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(s.QP[i][j]==0)flag=false;
if(flag)return NO_BLANK;
if(IsWin(s)==-1)return -MAX_NUM;
if(IsWin(s)==1)return MAX_NUM;
int count=0;
//将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
if(s.QP[i][j]==0)tmpQP[i][j]=1;
else tmpQP[i][j]=s.QP[i][j];
//电脑一方
//计算每一行中有多少行的棋子连成3个的
for(i=0;i<3;i++)
count+=(tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2])/3;
//计算每一列中有多少列的棋子连成3个的
for(i=0;i<3;i++)
count+=(tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i])/3;
//斜行有没有连成3个的？
count+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2])/3;
count+=(tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2])/3;
//将棋盘中的空格填满对方的棋子，既将棋盘数组中的0变为-1
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
if(s.QP[i][j]==0)tmpQP[i][j]=-1;
else tmpQP[i][j]=s.QP[i][j];
//对方
//计算每一行中有多少行的棋子连成3个的
for(i=0;i<3;i++)
count+=(tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2])/3;
//计算每一列中有多少列的棋子连成3个的
for(i=0;i<3;i++)
count+=(tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i])/3;
//斜行有没有连成3个的？
count+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2])/3;
count+=(tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2])/3;
return count;
}
//计算机通过该函数决定走哪一步，并对当前的棋局做出判断。
bool AutoDone()
{
cout<<"\t The QP now is:"<<endl;
PrintQP();
int
MAX_F=NO_BLANK,
parent=-1,
count,
i,
tag;
bool
max_min=TREE_DEPTH%2,
IsOK=false;
s_count=0;
if(IsWin(States[0])==-1)//如果人赢了
{
cout<<"\t Conguatulations! You Win! GAME OVER."<<endl;
return true;
}
for(int t=0;t<TREE_DEPTH;t++)
{
count=s_count;
for(int k=parent+1;k<=count;k++)
{
int n_child=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(States[k].QP[i][j]==0)
{
s_count++;
for(int i1=0;i1<3;i1++)
for(int j1=0;j1<3;j1++)
States[s_count].QP[i1][j1]=States[k].QP[i1][j1];
States[s_count].QP[i][j]=t%2==0?1:-1;
States[s_count].parent=k;
States[k].child[n_child++]=s_count;
if(t==0&&e_fun(States[s_count])==MAX_NUM)
{
States[k].e_fun=MAX_NUM;
States[k].bestChild=s_count;
goto L2;
}
}
}
parent=count;
cout<<s_count<<endl;
}
tag=States[s_count].parent;
int pos_x,pos_y;
for(i=0;i<=s_count;i++)
{
if(i>tag)
{
States[i].e_fun=e_fun(States[i]);
}
else
States[i].e_fun=NIL;
}
while(!IsOK)
{
for(int i=s_count;i>tag;i--)
{
if(max_min)
{
if(States[States[i].parent].e_fun<States[i].e_fun||States[States[i].parent].e_fun==NIL)
{
States[States[i].parent].e_fun=States[i].e_fun;
States[States[i].parent].bestChild=i;
}
}
else
{
if(States[States[i].parent].e_fun>States[i].e_fun||States[States[i].parent].e_fun==NIL)
{
States[States[i].parent].e_fun=States[i].e_fun;
States[States[i].parent].bestChild=i;
}
}
}
s_count=tag;
max_min=!max_min;
if(States[s_count].parent!=NIL)
tag=States[s_count].parent;
else
IsOK=true;
}
L2: //取落子的位置，将x,y坐标保存在变量pos_x和pos_y中，并将根（当前）节点中的棋局设为最佳儿子节点的棋局
for(int x=0;x<3;x++)
{
for(int y=0;y<3;y++)
{
if(States[States[0].bestChild].QP[x][y]!=States[0].QP[x][y])
{
pos_x=x;
pos_y=y;
}
States[0].QP[x][y]=States[States[0].bestChild].QP[x][y];
}
}
MAX_F=States[0].e_fun;
cout<<"\t The computer put a qizi at: "<<pos_x+1<<','<<pos_y+1<<'\n'<<"\t The QP now is:"<<endl;
PrintQP();
if(MAX_F==MAX_NUM)
{
cout<<"\t The computer WIN! You LOSE! GAME OVER."<<endl;
return true;
}
if(MAX_F==NO_BLANK)
{
cout<<"DRAW GAME!"<<endl;
return true;
}
return false;
}
//计算机通过该函数决定走哪一步，并对当前的棋局做出判断。
bool AutoDone1()
{
int
MAX_F=NO_BLANK,
parent=-1,
count,
i,
tag;
bool
max_min=TREE_DEPTH%2,
IsOK=false;
s_count=0;
if(IsWin(States[0])==-1)
{
cout<<"\t Conguatulations! computer-1 Win! GAME OVER."<<endl;
return true;
}
for(int t=0;t<TREE_DEPTH;t++)
{
count=s_count;
for(int k=parent+1;k<=count;k++)
{
int n_child=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(States[k].QP[i][j]==0)
{
s_count++;
for(int i1=0;i1<3;i1++)
for(int j1=0;j1<3;j1++)
States[s_count].QP[i1][j1]=States[k].QP[i1][j1];
States[s_count].QP[i][j]=t%2==0?-1:1;//根据是computer-1下还是computer1下，在空位上落子
States[s_count].parent=k;
States[k].child[n_child++]=s_count;
if(t==0&&e_fun(States[s_count])==MAX_NUM)
{
States[k].e_fun=MAX_NUM;
States[k].bestChild=s_count;
goto L2;
}
}
}
parent=count;
cout<<s_count<<endl;
}
tag=States[s_count].parent;
int pos_x,pos_y;
for(i=0;i<=s_count;i++)
{
if(i>tag)
{
States[i].e_fun=e_fun(States[i]);
}
else
States[i].e_fun=NIL;
}
while(!IsOK)
{
for(int i=s_count;i>tag;i--)
{
if(!max_min)
{
if(States[States[i].parent].e_fun<States[i].e_fun||States[States[i].parent].e_fun==NIL)
{
States[States[i].parent].e_fun=States[i].e_fun;
States[States[i].parent].bestChild=i;
}
}
else
{
if(States[States[i].parent].e_fun>States[i].e_fun||States[States[i].parent].e_fun==NIL)
{
States[States[i].parent].e_fun=States[i].e_fun;
States[States[i].parent].bestChild=i;
}
}
}
s_count=tag;
max_min=!max_min;
if(States[s_count].parent!=NIL)
tag=States[s_count].parent;
else
IsOK=true;
}
L2: //取落子的位置，将x,y坐标保存在变量pos_x和pos_y中，并将根（当前）节点中的棋局设为最佳儿子节点的棋局
for(int x=0;x<3;x++)
{
for(int y=0;y<3;y++)
{
if(States[States[0].bestChild].QP[x][y]!=States[0].QP[x][y])
{
pos_x=x;
pos_y=y;
}
States[0].QP[x][y]=States[States[0].bestChild].QP[x][y];
}
}
MAX_F=States[0].e_fun;
cout<<"\t The compu
