ym.cpp

用人工智能的αβ剪枝算法实现,界面整洁漂亮,人机各为一方,三子连成一线即赢

#include<stdio.h>
#include<string.h>
#include<iostream.h>
const int maxwin=32767;
const int minwin=-32767;
const int MAX=3;
const int dep=2;
struct node{
	int value,father,floor,son;
	char pf[MAX][MAX];
};
class chess{
public:  
    node queue[10000];
    int sign[10000],pai,p,q,ppp;
	void init();
	void print(char temp[3][3]);
	int equal(char a[MAX][MAX],char b[MAX][MAX]);
	int GetAllMoves(node f,int p,int &bit);
    int che(char f[MAX][MAX],int x,char ch);
    int check(char f[MAX][MAX]);
    int fun(char f[MAX][MAX]);
	int maxnum(int a,int b);
	int minnum(int a,int b);
	int max(int depth,node f,int vf_min);
    int min(int depth,node f,int vf_max);
	int work(char sump[3][3],int &x,int &y);
};
void chess::print(char temp[3][3]){//打印结点的状态
	printf("state is:\n");
	printf("+-+-+-+\n");
	for (int i=0;i<MAX;i++){
		for (int j=0;j<MAX;j++){
			if(temp[i][j]=='c')printf("| ");
			else printf("|%c",temp[i][j]);
		}
		printf("|\n+-+-+-+\n");
	}
	return;
}
int chess::che(char f[MAX][MAX],int x,char ch){//判断f[i][j]为最上方的连续三个格子是否都为ch
	if (x==0) 
		if (f[0][0]==ch && f[0][1]==ch && f[0][2]==ch) return 1;
	if (x==1)
		if (f[1][0]==ch && f[1][1]==ch && f[1][2]==ch) return 1;
	if (x==2)
		if (f[2][0]==ch && f[2][1]==ch && f[2][2]==ch) return 1;
	if (x==3)
		if (f[0][0]==ch && f[1][0]==ch && f[2][0]==ch) return 1;
	if (x==4)
		if (f[0][1]==ch && f[1][1]==ch && f[2][1]==ch) return 1;
	if (x==5)
		if (f[0][2]==ch && f[1][2]==ch && f[2][2]==ch) return 1;
	if (x==6)
		if (f[0][0]==ch && f[1][1]==ch && f[2][2]==ch) return 1;
	if (x==7)
		if (f[0][2]==ch && f[1][1]==ch && f[2][0]==ch) return 1;
	return 0;
} 
int chess::check(char f[MAX][MAX]){
	for (int k=0;k<8;k++)
	    if (che(f,k,'x')==1) return maxwin;
		else if (che(f,k,'o')==1)return minwin;
	return 0;
}
int chess::fun(char f[MAX][MAX]){//计算估价值
	int a=0,i,j,k;
	for (k=0;k<8;k++)
	if (che(f,k,'x')==1) return maxwin;
	else if (che(f,k,'o')==1)return minwin;//返回P必胜或必败时的值
	k=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (f[i][j]=='c') k++;
	if (k==0) return 0;//和局
	int t1=0,t2=0,t3=0,onea=0,oneb=0,twoa=0,twob=0;
	for (k=0;k<3;k++){
	t1=0;t2=0;t3=0;
	for (i=0;i<3;i++){		
		if (f[i][k]=='c') t1++;
		   else if (f[i][k]=='x') t2++;
		       else t3++;
	}
    if (t2==1 && t3==0) onea++;
	if (t3==1 && t2==0) oneb++;
	if (t2==2 && t3==0) twoa++;
	if (t3==2 && t2==0) twob++;
	if (t2==1 && t3==2) a=2;
	if (t3==1 && t2==2) a=-2;
	}//纵
	for (k=0;k<3;k++){
		t1=0;t2=0;t3=0;
	for (i=0;i<3;i++){		
		if (f[k][i]=='c') t1++;
		   else if (f[k][i]=='x') t2++;
		       else t3++;
    }
	if (t2==1 && t3==0) onea++;
	if (t3==1 && t2==0) oneb++;
	if (t2==2 && t3==0) twoa++;
	if (t3==2 && t2==0) twob++;
	if (t2==1 && t3==2) a=2;
	if (t3==1 && t2==2) a=-2;
	}//横
	t1=0;t2=0;t3=0;
	for (i=0;i<3;i++)
		if (f[i][i]=='c') t1++;
		   else if (f[i][i]=='x') t2++;
		      else t3++;
	if (t2==1 && t3==0) onea++;
	if (t3==1 && t2==0) oneb++;
	if (t2==2 && t3==0) twoa++;
	if (t3==2 && t2==0) twob++;
	if (t2==1 && t3==2) a=2;
	if (t3==1 && t2==2) a=-2;	
	t1=0;t2=0;t3=0;
	for (i=0;i<3;i++)
		if (f[i][3-i-1]=='c') t1++;
		   else if (f[i][3-i-1]=='x') t2++;
		      else t3++;
	if (t2==1 && t3==0) onea++;
	if (t3==1 && t2==0) oneb++;
	if (t2==2 && t3==0) twoa++;
	if (t3==2 && t2==0) twob++;
	if (t2==1 && t3==2) a=2;
	if (t3==1 && t2==2) a=-2;	
	return (onea-oneb)+4*(twoa-twob)+a;
}
void chess::init(){//初始化，队列置空后，放成c表示空格
	memset(queue,0,sizeof(queue));
	memset(sign,0,sizeof(sign));
	p=0;q=1;
	for (int i=0;i<10000;i++)
		queue[i].son=-1;
	queue[p].father=-1;//初始点没有父亲
	queue[p].floor=0;//初始点的层数为0
	queue[p].value=0;//初始点的值为0（因为刚开始时，局面对谁都是公平的）
	return;
}
int chess::equal(char a[MAX][MAX],char b[MAX][MAX]){//判断两个max*max的棋局是否为相同的，是则返回1，否则返回0
	int t=0;
	for (int i=0;i<MAX;i++)
		for (int j=0;j<MAX;j++)
			if (a[i][j]!=b[i][j]) t=1;
	if (t==0) return 1;
	return 0;
}
int chess::maxnum(int a,int b){
	if (a>b) return a;
	else return b;
}
int chess::minnum(int a,int b){
	if (a<b) return a;
	else return b;
}
int chess::GetAllMoves(node f,int p,int &bit){
	int s=0,w;
	for (int i=0;i<MAX;i++)
		for (int j=0;j<MAX;j++){//如果枚举的位置上有棋子了，那么不理它，继续下一个枚举
			if (f.pf[i][j]=='x' || f.pf[i][j]=='o')continue;
			node temp;
			temp=f;
			temp.father=p;
			temp.floor=f.floor+1;
			temp.value=fun(temp.pf);//如果层数为奇数的话，那么就是max下棋，标记就是X，否则就是O
			if (temp.floor%2==1) temp.pf[i][j]='x';
			else temp.pf[i][j]='o';
			int t=0;
			for (int k=0;k<q;k++)if (equal(queue[k].pf,temp.pf)==1) w=1;
			if (w==1) continue;//当生成的状态已经扩展过的时候，不理它，枚举下一个
			if (s==0) bit=q;
			queue[q++]=temp;
			s++;
		}
	return s;
}
int chess::min(int depth,node f,int vf_max){
	int i,j,kk=0;
	for (i=0;i<3;i++)
		for(j=0;j<3;j++)
			if (f.pf[i][j]=='c') kk++;
	if (depth<=0||kk==0|| fun(f.pf)==minwin)  {
		f.floor=dep-depth;
		f.value=fun(f.pf);
		for (int i=0;i<q;i++)
			if (equal(queue[i].pf,f.pf)==1) queue[i].value =f.value ;
		return f.value;
	}	
	int result=maxwin,x,nCount=GetAllMoves(f,p,x);
	f.son=x;
	for (i=0;i<nCount;i++){
		node temp=queue[x++];
		int t=max(depth-1,temp,result);
		result=minnum(result,t);
		if (result<vf_max) break;//此处进行剪枝操作，当该节点扩展的节点的value值小于其前的max走步值时进行剪枝
	}
	f.floor=dep-depth;
	f.value=result;
	for (i=0;i<q;i++)if (equal(f.pf,queue[i].pf)==1) queue[i]=f;
	return result;
}
int chess::max(int depth,node f,int vf_min){
	int i,kk=0;
	if (depth<=0|| fun(f.pf)==minwin) {
		f.floor =dep-depth;
		f.value=fun(f.pf);
		for (i=0;i<q;i++)
			if (equal(queue[i].pf,f.pf)) queue[i].value=f.value;
		return f.value;
	}
	int result=minwin,x,nCount=GetAllMoves(f,p,x);
	f.son=x;
	if (nCount==0) return 0;
	for (i=0;i<nCount;i++){
		node temp=queue[x++];
		int t=min(depth-1,temp,result);
		result=maxnum(result,t);
		if (result>vf_min)//此处进行剪枝操作，当该节点扩展的节点的value值大于其前的min走步值时进行剪枝
			break;
	}
	f.floor=dep-depth;
	f.value=result;
	for (i=0;i<q;i++)
		if (equal(f.pf,queue[i].pf)==1) queue[i]=f;
	return result;
}
int chess::work(char sump[3][3],int &x,int &y){
	init();
	int sign1,i,j,kk,ppp=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++){
			queue[p].pf[i][j]=sump[i][j];
		    if (queue[p].pf[i][j]!='c')ppp++;
		}
	if(check(queue[p].pf)==-32767){
			 printf("You win!\n");return 1;
	}
	kk=0;
	for (i=0;i<3;i++)
		for (j=0;j<3;j++)
			if (queue[p].pf[i][j]=='c')kk++;
	 if(kk==0){
		 printf("It is a draw!\n"); return 1;
		 }
	max(dep,queue[0],maxwin);
    j=1;int pi=j;
   	while (j<q && queue[j].floor==1){
		if (queue[j].value==queue[0].value) {
			pi=j;break;
		}
		j++;
	}
	sign1=0;
    for (i=0;i<MAX&&sign1==0;i++)
	    for (j=0;j<MAX;j++){
	        if (queue[pi].pf[i][j]!=sump[i][j]){
					x=i;y=j;sign1=1;break;
				}
			}
	if(check(queue[pi].pf)==32767){
		printf("The computer win!\n");return 1;
		 }
	 kk=0;
	 for (i=0;i<3;i++)
	     for (j=0;j<3;j++)
		      if (queue[pi].pf[i][j]=='c')kk++;
	 if(kk==0){
		 printf("It is a draw!\n"); return 1;
	 }
     return 0;
}
int main(){
	chess onech;
	int i,j,k,g,x,y;
	char sign='y',temp[3][3];
	while(sign=='y'){		
		printf("请初始化你的棋盘:(如果让机器先下请将棋盘全置为c，否则请将你的棋子用o表示，其余用c表示)\n");
	    int ppp=0;
	    for (i=0;i<MAX;i++)
	 	     for (j=0;j<MAX;j++)
			   scanf("%c",&temp[i][j]);
		while(1){
			onech.pai=0;
		    if(onech.work(temp,x,y)==1)break;
			temp[x][y]='x';
			onech.print(temp);
            printf("请输入你要放棋子的位置(从0开始计数，按 行 列 形式给出)\n");
			scanf("%d %d",&k,&g);
			temp[k][g]='o';
		}
		printf("Do you want to try again!(y\\n)\n");
        cin>>sign;
	}
	return 0;
}