五⼦棋ai：极⼤极⼩搜索和α-β剪枝算法的思想和实现（qt和c++）（⼆）贪⼼算
我查了⼤量的⽹上资料，结合⾃⼰编程实践，⾛了很多弯路，总结了⼀些关于五⼦棋ai的经验以供⼤家参考借鉴。
⼀、贪⼼算法（相当于ai只思考⼀步的情况）
对于五⼦棋ai，⼤部分⼈想到的是做⼀个评估函数。这⾥的评估函数⽹上⼤概有两种，但是很多⼈会弄混淆。
第⼀种我称为K函数（只是⼀个代号，与第⼆种相区别），是对⼀个可⾛的空位⼦进⾏打分，如果ai⽩⼦落在这个空位置的分数越⾼，说明这个位置就越好，每次ai⾛棋就到⼀个最好的空位置就⾏了。 第⼆种我称为F函数，是对现在的棋盘局⾯进⾏打分。 ai⽩⼦⾸先所有可以⾛的空位置，模拟⾛了这个位置以后，⽤f函数进⾏局⾯评分，如果⾛了这样的⼀个空位置的得分越⾼，说明这个位置就越好，每次ai⾛棋就这样⼀个分数最⾼的位置。
那么你可能就要问了，这两个评估函数有什么区别呢？区别⾮常⼤！如果你只是想实现⼀个只看⼀步的a
i，那么你可以⽤K函数也可以⽤F函数。但是如果你想要实现基于博弈树的极⼤极⼩搜索和α-β剪枝算法的“聪明”ai，就只能⽤F函数，因为博弈树必须要对局⾯打分，⽽不是对位置打分。如果你明⽩了这⼀点，那么接下来就好办了。
⼆、评估函数（对⽩⼦⾛了⼀步的局⾯评估）
怎么对局势有⼀个⽐较准确的估计呢？我查阅了⼤量资料。五⼦棋的局势⽆⾮就是对棋型个数和权重的统计。（对某⼀⽅⽽⾔的） 五⼦棋棋型
我分为8种：
1.连5或者长连
2.活4（有两个位置可以形成连5）
3.冲4（有⼀个位置可以形成连5）
还有其他情况，⽐如边界，总之再下⼀步(只能是1步⽽不是2步)就能连5的就是冲4。 4.活3（⾛⼀步可以形成活4）
5.眠3（⾛⼀步可以形成冲4）
6.活2（⾛⼀步可以形成活3）：形状⾃⾏脑补
7.眠2（⾛⼀步可以形成眠3）
8.活1（⾛⼀步可以形成活2）
具体评分规则
我⽤六元组（⼀条直线上连续六个位置的状态）来表⽰棋型，通过检查棋盘上所有六元组来得分。最容易漏掉的地⽅是边界，⽐如如果⼀个斜线只有5个位置也有可能连5、但六元组没考虑进来等等问题，办法是⽤⼀个更⼤的、包括了边界的数组保存棋盘和边界信息。 1.六元组所有棋型辨识
⽤⼀个棋型辨识数组保存所有棋型。
#define C_NONE 0//棋⼦：⿊⼦,⽩⼦,⽆⼦
#define C_BLACK 1
#define C_WHITE 2
//棋型代号下标权重
#define OTHER 0//0，其他棋型不考虑
#define WIN 1//100000,⽩赢
#define LOSE 2//-10000000
#define FLEX4 3//50000,⽩活4
#define flex4 4//-80000
#define BLOCK4 5//400
#define block4 6//-80000
#define FLEX3 7//400
#define flex3 8//-8000
#define BLOCK3 9//20
#define block3 10//-40
#define FLEX2 11//20
#define flex2 12//-40
#define BLOCK2 13//1
#define block2 14//-2
#define FLEX1 15//1
#define flex1 16//-2徐妙锦
int tuple6type[4][4][4][4][4][4];//棋型辨识数组,0⽆⼦,1⿊⼦,2⽩⼦,3边界需要对这个数组进⾏初始化。
void chessAi::init_tuple6type(){
memset(tuple6type,0,sizeof(tuple6type));//全部设为0
金纳米粒子//⽩连5,ai赢
tuple6type[2][2][2][2][2][2]=WIN;
tuple6type[2][2][2][2][2][0]=WIN;
tuple6type[0][2][2][2][2][2]=WIN;
tuple6type[2][2][2][2][2][1]=WIN;
tuple6type[1][2][2][2][2][2]=WIN;
tuple6type[3][2][2][2][2][2]=WIN;//边界考虑
tuple6type[2][2][2][2][2][3]=WIN;
//⿊连5,ai输
tuple6type[1][1][1][1][1][1]=LOSE;
tuple6type[1][1][1][1][1][0]=LOSE;
tuple6type[0][1][1][1][1][1]=LOSE;
tuple6type[1][1][1][1][1][2]=LOSE;
tuple6type[2][1][1][1][1][1]=LOSE;
tuple6type[3][1][1][1][1][1]=LOSE;
tuple6type[1][1][1][1][1][3]=LOSE;
//⽩活4
tuple6type[0][2][2][2][2][0]=FLEX4;
//⿊活4
tuple6type[0][1][1][1][1][0]=flex4;
//⽩活3
tuple6type[0][2][2][2][0][0]=FLEX3;
tuple6type[0][0][2][2][2][0]=FLEX3;
tuple6type[0][2][0][2][2][0]=FLEX3;
tuple6type[0][2][2][0][2][0]=FLEX3;
//⿊活3
tuple6type[0][1][1][1][0][0]=flex3;
tuple6type[0][0][1][1][1][0]=flex3;
tuple6type[0][1][0][1][1][0]=flex3;
tuple6type[0][1][1][0][1][0]=flex3;
//⽩活2
tuple6type[0][2][2][0][0][0]=FLEX2;
tuple6type[0][2][0][2][0][0]=FLEX2;
tuple6type[0][2][0][0][2][0]=FLEX2;
tuple6type[0][0][2][2][0][0]=FLEX2;
tuple6type[0][0][2][0][2][0]=FLEX2;
tuple6type[0][0][0][2][2][0]=FLEX2;
/
/⿊活2
tuple6type[0][1][1][0][0][0]=flex2;
tuple6type[0][1][0][1][0][0]=flex2;
tuple6type[0][1][0][0][1][0]=flex2;
tuple6type[0][0][1][1][0][0]=flex2;
tuple6type[0][0][1][0][1][0]=flex2;
tuple6type[0][0][0][1][1][0]=flex2;
//⽩活1
tuple6type[0][2][0][0][0][0]=FLEX1;
tuple6type[0][0][2][0][0][0]=FLEX1;
tuple6type[0][0][0][2][0][0]=FLEX1;
tuple6type[0][0][0][0][2][0]=FLEX1;
//⿊活1
tuple6type[0][1][0][0][0][0]=flex1;
tuple6type[0][0][1][0][0][0]=flex1;
tuple6type[0][0][0][1][0][0]=flex1;
tuple6type[0][0][0][0][1][0]=flex1;
int p1,p2,p3,p4,p5,p6,x,y,ix,iy;//x：左5中⿊个数,y：左5中⽩个数,ix：右5中⿊个数,iy：右5中⽩个数
for(p1=0;p1<4;++p1){
for(p2=0;p2<3;++p2){
for(p3=0;p3<3;++p3){
for(p4=0;p4<3;++p4){
for(p5=0;p5<3;++p5){
for(p6=0;p6<4;++p6){
x=y=ix=iy=0;
if(p1==1)x++;
else if(p1==2)y++;
if(p2==1){x++;ix++;}
else if(p2==2){y++;iy++;}
if(p3==1){x++;ix++;}
else if(p3==2){y++;iy++;}
if(p4==1){x++;ix++;}
else if(p4==2){y++;iy++;}
if(p5==1){x++;ix++;}
else if(p5==2){y++;iy++;}
if(p6==1)ix++;
else if(p6==2)iy++;
if(p1==3||p6==3){//有边界
if(p1==3&&p6!=3){//左边界
//⽩冲4
if(ix==0&&iy==4){//若右边有空位是活4也没关系，因为活4权重远⼤于冲4，再加上冲4权重变化可以不计
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
爱立信r380tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK4;
}
//⿊冲4
if(ix==4&&iy==0){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block4;
}
//⽩眠3
if(ix==0&&iy==3){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK3;
}
//⿊眠3
if(ix==3&&iy==0){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block3;
}
//⽩眠2
if(ix==0&&iy==2){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK2;
}
//⿊眠2
if(ix==2&&iy==0){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block2;
}
}else if(p6==3&&p1!=3){//右边界
//⽩冲4
if(x==0&&y==4){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK4;
}
//⿊冲4
if(x==4&&y==0){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block4;
}
//⿊眠3
if(x==3&&y==0){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK3;
}
//⽩眠3
if(x==0&&y==3){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block3;
}
月台 艾雯
//⿊眠2
if(x==2&&y==0){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK2;
}
//⽩眠2
if(x==0&&y==2){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)蔡威廉
tuple6type[p1][p2][p3][p4][p5][p6]=block2;
}
}
}else{//⽆边界
//⽩冲4
if((x==0&&y==4)||(ix==0&&iy==4)){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK4;
}
//⿊冲4
if((x==4&&y==0)||(ix==4&&iy==0)){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block4;
}
//⽩眠3
if((x==0&&y==3)||(ix==0&&iy==3)){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=BLOCK3;
}
//⿊眠3
if((x==3&&y==0)||(ix==3&&iy==0)){
if(tuple6type[p1][p2][p3][p4][p5][p6]==0)
tuple6type[p1][p2][p3][p4][p5][p6]=block3;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议