首页 > 其他分享 >五子棋AI

五子棋AI

时间：2022-10-20 12:22:42浏览次数：48  
标签：AI 五子棋 LEN else fx int && type

瞎写的，传上来备份一下

#pragma GCC optimize(3)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define L2 1
#define abs(x) (x>0?(x):-(x))
#define inf 999999
#define LEN 19
//normal size is 19
using namespace std;

int a[LEN+2][LEN+2],randomseed;
//={
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,1,2,0,0,0,1,0,0,0,0,0,0},
//{0,0,2,2,2,1,1,1,2,1,0,0,0,0,0},
//{0,0,0,1,2,2,1,1,2,1,0,0,0,0,0},
//{0,0,0,1,1,2,2,1,2,0,0,0,0,0,0},
//{0,0,0,1,2,1,1,2,0,0,0,0,0,0,0},
//{0,0,0,1,2,2,2,2,1,0,0,0,0,0,0},
//{0,1,2,2,2,2,1,0,0,0,0,0,0,0,0},
//{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
//{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}; //1P=X 2P=O

int v[6]={0,1,10,100,inf,inf};
int fx[2][8]={{0,1,1,1,0,-1,-1,-1},{1,1,0,-1,-1,-1,0,1}};
int i,j,k,l,x,y,type,tot;
int level1,level2; //program's level
bool p1,p2,L; //=0 is human,=1 is computer
bool show; //whether paint the map
//win:
//easy:normal=1:inf

int random(int x,int y)
{
	return rand()%(y-x+1)+x;
}

void paint()
{
	int i,j;
	
//	system("cls");
	printf("  1 2 3 4 5 6 7 8 9 10111213141516171819\n");
	fo(i,1,LEN)
	{
		printf("%2d",i);
		
		fo(j,1,LEN)
		{
			switch (a[i][j])
			{
				case 0:{
					printf("..");
					break;
				}
				case 1:{
					printf("●");
					break;
				}
				case 2:{
					printf("○");
					break;
				}
			}
		}
		printf("\n");
	}
}

void win(int type)
{
	paint();
	printf("%dP win!\n",type);
	cout<<randomseed<<endl;
	system("pause");
	exit(0);
}

void check()
{
	int i,j,k,l;
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN-4)
		if (a[i][j] && a[i][j]==a[i][j+1] && a[i][j+1]==a[i][j+2] && a[i][j+2]==a[i][j+3] && a[i][j+3]==a[i][j+4])
		win(a[i][j]);
	}
	fo(i,1,LEN-4)
	{
		fo(j,1,LEN)
		if (a[i][j] && a[i][j]==a[i+1][j] && a[i+1][j]==a[i+2][j] && a[i+2][j]==a[i+3][j] && a[i+3][j]==a[i+4][j])
		win(a[i][j]);
	}
	fo(i,1,LEN-4)
	{
		fo(j,1,LEN-4)
		if (a[i][j] && a[i][j]==a[i+1][j+1] && a[i+1][j+1]==a[i+2][j+2] && a[i+2][j+2]==a[i+3][j+3] && a[i+3][j+3]==a[i+4][j+4])
		win(a[i][j]);
	}
	fo(i,1,LEN-4)
	{
		fo(j,1,LEN-4)
		if (a[i][j+4] && a[i][j+4]==a[i+1][j+3] && a[i+1][j+3]==a[i+2][j+2] && a[i+2][j+2]==a[i+3][j+1] && a[i+3][j+1]==a[i+4][j])
		win(a[i][j+4]);
	}
}
bool Check()
{
	int i,j,k,l;
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN-4)
		if (a[i][j] && a[i][j]==a[i][j+1] && a[i][j+1]==a[i][j+2] && a[i][j+2]==a[i][j+3] && a[i][j+3]==a[i][j+4])
		return 1;
	}
	fo(i,1,LEN-4)
	{
		fo(j,1,LEN)
		if (a[i][j] && a[i][j]==a[i+1][j] && a[i+1][j]==a[i+2][j] && a[i+2][j]==a[i+3][j] && a[i+3][j]==a[i+4][j])
		return 1;
	}
	fo(i,1,LEN-4)
	{
		fo(j,1,LEN-4)
		if (a[i][j] && a[i][j]==a[i+1][j+1] && a[i+1][j+1]==a[i+2][j+2] && a[i+2][j+2]==a[i+3][j+3] && a[i+3][j+3]==a[i+4][j+4])
		return 1;
	}
	fo(i,1,LEN-4)
	{
		fo(j,1,LEN-4)
		if (a[i][j+4] && a[i][j+4]==a[i+1][j+3] && a[i+1][j+3]==a[i+2][j+2] && a[i+2][j+2]==a[i+3][j+1] && a[i+3][j+1]==a[i+4][j])
		return 1;
	}
	return 0;
}

void put(int x,int y,int type)
{
	++tot;
	if (show)
	{
		printf("\n");
		cout<<tot<<endl;
		printf("%dP: (%d,%d)\n",type,x,y);
	}
	
	a[x][y]=type;
	check();
}

void work_easy(int type)
{
	int x,y;
	
	x=random(1,LEN),y=random(1,LEN);
	while (a[x][y])
	x=random(1,LEN),y=random(1,LEN);
	
	put(x,y,type);
}

void work_normal(int type)
{
	int i,j,k,l,mn=-1,mnx=(LEN+1)/2,mny=(LEN+1)/2,S,s,x,y;
	bool bz1,bz2;
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN)
		if (!a[i][j])
		{
			fo(k,0,7)
			if (a[i+fx[0][k]][j+fx[1][k]])
			break;
			
			if (k==8) continue;
			
			S=0;
			fo(k,0,7)
			{
				x=i+fx[0][k];
				y=j+fx[1][k];
				l=0;s=0;
				while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=(3-type) && l<4)
				{
					++l;
					s+=(a[x][y]==type);
					
					x+=fx[0][k];
					y+=fx[1][k];
				}
				S+=v[s];
				
//				---
				
				x=i+fx[0][k];
				y=j+fx[1][k];
				l=0;s=0;
				while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=type && l<4)
				{
					++l;
					s+=(a[x][y]==(3-type));
					
					x+=fx[0][k];
					y+=fx[1][k];
				}
				S+=v[s];
			}
			
			if (S>mn || S==mn && rand()%100<30)
			{
				mn=S;
				mnx=i;
				mny=j;
			}
		}
	}
	
	put(mnx,mny,type);
}

bool pd(int type)
{
	int i,j;
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN)
		if (!a[i][j])
		{
			a[i][j]=type;
			
			if (Check())
			{
				a[i][j]=0;
				return 1;
			}
			a[i][j]=0;
		}
	}
	
	return 0;
}

int Dfs(int bg,int t,int type)
{
	int A[LEN+2][LEN+2];memset(A,0,sizeof(A));
	int i,j,k,K,X,Y,l,mn=-2133333333,mn2,mnx=(LEN+1)/2,mny=(LEN+1)/2,S,s,x,y;//,tot=0;
	bool bz1,bz2,BZ;
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN)
		if (!a[i][j])
		{
			BZ=0;
			fo(k,0,7)
			{
				if (a[i+fx[0][k]][j+fx[1][k]])
				{
					BZ=1;
					break;
				}
				
				fo(K,0,7)
				{
					X=i+fx[0][k]+fx[0][K];
					Y=i+fx[1][k]+fx[1][K];
					
					if (X>=1 && X<=LEN && Y>=1 && Y<=LEN && a[X][Y])
					{
						BZ=1;
						break;
					}
				}
			}
			
			if (!BZ) continue;
			
			S=0;
			fo(k,0,7)
			{
				x=i+fx[0][k];
				y=j+fx[1][k];
				l=0;s=0;
				while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=(3-type) && l<4)
				{
					++l;
					s+=(a[x][y]==type);
					
					x+=fx[0][k];
					y+=fx[1][k];
				}
				S+=v[s];
				
//				---
				
				x=i+fx[0][k];
				y=j+fx[1][k];
				l=0;s=0;
				while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=type && l<4)
				{
					++l;
					s+=(a[x][y]==(3-type));
					
					x+=fx[0][k];
					y+=fx[1][k];
				}
				S+=v[s];
			}
			fo(k,0,7)
			if (x+fx[0][k]>=1 && x+fx[0][k]<=LEN && y+fx[1][k]>=1 && y+fx[1][k]<=LEN)
			{
				if (a[i+fx[0][k]][j+fx[1][k]]==type)
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==type && l<4)
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (a[x][y] || !(x>=1 && x<=LEN && y>=1 && y<=19))
					S+=v[s];
					else
					S+=v[s+1];
				}
				
//				---
				
				if (a[i+fx[0][k]][j+fx[1][k]]==(3-type))
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==(3-type))
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (a[x][y] || !(x>=1 && x<=LEN && y>=1 && y<=19))
					S+=v[s];
					else
					S+=v[s+1];
				}
			}
			fo(k,0,3)
			{
				if (a[i+fx[0][k]][j+fx[1][k]]==type && a[i+fx[0][k+4]][j+fx[1][k+4]]==type)
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==type)
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==(3-type))
					bz1=0; else bz1=1;
					
					x=i+fx[0][k+4];
					y=j+fx[1][k+4];
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==type)
					{
						++s;
						
						x+=fx[0][k+4];
						y+=fx[1][k+4];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==(3-type))
					bz2=0; else bz2=1;
					
					if (s>=4)
					S+=inf;
					else
					{
						if (bz1 && bz2)
						S+=v[s+1]+L*L2*v[s+1];
						else
						if (bz1 || bz2)
						S+=v[s]+L*L2*v[s];
					}
				}
				
//				---
				
				if (a[i+fx[0][k]][j+fx[1][k]]==(3-type) && a[i+fx[0][k+4]][j+fx[1][k+4]]==(3-type))
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==(3-type))
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==type)
					bz1=0; else bz1=1;
					
					x=i+fx[0][k+4];
					y=j+fx[1][k+4];
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==(3-type))
					{
						++s;
						
						x+=fx[0][k+4];
						y+=fx[1][k+4];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==type)
					bz2=0; else bz2=1;
					
					if (s>=4)
					S+=inf;
					else
					{
						if (bz1 && bz2)
						S+=v[s+1];
						else
						if (bz1 || bz2)
						S+=v[s];
					}
				}
			}
			
			a[i][j]=type;
			if (Check())
			S+=inf;
			else
			{
				if (t>1 && pd(3-type))
				S-=inf;
//				S-=dfs(bg,t-1,3-type);
			}
			a[i][j]=0;
			A[i][j]=S;
			
			if (S>mn || S==mn && rand()%100<30)//abs(i-(LEN+1)/2)+abs(j-(LEN+1)/2)<mn2)
			{
				mn=S;
				mn2=abs(i-(LEN+1)/2)+abs(j-(LEN+1)/2);
				mnx=i;
				mny=j;
				
//				if (mn>=999999)
//				break;
			}
//			A[++tot]=S;
		}
		
//		if (mn>=999999)
//		break;
	}
	
	if (t==bg)
	put(mnx,mny,type);
	else
	return mn;
//	else
//	{
//	}
}

int dfs(int bg,int t,int type) //lunatic
{
	int A[LEN+2][LEN+2],b[7];memset(A,0,sizeof(A));
	int i,j,k,K,X,Y,l,mn=-2133333333,mnx=(LEN+1)/2,mny=(LEN+1)/2,S,s,x,y;//,tot=0;
	bool bz1,bz2,BZ;
	
	bz1=0;
	fo(i,1,LEN)
	{
		fo(j,1,LEN)
		if (a[i][j]) {bz1=1;break;}
	}
	if (!bz1) {put((LEN+1)/2,(LEN+1)/2,type);return 0;}
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN)
		if (!a[i][j])
		{
			BZ=0;
			fo(k,0,7)
			{
				if (a[i+fx[0][k]][j+fx[1][k]])
				{
					BZ=1;
					break;
				}
				
				fo(K,0,7)
				{
					X=i+fx[0][k]+fx[0][K];
					Y=i+fx[1][k]+fx[1][K];
					
					if (X>=1 && X<=LEN && Y>=1 && Y<=LEN && a[X][Y])
					{
						BZ=1;
						break;
					}
				}
			}
			
			if (!BZ) continue;
			
			S=0;
			fo(k,0,7)
			{
				x=i+fx[0][k];
				y=j+fx[1][k];
				l=0;s=0;
				while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=(3-type) && l<4)
				{
					++l;
					s+=(a[x][y]==type);
					
					x+=fx[0][k];
					y+=fx[1][k];
				}
				S+=v[s];
				
//				---
				
				x=i+fx[0][k];
				y=j+fx[1][k];
				l=0;s=0;
				while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=type && l<4)
				{
					++l;
					s+=(a[x][y]==(3-type));
					
					x+=fx[0][k];
					y+=fx[1][k];
				}
				S+=v[s];
			}
			l=0;
			fo(k,0,7)
			if (x+fx[0][k]>=1 && x+fx[0][k]<=LEN && y+fx[1][k]>=1 && y+fx[1][k]<=LEN)
			{
				if (a[i+fx[0][k]][j+fx[1][k]]==type)
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==type && l<4)
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (a[x][y] || !(x>=1 && x<=LEN && y>=1 && y<=19))
					S+=v[s];
					else
					S+=v[s+1];
				}
				
//				---
				
				if (a[i+fx[0][k]][j+fx[1][k]]==(3-type))
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==(3-type))
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (a[x][y] || !(x>=1 && x<=LEN && y>=1 && y<=19))
					S+=v[s];
					else
					S+=v[s+1];
				}
			}
			
			memset(b,0,sizeof(b));
			fo(k,0,7)
			if (x+fx[0][k]>=1 && x+fx[0][k]<=LEN && y+fx[1][k]>=1 && y+fx[1][k]<=LEN)
			{
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;l=1;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=3-type && l<=4)
					{
						s+=a[x][y]==type;
						
						x+=fx[0][k];
						y+=fx[1][k];
						++l;
					}
					if (a[x][y] || !(x>=1 && x<=LEN && y>=1 && y<=19))
					++b[s];
					else
					++b[s+1];
				}
				
//				---
				
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;l=1;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]!=type && l<=4)
					{
						s+=a[x][y]==(3-type);
						
						x+=fx[0][k];
						y+=fx[1][k];
						++l;
					}
					if (a[x][y] || !(x>=1 && x<=LEN && y>=1 && y<=19))
					++b[s];
					else
					++b[s+1];
				}
			}
//			if (tot==31 && i==8 && j==9)
//			tot=tot;
			if (b[3]+b[4]+b[5]+b[6]>1)
			S+=(b[3]+b[4]+b[5]+b[6]-1)*1000;
			
			fo(k,0,3)
			{
				if (a[i+fx[0][k]][j+fx[1][k]]==type && a[i+fx[0][k+4]][j+fx[1][k+4]]==type)
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==type)
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==(3-type))
					bz1=0; else bz1=1;
					
					x=i+fx[0][k+4];
					y=j+fx[1][k+4];
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==type)
					{
						++s;
						
						x+=fx[0][k+4];
						y+=fx[1][k+4];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==(3-type))
					bz2=0; else bz2=1;
					
					if (s>=4)
					S+=inf;
					else
					{
						if (bz1 && bz2)
						S+=v[s+1];
						else
						if (bz1 || bz2)
						S+=v[s];
					}
				}
				
//				---
				
				if (a[i+fx[0][k]][j+fx[1][k]]==(3-type) && a[i+fx[0][k+4]][j+fx[1][k+4]]==(3-type))
				{
					x=i+fx[0][k];
					y=j+fx[1][k];
					s=0;
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==(3-type))
					{
						++s;
						
						x+=fx[0][k];
						y+=fx[1][k];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==type)
					bz1=0; else bz1=1;
					
					x=i+fx[0][k+4];
					y=j+fx[1][k+4];
					while (x>=1 && x<=LEN && y>=1 && y<=LEN && a[x][y]==(3-type))
					{
						++s;
						
						x+=fx[0][k+4];
						y+=fx[1][k+4];
					}
					if (!(x>=1 && x<=LEN && y>=1 && y<=LEN) || a[x][y]==type)
					bz2=0; else bz2=1;
					
					if (s>=4)
					S+=inf;
					else
					{
						if (bz1 && bz2)
						S+=v[s+1];
						else
						if (bz1 || bz2)
						S+=v[s];
					}
				}
			}
			
			a[i][j]=type;
			if (Check())
			S+=inf;
			else
			{
				if (t>1 && pd(3-type))
				S=0;
//				S-=dfs(bg,t-1,3-type);
			}
			a[i][j]=0;
			A[i][j]=S;
			
			if (!L)
			{
				if (S>mn || S==mn && rand()%100<30)//abs(i-(LEN+1)/2)+abs(j-(LEN+1)/2)<mn2)
				{
					mn=S;
					mnx=i;
					mny=j;
				}
			}
		}
	}
	
	fo(i,1,LEN)
	{
		fo(j,1,LEN)
		if (!a[i][j] && A[i][j]>0)
		{
			S=l=0;
			fo(k,0,7)
			if (A[i+fx[0][k]][j+fx[1][k]]>0)
			S+=A[i+fx[0][k]][j+fx[1][k]]+20;
			S=S/2+A[i][j];
			
			if (S>mn || S==mn && rand()%100<30)
			{
				mn=S;
				mnx=i;
				mny=j;
			}
		}
	}
	if (mn==-2133333333)
	{
		fo(i,1,LEN)
		{
			fo(j,1,LEN)
			if (!a[i][j])
			{
				fo(k,0,7)
				if (a[i+fx[0][k]][j+fx[1][k]]==3-type && rand()%100<30)
				{
					mnx=i;
					mny=j;
				}
			}
		}
	}
//	fo(i,1,LEN)
//	{
//		fo(j,1,LEN)
//		cout<<A[i][j]<<" ";
//		cout<<endl;
//	}
	
	if (t==bg)
	put(mnx,mny,type);
	else
	return mn;
}

void work_hard(int type)
{
	v[2]=10;
	Dfs(2,2,type);
}

void work_lunatic(int type)
{
	L=1;v[2]=50;
	dfs(2,2,type);
}

int main()
{
	randomseed=time(NULL);
//	randomseed=1587714028; //1pwin 1587615806 1587615899 1587615946
	srand(randomseed);
	rand();
	
	p1=0;
	level1=3;
	p2=1;
	level2=4;
	show=1;
	
	type=1;
	while (1)
	{
		if (show)
		paint();
		
		if (type==1)
		{
			if (!p1)
			{
				scanf("%d%d",&x,&y);
				while (a[x][y])
				{
					printf("No!");
					scanf("%d%d",&x,&y);
				}
				
				put(x,y,type);
			}
			else
			{
				switch (level1)
				{
					case 1:{
						work_easy(type);
						break;
					}
					case 2:{
						work_normal(type);
						break;
					}
					case 3:{
						work_hard(type);
						break;
					}
					case 4:{
						work_lunatic(type);
						break;
					}
				}
			}
		}
		else
		{
			if (!p2)
			{
				scanf("%d%d",&x,&y);
				while (a[x][y])
				{
					printf("No!");
					scanf("%d%d",&x,&y);
				}
				
				put(x,y,type);
			}
			else
			{
				switch (level2)
				{
					case 1:{
						work_easy(type);
						break;
					}
					case 2:{
						work_normal(type);
						break;
					}
					case 3:{
						work_hard(type);
						break;
					}
					case 4:{
						work_lunatic(type);
						break;
					}
				}
			}
		}
		type=3-type;
	}
}

标签：AI,五子棋,LEN,else,fx,int,&&,type
From： https://www.cnblogs.com/gmh77/p/16809431.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99