基于博弈树和alpha-beta剪枝算法的五子棋ai优化版2.0
基于博弈树和alpha-beta剪枝算法的五子棋ai优化版2.0
0x00 好久不见
跟着《操作系统真象还原》动手写的项目已经到尾声了，我也准备开始c++ 计算机网络 和刷算法题了。动手做项目，心理比较踏实，掌握的也牢靠，这本书里非常好（可惜代码bug也不少，但这也强迫读者自己修复，必须理解才行）。偷一点时间，把五子棋代码优化了下，我觉得能下赢大部分人了，可惜室友是个bt，不过他也为我的优化提供了宝贵的建议。
0x01 代码
以下代码无第三方依赖，windows linux下均可直接编译。（小技巧，输入996 996可以悔棋）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>
#define mapsize 225
#define maplen 15
#define dddd 4//思考的层数，建议4层 多了太慢了，并且奇数层和偶数层的评估函数要不同
int map[mapsize];
int map_bak[mapsize];
typedef struct child* ch;
struct child{
int*map_array;
int map_cnt;
};
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");
}
static inline ch getchild(int data[maplen][maplen],int flag){
ch ret=(ch)malloc(sizeof(struct child));
ret->map_array=NULL;
ret->map_cnt=0;
int map_cnt=0;
int map_t[maplen][maplen];
memset(map_t,0,sizeof(map_t));
int i,j,k;
for(i=0;i<maplen;i++){
for(j=0;j<maplen;j++){
if(data[i][j]){
if(i-1>=0&&j-1>=0) map_t[i-1][j-1]=!data[i-1][j-1];
if(i-1>=0) map_t[i-1][j]=!data[i-1][j];
if(i-1>=0&&j+1<maplen) map_t[i-1][j+1]=!data[i-1][j+1];
if(j-1>=0) map_t[i][j-1]=!data[i][j-1];
if(j+1<maplen) map_t[i][j+1]=!data[i][j+1];
if(i+1<maplen&&j-1>=0) map_t[i+1][j-1]=!data[i+1][j-1];
if(i+1<maplen) map_t[i+1][j]=!data[i+1][j];
if(i+1<maplen&&j+1<maplen) map_t[i+1][j+1]=!data[i+1][j+1];
}
}
}
for(i=0;i<maplen;i++){
for(j=0;j<maplen;j++){
if(map_t[i][j]){
map_cnt++;
}
}
}
// printf("map_cnt %d\n",map_cnt);
ret->map_cnt=map_cnt;
ret->map_array=(int*)malloc(map_cnt*sizeof(int)*mapsize);
memset(ret->map_array,0,map_cnt*sizeof(int)*mapsize);
int* p=(int*)ret->map_array;
k=0;
for(i=0;i<maplen;i++){
for(j=0;j<maplen;j++){
if(map_t[i][j]){
memcpy(p+k*mapsize,data,sizeof(int)*mapsize);
*(p+k*mapsize+i*maplen+j)=flag;
k++;
}
}
}
return ret;
}
static inline int getvalue(int *data,int flag){
int i,j,k;
int val[5]={0,0,0,0,0}; //分别代表 1子 2 3 4 5子相连的个数
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-j):(i-j);
int y=(i+1)>maplen?(i+1-maplen+j):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]+=8;
}
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?(1-maplen+i+j):(j);
y=(i+1)>maplen?(j):(maplen-1+j-i);
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]+=8;
}
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]+=8;
}
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]+=8;
}
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]<<15)+(val[1]<<10)+(val[0]<<8)+(val[3]<<2);
else return (val[2]<<15)+(val[1]<<10)+(val[0]<<8)+(val[3]<<2);
}
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);
int i;
for(i=0;i<p->map_cnt;i++){
int tmp=maxmin(depth-1,p->map_array+i*mapsize,flag*(-1),a,b);
if(tmp>a) {
a=tmp;
if(a>b) break;
if(depth==dddd){
memcpy(data,p->map_array+i*mapsize,sizeof(int)*mapsize);
printf("电脑埋头苦算中：%d\n",a);
}
}
}
free(p->map_array);
free(p);
return a;
}else{
ch p=getchild(data,flag);
//printf("child cnt %d\n",p->map_cnt);
int i;
for(i=0;i<p->map_cnt;i++){
int tmp=maxmin(depth-1,p->map_array+i*mapsize,flag*(-1),a,b);
if(tmp<b) {
b=tmp;
if(a>b) break;
}
}
free(p->map_array);
free(p);
return b;
}
}
void getnextstep(int*a,int*b,int*map){
int i;
printf("your step,please:\n");
while(scanf("%d%d",a,b)!=2||*a<0||*a>=maplen||*b<0||*b>=maplen||map[*a*maplen+*b] ){
if(*a==996&&*b==996){
memcpy(map,map_bak,sizeof(int)*mapsize);
printf("go back once !!!\n");
print_map(map);
}else{
i=gets(NULL);
printf("输入有误！请重新输入位置x,y(从0-%d)\n",maplen-1);
}
}
memcpy(map_bak,map,sizeof(int)*mapsize);
}
int main(void){
// map[112]=1;
print_map(map);
while(1){
int x,y;
getnextstep(&x,&y,map);
map[x*maplen+y]=-1;
print_map(map);
if(getvalue(map,-1)>=32000){
printf("you win！\n");
}
maxmin(dddd,map,1,-100000,100000);
print_map(map);
if(getvalue(map,1)>=16000){
printf("ai win！\n");
}
}
return 0;
}
