五子棋ai（优化版）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mapsize 225
#define maplen 15
#define dddd 4 
int map[mapsize];
typedef struct child* ch;
struct child{
	int*ls;
	ch next;
};
void print_map(int* data){
	int i,j;
	printf("\t 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 \n");
	printf("\t ———————————————\n");
	for(i=0;i<maplen;i++){
		printf("%d\t|",i); 
		for(j=0;j<maplen;j++){
			switch(data[i*maplen+j]){
				case 0:
					printf("  ");
					break;
				case 1:
					printf("X ");
					break;
				case -1:
					printf("O ");
					break ;
			}
		}
		printf("|"); 
		printf("\n");
	}
	printf("\t ———————————————\n");

}
ch getchild(int* data,int flag){
	ch ret=(ch)malloc(sizeof(struct child));
	ret->ls=(int*)malloc(sizeof(int)*mapsize);
	memset(ret->ls,0,sizeof(int)*mapsize);
	ret->next=NULL;
	int i,j;
	for(i=0;i<maplen;i++){
		for(j=0;j<maplen;j++){
			if(data[i*maplen+j]){
				if(i-1>=0&&j-1>=0) ret->ls[(i-1)*maplen+j-1]=!data[(i-1)*maplen+j-1];
				if(i-1>=0) ret->ls[(i-1)*maplen+j]=!data[(i-1)*maplen+j];
				if(i-1>=0&&j+1<maplen) ret->ls[(i-1)*maplen+j+1]=!data[(i-1)*maplen+j+1];
				if(j-1>=0) ret->ls[i*maplen+j-1]=!data[i*maplen+j-1];
				if(j+1<maplen) ret->ls[i*maplen+j+1]=!data[i*maplen+j+1];
				if(i+1<maplen&&j-1>=0) ret->ls[(i+1)*maplen+j-1]=!data[(i+1)*maplen+j-1];
				if(i+1<maplen) ret->ls[(i+1)*maplen+j]=!data[(i+1)*maplen+j];
				if(i+1<maplen&&j+1<maplen) ret->ls[(i+1)*maplen+j+1]=!data[(i+1)*maplen+j+1];
			}
		}
	}
	ch p=ret;
	for(i=0;i<mapsize;i++){
		if(ret->ls[i]){
			ch tmp=(ch)malloc(sizeof(struct child));
			tmp->ls=(int*)malloc(sizeof(int)*mapsize);
			tmp->next=NULL;
			memcpy(tmp->ls,data,sizeof(int)*mapsize);
			tmp->ls[i]=flag;
			p->next=tmp;
			p=p->next;
		}
	}
	return ret;
}
int getvalue(int *data,int flag){
	int i,j,k;
	int val[5]={0,0,0,0,0};
	for(i=0;i<2*maplen-1;i++){
		int len=0;
		int len1=0;
		for(j=0;j<((i+1)>maplen?(2*maplen-1-i):(i+1));j++){
			int x=(i+1)>maplen?(maplen-1):(i-j);
			int y=(i+1)>maplen?(i+1-maplen):j;
			if(data[x*maplen+y]==flag){
				len1++;
				if(x-1<0||y+1>=maplen||(data[(x-1)*maplen+y+1]!=flag)){
					switch(len1){
						case 2:{
							if(x+2<maplen&&y-2>=0&&x-1>=0&&y+1<maplen&&!data[(x+2)*maplen+y-2]&&!data[(x-1)*maplen+y+1]){
								val[3]++;
							}
							break;
						}
						case 3:{
							if((x+3<maplen&&y-3>=0&&!data[(x+3)*maplen+y-3])&&(x-1>=0&&y+1<maplen&&!data[(x-1)*maplen+y+1])){
								val[0]+=3;
							}
							if((x+3<maplen&&y-3>=0&&!data[(x+3)*maplen+y-3])&&(x+4<maplen&&y-4>=0&&!data[(x+4)*maplen+y-4])){
								val[0]++;
							}
							if((x-2>=0&&y+2<maplen&&!data[(x-2)*maplen+y+2])&&(x-1>=0&&y+1<maplen&&!data[(x-1)*maplen+y+1])){
								val[0]++;
							}
							break;
						}
						case 4:{
							if((x-1>=0&&y+1<maplen&&!data[(x-1)*maplen+y+1])){
								val[1]++;
							}
							if((x+4<maplen&&y-4>=0&&!data[(x+4)*maplen+y-4])){
								val[1]++;
							}
							break;
						}
						case 5:{
							val[2]++;						
							break;
						}
					}
				} 
				
			}else{
				len1=0;
			}
			x=(i+1)>maplen?j:maplen-1-i+j;
			y=(i+1)>maplen?(i+1-maplen+j):j; 
			if(data[x*maplen+y]==flag){
				len++;
				if(x+1>=maplen||y+1>=maplen||data[(x+1)*maplen+y+1]!=flag){
					switch(len){
						case 2:{
							if(x-2>=0&&y-2>=0&&x+1<maplen&&y+1<maplen&&!data[(x-2)*maplen+y-2]&&!data[(x+1)*maplen+y+1]){
								val[3]++;
							}
							break;
						}
						case 3:{
							if((x+1<maplen&&y+1<maplen&&!data[(x+1)*maplen+y+1])&&(x-3>=0&&y-3>=0&&!data[(x-3)*maplen+y-3])){
								val[0]+=3;
							}
							if((x+1<maplen&&y+1<maplen&&!data[(x+1)*maplen+y+1])&&(x+2<maplen&&y+2<maplen&&!data[(x+2)*maplen+y+2])){
								val[0]++;
							}
							if((x-4>=0&&y-4>=0&&!data[(x-4)*maplen+y-4])&&(x-3>=0&&y-3>=0&&!data[(x-3)*maplen+y-3])){
								val[0]++;
							}
							break;
						}
						case 4:{
							if((x+1<maplen&&y+1<maplen&&!data[(x+1)*maplen+y+1])){
								val[1]++;
							}
							if((x-4>=0&&y-4>=0&&!data[(x-4)*maplen+y-4])){
								val[1]++;
							}
							break;
						}
						case 5:{
							val[2]++;
							break;
						}
					}
				} 
				
			}else{
				len=0;
			}
			
		}
	} 
	for(i=0;i<maplen;i++){
		int len=0;
		int len1=0;
		for(j=0;j<maplen;j++){
			if(data[j*maplen+i]==flag){
				len1++;
				if(j+1>=maplen||data[(j+1)*maplen+i]!=flag){
					switch(len1){
						case 2:{
							if(j-2>=0&&j+1<maplen&&!data[(j-2)*maplen+i]&&!data[(j+1)*maplen+i]){
								val[3]++;
							}
							break;
						}
						case 3:{
							if((j+1<maplen&&!data[(j+1)*maplen+i])&&(j-3>=0&&!data[(j-3)*maplen+i])){
								val[0]+=3;
							}
							if((j+1<maplen&&!data[(j+1)*maplen+i])&&(j+2<maplen&&!data[(j+2)*maplen+i])){
								val[0]++;
							}
							if((j-4>=0&&!data[(j-4)*maplen+i])&&(j-3>=0&&!data[(j-3)*maplen+i])){
								val[0]++;
							}
							
							break;
						}
						case 4:{
							if((j+1<maplen&&!data[(j+1)*maplen+i])){
								val[1]++;
							}
							if((j-4>=0&&!data[(j-4)*maplen+i])){
								val[1]++;
							}
							break;
						}
						case 5:{
							val[2]++;	
							break;
						}
					}
				}
				
			}else{
				len1=0;
			}
			
			if(data[i*maplen+j]==flag){
				len++;
				if(j+1>=maplen||data[i*maplen+j+1]!=flag){
					switch(len){
						case 2:{
							if(j-2>=0&&j+1<maplen&&!data[i*maplen+j-2]&&!data[i*maplen+j+1]){
								val[3]++;
							}
							break;
						}
						case 3:{
							if((j+1<maplen&&!data[i*maplen+j+1])&&(j-3>=0&&!data[i*maplen+j-3])){
								val[0]+=3;
							}
							if((j+1<maplen&&!data[i*maplen+j+1])&&(j+2<maplen&&!data[i*maplen+j+2])){
								val[0]++;
							}
							if((j-4>=0&&!data[i*maplen+j-4])&&(j-3>=0&&!data[i*maplen+j-3])){
								val[0]++;
							}
							
							break;
						}
						case 4:{
							if((j+1<maplen&&!data[i*maplen+j+1])){
								val[1]++;
							}
							if((j-4>=0&&!data[i*maplen+j-4])){
								val[1]++;
							}
							break;
						}
						case 5:{
							val[2]++;
							
							break;
						}
					}
				}	
			}else{
				len=0;
			}
		}
	}
	if(flag==1) return (val[2]<<14)+(val[1]<<10)+(val[0]<<5)+(val[3]<<2);
	else return (val[2]<<13)+(val[1]<<9)+(val[0]<<4)+(val[3]<<1);
	
}
int maxmin(int depth,int*data,int flag,int a,int b){
	if(!depth){
		return getvalue(data,1)-getvalue(data,-1);
	}
	if(flag==1){//轮到自己走了，选最大的 
		ch p=getchild(data,flag);
		ch p1=p->next;
		while(p->next){
			int tmp=maxmin(depth-1,p->next->ls,flag*(-1),a,b);		
			if(tmp>a) {
				a=tmp;
				if(a>b) break;
				if(depth==dddd){
					memcpy(data,p->next->ls,sizeof(int)*mapsize);
					printf("电脑埋头苦算中：%d\n",a);
				}			
			}
			free(p->ls);
			free(p);
			p=p1;
			p1=p1->next;	
		}
		while(p->next){
			free(p->ls);
			free(p);
			p=p1;
			p1=p1->next;
		}
		free(p->ls);
			free(p); 
		return a;
	}else{
		ch p=getchild(data,flag);
		ch p1=p->next;
		while(p->next){
			int tmp=maxmin(depth-1,p->next->ls,flag*(-1),a,b);
			if(tmp<b){
				 b=tmp;
				 if(a>b) break;
			}
			free(p->ls);
			free(p);
			p=p1;
			p1=p1->next;
			
		}
		while(p->next){
			free(p->ls);
			free(p);
			p=p1;
			p1=p1->next;
		}
		free(p->ls);
			free(p);
		return b;
	}	
} 
void getnextstep(int*a,int*b,int*map){	
	while(scanf("%d%d",a,b)!=2||*a<0||*a>=maplen||*b<0||*b>=maplen||map[*a*maplen+*b]){
		gets(NULL);
		printf("输入有误！请重新输入位置x,y(从0-%d)\n",maplen-1);			
	}
}
int trans(int x,int y){
	return x*maplen+y;
}
int main(void){
	map[112]=1;
//	map[0]=-1;
//	map[15]=-1;
//	map[30]=-1;
//	map[45]=-1;
//	map[1]=1;
//	map[2]=1;
//	map[3]=1;
//	ch chd=getchild(map,1);
//	while(chd->next){
//		print_map(chd->next->ls);
//		printf("%d",getvalue(chd->next->ls,1)-getvalue(chd->next->ls,-1));
//		chd=chd->next;
//	}

	print_map(map);
	while(1){
		int x,y;
		getnextstep(&x,&y,map);
		map[x*maplen+y]=-1;
		print_map(map);
		if(getvalue(map,-1)>=14000){
			printf("you win！\n");
			break;
		}	
		maxmin(dddd,map,1,-100000,100000);
		print_map(map);
		if(getvalue(map,1)>=14000){
			printf("ai win！\n");
			break;
		}
	}
	return 0;
}