C语言实现极小极大搜索算法五子棋
本人只是一名大二学生，技术有限，代码比较乱，但愿指正，这也是我第一次写博客，排版也很差，见谅。
极小极大算法
无论是什么棋类，看似很复杂，但均可以把每一种走法列出来，列出来后，你就能够发现，它就是一颗博弈树。因此咱们能够用极小极大搜索算法来实现五子棋。javascript
极小极大算法博弈树的生成，每一层分为MAX层或MIN层，如图（图片来自百度），第0层为当前局面，MAX层生成的走法即为下一层的MIN层，除第0层，其余MAX层为上一层MIN层的走法，MIN层也为上一层MAX层的走法。java
极小极大搜索算法分数的传递，在MAX层中，为了MAX层利益的极大化，会从下一层选择最大的分数，而在MIN层中，为了对手利益的最小化，会从下一层选择分数最小。web
分数的传递可使用递归来实现算法
int minMax(int co[20][20],int deep,int a,int Alpha,int Beta) //分数传递,a为1表示白棋，为2表示黑棋,调用时Alpha，Beta赋为NGIF,PTIF { int i,j; int c[20][20]; int minmax; int b; int n=1; Tree tree; tree.data=NGIF; tree.Alpha=Alpha; tree.Beta=Beta; tree.X=0; tree.Y=0; if(a==1) b=2; else b=1; if(deep>0) { for(i=0;i<20;i++) for(j=0;j<20;j++) { if(co[i][j]==0&&jdgen(co,i,j,1)&&tree.Alpha<tree.Beta)//α-β剪枝 { memcpy(c,co,sizeof(int)*400); c[i][j]=a; minmax=minMax(c,deep-1,b,tree.Alpha,tree.Beta);//递归调用 if(deep%2==0) { if(n==1) { tree.data=minmax; n++; } if(tree.Alpha<minmax) { tree.Alpha=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } else { if(n==1) { tree.data=minmax; n++; } if(tree.Beta>minmax) { tree.Beta=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } } } for(i=0;i<20;i++) for(j=0;j<20;j++) { if(co[i][j]==0&&jdgen(co,i,j,2)&&tree.Alpha<tree.Beta)//α-β剪枝 { memcpy(c,co,sizeof(int)*400); c[i][j]=a; minmax=minMax(c,deep-1,b,tree.Alpha,tree.Beta);//递归调用 if(deep%2==0) { if(tree.Alpha<minmax) { tree.Alpha=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } else { if(tree.Beta>minmax) { tree.Beta=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } } } X=tree.X; Y=tree.Y; return tree.data; } else { return score(a,co,1);//局面评分 } }
α-β剪枝
由五子棋生成的博弈树及其庞大，若是不对它进行优化，它能搜索的层数就及其有限，α-β剪枝可以去掉一些用处不大的走法，以提升运行的速度。windows
α-β剪枝的实现，博弈树中每个节点都有一个α和β，初始设置α为负无穷大，β为正无穷大。对于MAX层，为了是本身利益最大化，会从下一层选择最大的分数，当传递上来的分数大于α时，则修改α值为此分数。对于MIN层，为了使对手利益最小化，会从下一层选择最小分数，当分数小于β，则修改β值，当每个节点要生成下一步棋子时，先判断α与β，若是α>β，则不用在生成下一步的走法，而是返回上一层。svg
详情可移步 Alpha-Beta剪枝(Alpha Beta Pruning)函数
棋子生成
棋子生成函数能够生成下一步可走的走法，对于整个棋盘，若是每个能够落子的地方都要生成棋子，那运行速度将会很是慢，搜索深度会很是有限，这一步也是对程序优化的重要部分。事实上不是每个空位都要搜索，有一个比较简单的作法，就是只搜索有棋子的邻居空位，即只需搜索两步以内有棋子的空位，如图红色区域。
优化
int jdgen(int co[20][20],int x,int y,int n) //判断x，y坐标是否可生成棋子，能够返回1，不然返回0,n为1，判断内侧棋子，为2，判断外侧棋子 { int i,j; int sum=0; if(n==1) { for(i=x-1;i<x+2;i++) for(j=y-1;j<y+2;j++) if((i>0&&j>0&&i<20&&j<20)&&(co[i][j]==1||co[i][j]==2)) sum=1; } else { for(i=x-2;i<x+3;i+=2) for(j=y-2;j<y+3;j+=2) if((i>0&&j>0&&i<20&&j<20)&&(co[i][j]==1||co[i][j]==2)) sum=1; } return sum; }
局面分数评估
极小极大搜索的分数，来自最后一层对局面的评估。这一步咱们也采用比较简单的一种作法。评分规则：活一10，活二100，活三1000，活四10000，活五100000。死二10，死三100，死四1000。若是连子两侧没有被堵死，则称为活，若是只堵死一侧，称为死，若是都被堵死，则没有分数。
将机器的棋子进行单独打分，在减去对手棋子单独打分，即为最终局面的分数。spa
// 评分函数 int score(int a,int co[20][20],int n) //评分,a为1表示白棋，为2表示黑棋,n为1避免递归调用出现死循环 { int i,j,k,l; int sum=0,su=0; for(i=0;i<20;i++) //点 for(j=0;j<20;j++) if(co[i][j]==a) { for(k=i-1;k<i+2;k++) for(l=j-1;l<j+2;l++) su+=co[k][l]; if(su==a&&i!=0&&i!=19&&j!=0&&j!=19) sum+=10; su=0; } su=0; for(i=0;i<20;i++) //横 for(j=0;j<21;j++) { if(co[i][j]==a) su++; else if(su>1) { if(co[i][j-su-1]==0&&co[i][j]==0) { sum+=pow(10,su); } else if(co[i][j-su-1]!=0&&co[i][j]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } for(su=0,i=0;i<20;i++) //竖 for(j=0;j<21;j++) { if(co[j][i]==a) su++; else if(su>1) { if(co[j-su-1][i]==0&&co[j][i]==0) { sum+=pow(10,su); } else if(co[j-su-1][i]!=0&&co[j][i]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } for(su=0,i=-19;i<20;i++) //╱ for(j=i,k=19;j<20;j++,k--) if(j>=0&&j<20&&k>=0&&k<20) { if(co[j][k]==a) su++; else if(su>1) { if(co[j-su-1][k+su+1]==0&&co[j][k]==0) { sum+=pow(10,su); } else if(co[j-su-1][k+su+1]!=0&&co[j][k]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } for(su=0,i=-19;i<20;i++) //╲ for(j=i,k=0;j<20;j++,k++) if(j>=0&&j<20&&k>=0&&k<20) { if(co[j][k]==a) su++; else if(su>1) { if(co[j-su-1][k-su-1]==0&&co[j][k]==0) { sum+=pow(10,su); } else if(co[j-su-1][k-su-1]!=0&&co[j][k]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } if(n==1&&a==1) return sum-score(2,co,2); else if(n==1&&a==2) return sum-score(1,co,2); else if(n==2) return sum; }
程序代码
// wuziqi.c #include<stdio.h> #include<stdlib.h> #include<windows.h> int coord[20][20];//白棋为1，黑棋为2 extern int* human(); extern int* conputer(int x); static void gotoxy(int x,int y) { COORD pos={x,y}; HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleCursorPosition(hOut,pos); } static void board(int co[20][20]) //棋盘:输出棋盘网格 { int i,j; gotoxy(0,0);puts("┏ ━"); gotoxy(0,42);puts("┗ ━"); gotoxy(84,0);puts("┓"); gotoxy(84,42);puts("┛"); for(i=1;i<21;i++) for(j=1;j<21;j++) { gotoxy(j*4,2*i-1);puts("┃"); gotoxy(j*4,i*2);puts("╋ ━"); } for(i=1;i<22;i++) { gotoxy(0,i*2-1);puts("┃"); gotoxy(84,i*2-1);puts("┃"); } for(i=1;i<21;i++) { gotoxy(i*4,0);puts("┳ ━"); gotoxy(i*4,42);puts("┻ ━"); gotoxy(i*4,41);puts("┃"); gotoxy(2,i*2);puts("━"); gotoxy(0,i*2);puts("┣"); gotoxy(84,i*2);puts("┫"); } for(i=0;i<20;i++) for(j=0;j<20;j++) coord[i][j]=0; } static void chess(int x,int y,int a) //下棋:a为1表示白棋下，为2表示黑棋下，输入x，y和a后向棋盘输出棋子并对coord赋值 { if(a==1&&coord[x][y]==0) { gotoxy((y+1)*4,(x+1)*2);puts("●"); coord[x][y]=1; } else if(a==2&&coord[x][y]==0) { gotoxy((y+1)*4,(x+1)*2);puts("○"); coord[x][y]=2; } } void location(int x,int y) // 定位 { gotoxy((y+1)*4-2,(x+1)*2-1);puts("┛"); gotoxy((y+1)*4+2,(x+1)*2-1);puts("┗"); gotoxy((y+1)*4-2,(x+1)*2+1);puts("┓"); gotoxy((y+1)*4+2,(x+1)*2+1);puts("┏"); } void clearlocation(int x,int y) //清除定位 { gotoxy((y+1)*4-2,(x+1)*2-1);puts(" "); gotoxy((y+1)*4+2,(x+1)*2-1);puts(" "); gotoxy((y+1)*4-2,(x+1)*2+1);puts(" "); gotoxy((y+1)*4+2,(x+1)*2+1);puts(" "); } static int overgame(int x,int y,int a) //判断输赢:a为1表示白棋胜，2表示黑棋胜，x，y表示当前下子,若是一方获胜返回1，不然返回0 { int i,j,sum; for(sum=0,j=y-4;j<y+5;j++)//横 { if(sum>4) break; else if(coord[x][j]!=a) sum=0; else sum++; } if(sum==5) { gotoxy(86,1); if(a==1) puts("白棋胜，按任意键退出"); else if(a==2) puts("黑棋胜，按任意键退出"); return 1; } for(sum=0,i=x-4;i<x+5;i++)//竖 { if(sum>4) break; else if(coord[i][y]!=a) sum=0; else sum++; } if(sum==5) { gotoxy(86,1); if(a==1) puts("白棋胜，按任意键退出"); else if(a==2) puts("黑棋胜，按任意键退出"); return 1; } for(sum=0,i=x-4,j=y-4;i<x+5&&j<y+5;i++,j++)//╲ { if(sum>4) break; else if(coord[i][j]!=a) sum=0; else sum++; } if(sum==5) { gotoxy(86,1); if(a==1) puts("白棋胜，按任意键退出"); if(a==2) puts("黑棋胜，按任意键退出"); return 1; } for(sum=0,i=x-4,j=y+4;i<x+5&&j>y-5;i++,j--)//╱ { if(sum>4) break; else if(coord[i][j]!=a) sum=0; else sum++; } if(sum==5) { gotoxy(86,1); if(a==1) puts("白棋胜，按任意键退出"); if(a==2) puts("黑棋胜，按任意键退出"); return 1; } return 0; } static void control(int *p,int a) //控制p1，p2玩家落子，p1（），p2（）返回值转给p，a为1表示白棋下，为2表示黑棋下 { static int x,y; chess(p[0],p[1],a); location(p[0],p[1]); clearlocation(x,y); x=p[0]; y=p[1]; if(overgame(p[0],p[1],a)==1) { gotoxy(86,0); exit(0); } } int main() { int x,n; printf("输入搜索深度(输入偶数,例:2,4,6,搜索深度越深,程序运行越慢):"); scanf("%d",&x); printf("先手按1,后手按2:"); scanf("%d",&n); gotoxy(0,0); puts(" "); gotoxy(0,1); puts(" "); board(coord); while(1) { if(n==1){ control(human(),1); control(computer(x),2); } if(n==2){ control(computer(x),1); control(human(),2); } } }
// MINMAX.c #include<math.h> #include<string.h> #define PTIF 2147483647//正无穷,Beta #define NGIF -2147483648//负无穷,Alpha int X,Y; extern int coord[20][20]; int score(int a,int co[20][20],int n) //评分,a为1表示白棋，为2表示黑棋,n为1避免递归调用出现死循环 { int i,j,k,l; int sum=0,su=0; for(i=0;i<20;i++) //点 for(j=0;j<20;j++) if(co[i][j]==a) { for(k=i-1;k<i+2;k++) for(l=j-1;l<j+2;l++) su+=co[k][l]; if(su==a&&i!=0&&i!=19&&j!=0&&j!=19) sum+=10; su=0; } su=0; for(i=0;i<20;i++) //横 for(j=0;j<21;j++) { if(co[i][j]==a) su++; else if(su>1) { if(co[i][j-su-1]==0&&co[i][j]==0) { sum+=pow(10,su); } else if(co[i][j-su-1]!=0&&co[i][j]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } for(su=0,i=0;i<20;i++) //竖 for(j=0;j<21;j++) { if(co[j][i]==a) su++; else if(su>1) { if(co[j-su-1][i]==0&&co[j][i]==0) { sum+=pow(10,su); } else if(co[j-su-1][i]!=0&&co[j][i]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } for(su=0,i=-19;i<20;i++) //╱ for(j=i,k=19;j<20;j++,k--) if(j>=0&&j<20&&k>=0&&k<20) { if(co[j][k]==a) su++; else if(su>1) { if(co[j-su-1][k+su+1]==0&&co[j][k]==0) { sum+=pow(10,su); } else if(co[j-su-1][k+su+1]!=0&&co[j][k]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } for(su=0,i=-19;i<20;i++) //╲ for(j=i,k=0;j<20;j++,k++) if(j>=0&&j<20&&k>=0&&k<20) { if(co[j][k]==a) su++; else if(su>1) { if(co[j-su-1][k-su-1]==0&&co[j][k]==0) { sum+=pow(10,su); } else if(co[j-su-1][k-su-1]!=0&&co[j][k]!=0) { if(su==5) sum+=100000; } else { if(su==5) sum+=100000; else sum+=pow(10,su-1); } su=0; } else su=0; } if(n==1&&a==1) return sum-score(2,co,2); else if(n==1&&a==2) return sum-score(1,co,2); else if(n==2) return sum; } int jdgen(int co[20][20],int x,int y,int n) //判断x，y坐标是否可生成棋子，能够返回1，不然返回0,n为1，判断内侧，为2，判断外侧 { int i,j; int sum=0; if(n==1) { for(i=x-1;i<x+2;i++) for(j=y-1;j<y+2;j++) if((i>0&&j>0&&i<20&&j<20)&&(co[i][j]==1||co[i][j]==2)) sum=1; } else { for(i=x-2;i<x+3;i+=2) for(j=y-2;j<y+3;j+=2) if((i>0&&j>0&&i<20&&j<20)&&(co[i][j]==1||co[i][j]==2)) sum=1; } return sum; } typedef struct { int data; int Alpha; int Beta; int X; int Y; }Tree; int minMax(int co[20][20],int deep,int a,int Alpha,int Beta) //分数传递,a为1表示白棋，为2表示黑棋,调用时Alpha，Beta赋为NGIF,PTIF { int i,j; int c[20][20]; int minmax; int b; int n=1; Tree tree; tree.data=NGIF; tree.Alpha=Alpha; tree.Beta=Beta; tree.X=0; tree.Y=0; if(a==1) b=2; else b=1; if(deep>0) { for(i=0;i<20;i++) for(j=0;j<20;j++) { if(co[i][j]==0&&jdgen(co,i,j,1)&&tree.Alpha<tree.Beta) { memcpy(c,co,sizeof(int)*400); c[i][j]=a; minmax=minMax(c,deep-1,b,tree.Alpha,tree.Beta); if(deep%2==0) { if(n==1) { tree.data=minmax; n++; } if(tree.Alpha<minmax) { tree.Alpha=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } else { if(n==1) { tree.data=minmax; n++; } if(tree.Beta>minmax) { tree.Beta=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } } } for(i=0;i<20;i++) for(j=0;j<20;j++) { if(co[i][j]==0&&jdgen(co,i,j,2)&&tree.Alpha<tree.Beta) { memcpy(c,co,sizeof(int)*400); c[i][j]=a; minmax=minMax(c,deep-1,b,tree.Alpha,tree.Beta); if(deep%2==0) { if(tree.Alpha<minmax) { tree.Alpha=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } else { if(tree.Beta>minmax) { tree.Beta=minmax; tree.data=minmax; tree.X=i; tree.Y=j; } } } } X=tree.X; Y=tree.Y; return tree.data; } else { return score(a,co,1); } } int* computer(int x) { int i,j; int *p=(int*)malloc(2*sizeof(int)); static int n=0; if(n==0) { for(i=0;i<20;i++) for(j=0;j<20;j++) n+=coord[i][j]; if(n==0) { p[0]=9; p[1]=9; return p; } n++; } minMax(coord,x,2,NGIF,PTIF); p[0]=X; p[1]=Y; return p; }
// HUMAN.c #include<stdio.h> extern int coord[20][20]; extern void location(int x,int y); extern void clearlocation(int x,int y); int* human() { static int X=9,Y=9; char h; int *p=(int*)malloc(2*sizeof(int)); location(X,Y); while(1) { if(kbhit()!=0) { h=getch(); clearlocation(X,Y); switch(h) { case 72://上 if(X>0) X--; break; case 80://下 if(X<19) X++; break; case 75://左 if(Y>0) Y--; break; case 77://右 if(Y<19) Y++; break; case 32://空格 if(coord[X][Y]==0) { p[0]=X; p[1]=Y; return p; } break; } location(X,Y); } } }