类实现一字棋剪枝实现.cpp

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

#include<stdio.h>
#include<string.h>
#include<iostream.h>
const int maxwin=32767;
const int minwin=-32767;
const int MAX=3;
int pai;
struct node
{
	int value;
	int father;
	char pf[MAX][MAX];
	int floor;
	int son;
};
class chess
{
private:    
    int dep;
    int p,q,ppp;
    node queue[10000];
    int sign[10000];
public:
	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])
{
	int i,j;
	printf("state is:\n");
	printf("+-+-+-+\n");
	for (i=0;i<MAX;i++)
	{
		for (j=0;j<MAX;j++)
		{
			if(temp[i][j]=='c')printf("| ");
			else printf("|%c",temp[i][j]);
		}
		printf("|\n+-+-+-+\n");
	}
	//printf("Its value is %d,its floor is %d\n",f.value,f.floor);
	return;
}
//打印结点的状态

int chess::che(char f[MAX][MAX],int x,char 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;
} 
//判断f[i][j]为最上方的连续三个格子是否都为ch
int chess::check(char f[MAX][MAX])
{
	int k;
	for (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 i,j,k,maxf,minf;
	for (k=0;k<8;k++)
	if (che(f,k,'x')==1) return maxwin;
	else if (che(f,k,'o')==1)return minwin;
	//返回P必胜或必败时的值
	int result=0;
	for (i=0;i<3;i++)
	{	
		if (f[i][0]!='c' && f[i][1]!='c' && f[i][2]!='c' &&(f[i][0]=='x'||f[i][1]=='x'||f[i][2]=='x'))
			return 100;
		if (f[0][i]!='c' && f[1][i]!='c' && f[2][i]!='c' &&(f[0][i]=='x'||f[1][i]=='x'||f[2][i]=='x'))
			return 100;
	}
	if (f[0][0]!='c' && f[1][1]!='c' && f[2][2]!='c' &&(f[0][0]=='x'||f[1][1]=='x'||f[2][2]=='x'))
		return  100;			
	if (f[0][2]!='c' && f[1][1]!='c' && f[2][0]!='c' &&(f[0][2]=='x'||f[1][1]=='x'||f[2][0]=='x'))
		return 100;	
	for (i=0;i<3;i++)
	{
		if (f[i][0]!='c' && f[i][1]!='c' && f[i][2]!='c' &&(f[i][0]=='o'||f[i][1]=='o'||f[i][2]=='o'))
			return -100;
		if (f[0][i]!='c' && f[1][i]!='c' && f[2][i]!='c' &&(f[0][i]=='o'||f[1][i]=='o'||f[2][i]=='o'))
			return -100;
	}
	if (f[0][0]!='c' && f[1][1]!='c' && f[2][2]!='c' &&(f[0][0]=='o'||f[1][1]=='o'||f[2][2]=='o'))
		return -100;			
	if (f[0][2]!='c' && f[1][1]!='c' && f[2][0]!='c' &&(f[0][2]=='o'||f[1][1]=='o'||f[2][0]=='o'))
		return -100;
//防将军
	char temp[MAX][MAX];
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			temp[i][j]=f[i][j];
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (temp[i][j]!='x'&& temp[i][j]!='o') temp[i][j]='x';
	maxf=0;
	for (k=0;k<8;k++)
			if (che(temp,k,'x')==1) maxf++;
	
	//无法必胜或必败时，空格全是x时，max有多少种胜法
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			temp[i][j]=f[i][j];
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (temp[i][j]!='x'&& temp[i][j]!='o') temp[i][j]='o';
	minf=0;
	for (k=0;k<8;k++)
			if (che(temp,k,'o')==1) minf++;
	//无法必胜或必败时，空格全是o时，min有多少种胜法
	return maxf-minf;
}


void chess::init()
{
	memset(queue,0,sizeof(queue));
	memset(sign,0,sizeof(sign));
	p=0;q=1;
	int i;
	for (i=0;i<10000;i++)
		queue[i].son=-1;
	queue[p].father=-1;//初始点没有父亲
	queue[p].floor=0;//初始点的层数为0
	queue[p].value=0;//初始点的值为0（因为刚开始时，局面对谁都是公平的）
	return;
}

//初始化，队列置空后，放成c表示空格
int chess::equal(char a[MAX][MAX],char b[MAX][MAX])
{
	int i,j,t;
	t=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (a[i][j]!=b[i][j]) t=1;
	if (t==0) return 1;
//是否相同
	t=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (a[i][j]!=b[i][MAX-j-1]) t=1;
	if (t==0) return 1;
//是否关于y轴方向轴对称
	t=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (a[i][j]!=b[MAX-i-1][j]) t=1;
	if (t==0) return 1;
//是否关于x轴方向轴对称
	t=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (a[i][j]!=b[MAX-j-1][MAX-i-1]) t=1;
	if (t==0) return 1;
//是否关于y=x方向轴对称
	t=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
			if (a[i][j]!=b[j][i]) t=1;
	if (t==0) return 1;
//是否关于y=-x方向轴对称
	return 0;
//都不是，才相等；
}
//判断两个max*max的棋局是否为相同的，是则返回1，否则返回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,i,j;
	for (i=0;i<MAX;i++)
		for (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 (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)==maxwin || fun(f.pf)==minwin)    //此处与max不同
	{
		f.floor=dep-depth;
		f.value=fun(f.pf);
		for (i=0;i<q;i++)
			if (equal(queue[i].pf,f.pf)==1) queue[i].value =f.value ;
//		print(f);
		return f.value;
	}	
	int result=maxwin,x;
	int 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;
 //	print(f);
	return result;
}
int chess::max(int depth,node f,int vf_min)
{
	int i,kk=0;
	if (depth<=0)
	//	||kk==0 ||fun(f.pf)==maxwin || 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;
//		print(f);
		return f.value;
	}
	int result=minwin,x;
	int 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;
//	print(f);
	return result;
}


/*int chess::work()
{
	int i,j,g,k,pai=0,kk;
	char temp[MAX][MAX];
	init();
	printf("请初始化你的棋盘:(如果让机器先下请将棋盘全置为c，否则请将你的棋子用o表示，其余用c表示)\n");
	int ppp=0;
	for (i=0;i<MAX;i++)
		for (j=0;j<MAX;j++)
		{
			cin>>queue[p].pf[i][j];
		    if (queue[p].pf[i][j]!='c')ppp++;
		}
	if(ppp==0)pai=4;
	while(check(queue[0].pf)==0)
	{
		int pp=0;
		if (ppp!=0)
		{
			dep=2;
			if (pai==1)
			{
				dep=4;
			    printf("%d\n",max(dep,queue[0],maxwin));
			}
			else 
				printf("%d\n",max(dep,queue[0],maxwin));
		}
		else
		{
			dep=2;
			if (pai==1)
			{
				dep=3;
			    printf("%d\n",max(dep,queue[0],maxwin));
			}
			else 
			printf("%d\n",max(dep,queue[0],maxwin));
		}
		pai++;
	    printf("-------------------------------------------------\n");
	    j=1;int pi=j;
	   	while (j<q && queue[j].floor==1)
		{
			if (queue[j].value==queue[0].value) 
			{
				pi=j;
				break;
			}
			j++;
		}
		 print(queue[pi]);
		 for(k=0;k<3;k++)
			 for(g=0;g<3;g++)
				 temp[k][g]=queue[pi].pf[k][g]; 
		 if(check(queue[pi].pf)==32767)
		 {
			 printf("The computer win!\n");
			 return 0;
		 }
		 else if(check(queue[pi].pf)==-32767)
		 {
			 printf("You win!\n");
			 return 0;
		 }
		 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 0;
		 }
		 init();
	     for (k=0;k<MAX;k++)
			 for (g=0;g<MAX;g++)
			     queue[p].pf[k][g]=temp[k][g];
		 
		 while(1)
		 {
			 printf("请输入你要放棋子的位置(从0开始计数，按 行 列 形式给出)\n");
			 cin>>k>>g;
			 if(k>2||k<0||g>2||g<0)
				 printf("The expression is illegal!Try again!\n"); 
		     else if(queue[p].pf[k][g]=='c')
			 {
				 queue[p].pf[k][g]='o';
				 break;
			 }
			 else printf("There already have a chess! Try again!\n");
		 }
		
		 if (check(queue[p].pf)==-32767)
		 {
			 print(queue[pi]);
			 printf("You win!\n");
			 return 0;
		 }
		 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)
		 {
			 print(queue[p]);
			 printf("It is a draw!\n");
			 return 0;
		 }
	}
	return 0;
}*/
int chess::work(char sump[3][3],int &x,int &y)
{
	init();
	int sign1;
	int i,j,kk;
	//printf("请初始化你的棋盘:(如果让机器先下请将棋盘全置为c，否则请将你的棋子用o表示，其余用c表示)\n");
	int 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(ppp==0)pai=4;
	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;
		 }
	
		if (ppp!=0)
		{
			dep=2;
			if (pai==1)
			{
				dep=4;
			    max(dep,queue[0],maxwin);
			}
			else 
				max(dep,queue[0],maxwin);
		}
		else
		{
			dep=2;
			if (pai==1)
			{
				dep=3;
			    max(dep,queue[0],maxwin);
			}
			else max(dep,queue[0],maxwin);
		}
		pai++;
	   // printf("-------------------------------------------------\n");
	    j=1;int pi=j;
	   	while (j<q && queue[j].floor==1)
		{
			if (queue[j].value==queue[0].value) 
			{
				pi=j;
				break;
			}
			j++;
		}
	    //print(queue[pi].pf);
		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;
	int k,g;
	int x,y;
	char sign='y';
	char temp[3][3];
	while(sign=='y')
	{
		pai=0;
		printf("请初始化你的棋盘:(如果让机器先下请将棋盘全置为c，否则请将你的棋子用o表示，其余用c表示)\n");
	    int ppp=0;
	    for (i=0;i<MAX;i++)
	 	     for (j=0;j<MAX;j++)
			   cin>>temp[i][j];
		while(1)
		{
		    if(onech.work(temp,x,y)==1)break;
			temp[x][y]='x';
			onech.print(temp);
            printf("请输入你要放棋子的位置(从0开始计数，按 行 列 形式给出)\n");
			cin>>k>>g;
			temp[k][g]='o';
		}
		printf("Do you want to try again!(y\\n)\n");
        cin>>sign;
	}
	return 0;
}