#include
using?namespace?std;

int?num=0;?
int?pq;??????????????
int?tmpQP[3][3];?//表示棋盤數(shù)據(jù)的臨時數(shù)組，其中的元素0表示該格為空，
int?cur[3][3];?
????
const?int?depth=3;??//搜索樹的最大深度
???

void?Init（）??
{
?
?for（int?i=0;i<3;i++）
??for（int?j=0;j<3;j++）
??{
	?cur[i][j]=0;
??}
}

void?PrintQP（）??//打印當(dāng)棋盤格局的函數(shù)
{
?for（int?i=0;i<3;i++）
?{
??for（int?j=0;j<3;j++）
???cout<??cout<?}
}

int?CheckWin（）?//有人贏了嗎？返回0表示沒有人贏，返回-1表示人贏了，返回1表示計算機贏了
{
?for（int?i=0;i<3;i++）
?{
??if（cur[i][0]==1&&cur[i][1]==1&&cur[i][2]==1）return?1;
??if（cur[i][0]==-1&&cur[i][1]==-1&&cur[i][2]==-1）return?-1;
?}
?for（i=0;i<3;i++）
?{
??if（cur[0][i]==1&&cur[1][i]==1&&cur[2][i]==1）return?1;
??if（cur[0][i]==-1&&cur[1][i]==-1&&cur[2][i]==-1）return?-1;
?}
?if（（cur[0][0]==1&&cur[1][1]==1&&cur[2][2]==1）||（cur[2][0]==1&&cur[1][1]==1&&cur[0][2]==1））return?1;
?if（（cur[0][0]==-1&&cur[1][1]==-1&&cur[2][2]==-1）||（cur[2][0]==-1&&cur[1][1]==-1&&cur[0][2]==-1））return?-1;
??
?return?0;
}


int?value（）//評估函數(shù)
{
??p=0;
??q=0;
//將棋盤中的空格填滿自己的棋子，既將棋盤數(shù)組中的0變?yōu)?
?for（int?i=0;i<3;i++）
??for（int?j=0;j<3;j++）
???if（cur[i][j]==0）tmpQP[i][j]=1;
???else?tmpQP[i][j]=cur[i][j];
?
?//電腦一方
?//計算每一行中有多少行的棋子連成3個的
?for（i=0;i<3;i++）
??p+=（tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2]）/3;
?//計算每一列中有多少列的棋子連成3個的
?for（i=0;i<3;i++）
??p+=（tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i]）/3;
?//斜行有沒有連成3個的？
?p+=（tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2]）/3;
?p+=（tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2]）/3;
?
?//將棋盤中的空格填滿對方的棋子，既將棋盤數(shù)組中的0變?yōu)?1
?for（i=0;i<3;i++）
??for（int?j=0;j<3;j++）
???if（cur[i][j]==0）tmpQP[i][j]=-1;
???else?tmpQP[i][j]=cur[i][j];

?//對方
?//計算每一行中有多少行的棋子連成3個的
?for（i=0;i<3;i++）
??q+=（tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2]）/3;
?//計算每一列中有多少列的棋子連成3個的
?for（i=0;i<3;i++）
??q+=（tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i]）/3;
?//斜行有沒有連成3個的？
?q+=（tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2]）/3;
?q+=（tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2]）/3;
?
?return?p+q;
}


int?cut（int?&valint?depbool?max）??//主算法部分，實現(xiàn)A－B剪枝的算法，val為上一層的評價值，dep為搜索深度，max記錄上一層是否為極大層
{
????if（dep==depth??||?dep+num==9）?????//如果搜索深度達到最大深度，或者深度加上當(dāng)前棋子數(shù)已經(jīng)達到9，就直接調(diào)用評價函數(shù)
????{
????????return?value（）;
????}
????int?ijflagtemp;
????????
????bool?out=false;????????????????//out記錄是否剪枝，初始為false
????????????????
????if（CheckWin（）==1）????????????//如果用戶玩家輸了，就置上一層的評價值為無窮（用很大的值代表無窮）
????{
????????val=10000;
????????return?0;
????}

????if（max）????????????????????//如果上一層是極大層，本曾則需要是極小層，記錄flag為無窮大；反之，則為記錄為負無窮大
????????flag=10000;????????????//flag記錄本層節(jié)點的極值
????else
????????flag=-10000;
????for（i=0;i<3?&&?!out;i++）??????//兩重循環(huán)，遍歷棋盤所有位置
????{
????????for（j=0;j<3?&&?!out;j++）
????????{
????????????if（cur[i][j]==0）?????//如果該位置上沒有棋子
????????????{
????????????????if（max）????????????????//并且為上一層為極大層，即本層為極小層輪到用戶玩家走了。
????????????????{
????????????????????cur[i][j]=-1;?????//該位置填上用戶玩家棋子
????????????????????????
????????????????????if（CheckWin（）==-1）????//如果用戶玩家贏了
????????????????????????temp=-10000;????//置棋盤評價值為負