萌新也能写出的五子棋AI
RedLycoris · · 个人记录
萌新也能写出的五子棋AI
此五子棋，为无禁手五子棋简介
没错，这是一个十分简单的AI。即使你是个OI/五子棋萌新，只要你能够写代码，并且了解五子棋的规则，就能够写出这样有一定强度的AI。
首先，建立好一个棋盘。
你要写一个五子棋AI，就必须先有一个五子棋的棋盘。
我们可以定义一个类：
struct Gird{
int G[17][17];//None:0 Player:1 Computer:2 //15*15的棋盘
inline void init(){ //初始化棋盘
memset(G,0,sizeof(G));
for(int i=0;i<=16;++i)G[i][0]=3,G[i][16]=3; //设置边界
for(int i=0;i<=16;++i)G[0][i]=3,G[16][i]=3;
}
inline int check_row(int x,int y){ //判断是否是横着的5子赢了
if(y+4>15)return 0;
bool all=1;
for(int i=x,j=y;j<y+5;++j)if(G[i][j]!=G[x][y])all=0;
if(all==1 and G[x][y])return G[x][y];
return 0;
}
inline int check_col(int x,int y){ //判断是否是竖着的5子赢了
if(x+4>15)return 0;
bool all=1;
for(int i=x,j=y;i<x+5;++i)if(G[i][j]!=G[x][y])all=0;
if(all==1 and G[x][y])return G[x][y];
return 0;
}
inline int check_sla1(int x,int y){ //判断是否是斜向右下的5子赢了
if(x+4>15 or y+4>15)return 0;
bool all=1;
for(int i=x,j=y;i<x+5,j<y+5;++i,++j)if(G[i][j]!=G[x][y])all=0;
if(all==1 and G[x][y])return G[x][y];
return 0;
}
inline int check_sla2(int x,int y){ //判断是否是斜向左下的5子赢了
if(x+4>15 or y-4<1)return 0;
bool all=1;
for(int i=x,j=y;i<x+5,j>y-5;++i,--j)if(G[i][j]!=G[x][y])all=0;
if(all==1 and G[x][y])return G[x][y];
return 0;
}
inline int Count(){ //已经下了多少棋子
int cnt=0;
for(int i=1;i<=15;++i)for(int j=1;j<=15;++j)if(G[i][j]!=0)++cnt;
return cnt;
}
inline bool Draw(){ //全部铺满了（和棋）
return Count()==(15*15);
}
inline int Win(){ //判断棋盘上是否由一个人已经赢了
for(int i=1;i<=15;++i){
for(int j=1;j<=15;++j){
int T;
T=check_row(i,j);
if(T!=0)return T;
T=check_col(i,j);
if(T!=0)return T;
T=check_sla1(i,j);
if(T!=0)return T;
T=check_sla2(i,j);
if(T!=0)return T;
}
}
}
inline char Get(int x){ //判断棋子的种类
if(x==0)return '.';
if(x==1)return 'X';
if(x==2)return 'O';
}
inline void Print(int Turn){ //输出棋盘
system("cls");
cout<<"Turn To: "<<Get(Turn)<<'\n';
cout<<" 1 2 3 4 5 6 7 8 9 101112131415\n";
for(int i=1;i<=15;++i){
cout<<i<<" ";
if(i<10)cout<<" ";
for(int j=1;j<=15;++j)cout<<Get(G[i][j])<<" ";cout<<"\n";
}
}
};然后，我们可以写一个人VS人的对局测试一下棋盘。
inline void Player_to_player(){
int Now_Turn=1; //轮到谁了
Load();
system("cls");
Gird gird;
gird.init();
for(;!gird.Win();){ //对局继续
int x,y;
gird.Print(Now_Turn);
for(;;){
cout<<"Input where your chess put: \n";
cout<<"Line: ";cin>>x;cout<<'\n';
cout<<"Column: ";cin>>y;cout<<'\n';
if(x<=15 and y<=15 and x>=1 and y>=1 and !gird.G[x][y])break;
cout<<"Wrong Input!\nPlease enter it again.\n";
}
gird.G[x][y]=Now_Turn;
if(gird.Win()!=0){
cout<<gird.Get(Now_Turn)<<" wins!\n";
return;
}
Now_Turn=Next_Turn(Now_Turn); //换人
}
}
接下来就是核心的AI部分。
假设你没有任何的五子棋经验（像作者一样），你也可以想到一个最朴素的方法：
对于每一个新的局面，枚举下一个棋子放在了哪儿，使得放完后的局面的利益差最大。
我们定义利益为自己/敌人所有棋子的利益之和。
定义“活”为两头都为空的连续棋子。 如：..XXXX..
定义“死”为两头不是空的连续棋子。如：..OXXXO.
定义“冲”为一头为空，一头不为空的连续棋子。如：..OXXXX.
定义“空”为中间有一个断开、两头都为空的棋子。如：..XX.XX.
然后，对每一种状态设定一个参数，即为它带来的贡献。
每一种状态还有分两类：攻击时的，和防守时的。（这样可以防止盲目的攻击而不防守）
这个参数你不可能一下就确定，所以你需要在实战中不断的改善。
然后，我的AI采取的策略是“时候到了自然出手”。就是一开始先放手，到了中局将所有的攻击参数都乘上一个数。这样攻击的概率就会大一些了。
Code:
int zhihuo[2][6]={{0,5,25,84,15000000,15000000},{0,4,18,1500000,1500000,15000000}}; //0 先 1 后
int xiehuo[2][6]={{0,5,30,96,15000000,15000000},{0,4,24,1500000,1500000,15000000}};
int zhichong[2][6]={{0,2,20,42,390,15000000},{0,3,15,152,1500000,15000000}};
int xiechong[2][6]={{0,3,25,63,410,15000000},{0,3,15,115,1500000,15000000}};
int zhisi[2][6]={{0,1,15,15,155,15000000},{0,1,15,45,116,15000000}};
int xiesi[2][6]={{0,1,15,18,120,15000000},{0,1,15,59,128,15000000}};
int zhikong[2][6]={{0,4,32,145,395,15000000},{0,5,35,1500000,15000000,15000000}};
int xiekong[2][6]={{0,3,36,155,411,15000000},{0,3,40,1500000,15000000,15000000}}; //left+right
//huo
inline bool henzhihuo(Gird gird,int x,int y,int k){ //分类讨论 gird:棋盘 x,y : 初始点的位置 k:连续的长度
if(y+k>16)return 0;
bool all=1;
for(int i=x,j=y;j<y+k;++j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and (gird.G[x][y-1]==0) and (gird.G[x][y+k]==0))return 1;
return 0;
}
inline bool shuzhihuo(Gird gird,int x,int y,int k){
if(x+k>16)return 0;
bool all=1;
for(int i=x,j=y;i<x+k;++i)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and (gird.G[x-1][y]==0) and (gird.G[x+k][y]==0))return 1;
return 0;
}
inline bool xiaxiehuo(Gird gird,int x,int y,int k){
if(y+k>16 or y+k>16)return 0;
bool all=1;
for(int i=x,j=y;i<x+k and j<y+k;++i,++j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and (gird.G[x-1][y-1]==0) and (gird.G[x+k][y+k]==0))return 1;
return 0;
}
inline bool shangxiehuo(Gird gird,int x,int y,int k){
if(x+k>16 or y-k<0)return 0;
bool all=1;
for(int i=x,j=y;i<x+k and j>y-k;++i,--j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and (gird.G[x-1][y+1]==0) and (gird.G[x+k][y-k]==0))return 1;
return 0;
}
inline bool iszhihuo(Gird gird,int x,int y,int k){
return henzhihuo(gird,x,y,k) or shuzhihuo(gird,x,y,k);
}
inline bool isxiehuo(Gird gird,int x,int y,int k){
return shangxiehuo(gird,x,y,k) or xiaxiehuo(gird,x,y,k);
}
//chong
inline bool henzhichong(Gird gird,int x,int y,int k){
if(y+k>16)return 0;
bool all=1;
for(int i=x,j=y;j<y+k;++j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x][y-1]==0)+(gird.G[x][y+k]==0))==1)return 1;
return 0;
}
inline bool shuzhichong(Gird gird,int x,int y,int k){
if(x+k>16)return 0;
bool all=1;
for(int i=x,j=y;i<x+k;++i)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x-1][y]==0)+(gird.G[x+k][y]==0))==1)return 1;
return 0;
}
inline bool xiaxiechong(Gird gird,int x,int y,int k){
if(y+k>16 or y+k>16)return 0;
bool all=1;
for(int i=x,j=y;i<x+k and j<y+k;++i,++j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x-1][y-1]==0)+(gird.G[x+k][y+k]==0))==1)return 1;
return 0;
}
inline bool shangxiechong(Gird gird,int x,int y,int k){
if(x+k>16 or y-k<0)return 0;
bool all=1;
for(int i=x,j=y;i<x+k and j>y-k;++i,--j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x-1][y+1]==0)+(gird.G[x+k][y-k]==0))==1)return 1;
return 0;
}
inline bool iszhichong(Gird gird,int x,int y,int k){
return henzhichong(gird,x,y,k) or shuzhichong(gird,x,y,k);
}
inline bool isxiechong(Gird gird,int x,int y,int k){
return shangxiechong(gird,x,y,k) or xiaxiechong(gird,x,y,k);
}
//si
inline bool henzhisi(Gird gird,int x,int y,int k){
if(y+k>16)return 0;
bool all=1;
for(int i=x,j=y;j<y+k;++j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x][y-1]==0)+(gird.G[x][y+k]==0))==2)return 1;
return 0;
}
inline bool shuzhisi(Gird gird,int x,int y,int k){
if(x+k>16)return 0;
bool all=1;
for(int i=x,j=y;i<x+k;++i)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x-1][y]==0)+(gird.G[x+k][y]==0))==2)return 1;
return 0;
}
inline bool xiaxiesi(Gird gird,int x,int y,int k){
if(y+k>16 or y+k>16)return 0;
bool all=1;
for(int i=x,j=y;i<x+k and j<y+k;++i,++j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x-1][y-1]==0)+(gird.G[x+k][y+k]==0))==2)return 1;
return 0;
}
inline bool shangxiesi(Gird gird,int x,int y,int k){
if(x+k>16 or y-k<0)return 0;
bool all=1;
for(int i=x,j=y;i<x+k and j>y-k;++i,--j)if(gird.G[i][j]!=gird.G[x][y])all=0;
if(gird.G[x][y] and all and ((gird.G[x-1][y+1]==0)+(gird.G[x+k][y-k]==0))==2)return 1;
return 0;
}
inline bool iszhisi(Gird gird,int x,int y,int k){
return henzhisi(gird,x,y,k) or shuzhisi(gird,x,y,k);
}
inline bool isxiesi(Gird gird,int x,int y,int k){
return shangxiesi(gird,x,y,k) or xiaxiesi(gird,x,y,k);
}
//kong
inline bool henzhikong(Gird gird,int x,int y,int k){
if(y+k>15)return 0;
int all=2;
for(int i=x,j=y;j<y+k+1;++j)if(gird.G[i][j]==3-gird.G[x][y])all=0;else if(gird.G[i][j]==0)--all;
if(gird.G[x][y] and all==1 and ((gird.G[x][y-1]!=3-gird.G[x][y]) or (gird.G[x][y+k+1]!=3-gird.G[x][y])))return 1;
return 0;
}
inline bool shuzhikong(Gird gird,int x,int y,int k){
if(x+k>15)return 0;
int all=2;
for(int i=x,j=y;i<x+k+1;++i)if(gird.G[i][j]==3-gird.G[x][y])all=0;else if(gird.G[i][j]==0)--all;
if(gird.G[x][y] and all==1 and ((gird.G[x-1][y]!=3-gird.G[x][y]) or (gird.G[x+k+1][y]!=3-gird.G[x][y])))return 1;
return 0;
}
inline bool xiaxiekong(Gird gird,int x,int y,int k){
if(x+k>15 or y+k>15)return 0;
int all=2;
for(int i=x,j=y;i<x+k+1 and j<y+k+1;++i,++j)if(gird.G[i][j]==3-gird.G[x][y])all=0;else if(gird.G[i][j]==0)--all;
if(gird.G[x][y] and all==1 and ((gird.G[x-1][y-1]!=3-gird.G[x][y]) or (gird.G[x+k+1][y+k+1]!=3-gird.G[x][y])))return 1;
return 0;
}
inline bool shangxiekong(Gird gird,int x,int y,int k){
if(x+k>15 or y-k<1)return 0;
int all=2;
for(int i=x,j=y;i<x+k+1 and j>y-k-1;++i,--j)if(gird.G[i][j]==3-gird.G[x][y])all=0;else if(gird.G[i][j]==0)--all;
if(gird.G[x][y] and all==1 and ((gird.G[x-1][y+1]!=3-gird.G[x][y]) or (gird.G[x+k+1][y-k-1]!=3-gird.G[x][y])))return 1;
return 0;
}
inline bool iszhikong(Gird gird,int x,int y,int k){
return henzhikong(gird,x,y,k) or shuzhikong(gird,x,y,k);
}
inline bool isxiekong(Gird gird,int x,int y,int k){
return shangxiekong(gird,x,y,k) or xiaxiekong(gird,x,y,k);
}
inline pair<int,int> CountValue(Gird gird,pair<int,int>isxs){
int val[3];val[0]=0,val[1]=0,val[2]=0;
int xs[3];xs[1]=isxs.first;xs[2]=isxs.second;
for(int i=1;i<=15;++i){
for(int j=1;j<=15;++j){
for(int k=1;k<=5;++k){
if(gird.G[i][j]==0)continue;if(debug)cout<<i<<' '<<j<<' '<<k<<' '<<gird.G[i][j]<<'\n'; //养成debug的好习惯
if(iszhihuo(gird,i,j,k))val[gird.G[i][j]]+=zhihuo[xs[gird.G[i][j]]][k]; //依次判断每一种局面
if(isxiehuo(gird,i,j,k))val[gird.G[i][j]]+=xiehuo[xs[gird.G[i][j]]][k];
if(iszhichong(gird,i,j,k))val[gird.G[i][j]]+=zhichong[xs[gird.G[i][j]]][k];
if(isxiechong(gird,i,j,k))val[gird.G[i][j]]+=xiechong[xs[gird.G[i][j]]][k];
if(iszhisi(gird,i,j,k))val[gird.G[i][j]]+=zhisi[xs[gird.G[i][j]]][k];
if(isxiesi(gird,i,j,k))val[gird.G[i][j]]+=xiesi[xs[gird.G[i][j]]][k];
if(iszhikong(gird,i,j,k))val[gird.G[i][j]]+=zhikong[xs[gird.G[i][j]]][k];
if(isxiekong(gird,i,j,k))val[gird.G[i][j]]+=xiekong[xs[gird.G[i][j]]][k];
}
}
}
return mp(val[1],val[2]);
}
inline pair<int,int>GetCount(Gird gird,int xs){
if(xs==1)return CountValue(gird,mp(0,1));
else return CountValue(gird,mp(1,0));
}
inline pair<int,int>GoingToDie(Gird gird,int xs){
if(xs==1)return CountValue(gird,mp(0,1));
else return CountValue(gird,mp(1,0));
}
bool checked;
inline void Ck(Gird gird){
int cnt=0;
for(int i=1;i<=15;++i)for(int j=1;j<=15;++j)if(gird.G[i][j])++cnt;
if(cnt>=18)checked=1;
}
inline void check(Gird gird){ //该出手了
if(checked)return;
Ck(gird);
if(checked){ //
for(int i=1;i<=5;++i){
for(int j=0;j<2;++j){
zhihuo[j][i]*=4;
xiehuo[j][i]*=4;
zhichong[j][i]*=4;
xiechong[j][i]*=4;
zhisi[j][i]*=4;
xiesi[j][i]*=4;
zhikong[j][i]*=4;
xiekong[j][i]*=4;
}
}
}
}AI部分：
const int sma=2; //选择非最优解的概率(/32767)
const int smb=666; //同为最优解，替换当前最优解的概率(/32767)
const int Beg=7; //定义“开局”时放了多少棋子
inline bool Begin(Gird gird){ //是否是开局状态
int cnt=0;
for(int i=1;i<=15;++i)for(int j=1;j<=15;++j)if(gird.G[i][j]!=0)++cnt;
return cnt<=Beg;
}
inline bool First(Gird gird){ //最开始（防止一开始乱放）
int cnt=0;
for(int i=1;i<=15;++i)for(int j=1;j<=15;++j)if(gird.G[i][j]!=0)++cnt;
return cnt<=3;
}
inline Gird AI_esay(Gird gird){
check(gird);
pair<int,int>res;int mx=-2000000000;
res.first=0;res.second=0;
if(First(gird)){ //最开始
for(int i=6;i<=10;++i){
for(int j=6;j<=10;++j){ //限制放的位置
if(!gird.G[i][j]){
gird.G[i][j]=2;
pair<int,int>T=GetCount(gird,2);
if(gird.Win())return gird;
int delta=T.second-T.first;
if(T.second>1500000*(checked?4:1) and T.first<1500000)return gird; //AI完全可以赢了
if(delta>mx){ //更新最优解
mx=delta;
res=mp(i,j);
}else if(delta==mx){
if(rand()<smb){
mx=delta;
res=mp(i,j);
}
}else{
if(rand()<sma){
mx=delta;
res=mp(i,j);
}
}
gird.G[i][j]=0;
}
}
}
}else if(Begin(gird)){
//必须防守
for(int i=1;i<=15;++i){
for(int j=1;j<=15;++j){
if(!gird.G[i][j]){
gird.G[i][j]=2;
if(gird.Win()){
return gird;
}
pair<int,int>T=GetCount(gird,2);
int delta=T.second-T.first;
if(T.first>=1500000 and T.second<15000000){ //不行，敌人的进攻来了，必须防守
gird.G[i][j]=0;
continue;
}
if(T.second>1500000*(checked?4:1) and T.first<1500000)return gird;
if(delta>mx){
mx=delta;
res=mp(i,j);
}else if(delta==mx){
if(rand()<smb){
mx=delta;
res=mp(i,j);
}
}else{
if(rand()<sma){
mx=delta;
res=mp(i,j);
}
}
gird.G[i][j]=0;
}
}
}
gird.G[res.first][res.second]=2;
pair<int,int>P=GetCount(gird,2);
if(P.second-P.first==mx){
res=res;
}else{ //不必防守，还是在中间挑地方放
gird.G[res.first][res.second]=0;
for(int i=6;i<=10;++i){
for(int j=6;j<=10;++j){
if(!gird.G[i][j]){
gird.G[i][j]=2;
if(gird.Win()){
return gird;
}
pair<int,int>T=GetCount(gird,2);
int delta=T.second-T.first;
if(T.first>=1500000 and T.second<15000000){
gird.G[i][j]=0;
continue;
}
if(T.second>1500000*(checked?4:1) and T.first<1500000)return gird;
if(delta>mx){
mx=delta;
res=mp(i,j);
}else if(delta==mx){
if(rand()<smb){
mx=delta;
res=mp(i,j);
}
}else{
if(rand()<sma){
mx=delta;
res=mp(i,j);
}
}
gird.G[i][j]=0;
}
}
}
}
}else{ //非开局
for(int i=1;i<=15;++i){
for(int j=1;j<=15;++j){
if(!gird.G[i][j]){
gird.G[i][j]=2;
if(gird.Win()){
return gird;
}
pair<int,int>T=GetCount(gird,2);
int delta=T.second-T.first;
if(T.first>=1500000 and T.second<15000000){
gird.G[i][j]=0;
continue;
}
if(T.second>1500000*(checked?4:1) and T.first<1500000)return gird;
if(delta>mx){
mx=delta;
res=mp(i,j);
}else if(delta==mx){
if(rand()<smb){
mx=delta;
res=mp(i,j);
}
}else{
if(rand()<sma){
mx=delta;
res=mp(i,j);
}
}
gird.G[i][j]=0;
}
}
}
}
if(res.first==0 and res.second==0){ //必输，则随便挑一个最优的地方放了
for(int i=1;i<=15;++i){
for(int j=1;j<=15;++j){
if(!gird.G[i][j]){
gird.G[i][j]=2;
if(gird.Win()){
return gird;
}
pair<int,int>T=GoingToDie(gird,2);
int delta=T.second-T.first;
if(T.second>1500000*(checked?4:1) and T.first<1500000)return gird;
if(delta>mx){
mx=delta;
res=mp(i,j);
}else if(delta==mx){
if(rand()<smb){
mx=delta;
res=mp(i,j);
}
}else{
if(rand()<sma){
mx=delta;
res=mp(i,j);
}
}
gird.G[i][j]=0;
}
}
}
}
gird.G[res.first][res.second]=2;
return gird;
} 总结：
这个AI，没有用到任何的高深算法（如模拟退火，甚至连搜索都没有用），但是还是打过了百度上搜到的几个屑AI。
写这些AI，还是比写猪国杀之类的大模拟好多了，各位也去写一个吧！
整体代码(github，求star /cy)