logo资料库

人工智能 一字棋游戏代码.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：2.88M 资料格式：doc 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    班级：计算机 1105 姓名：李博扬 学号：20113248 人工智能期中作业 期中作业：一字棋编程 一字棋游戏规则如课堂讲授，下图为示例图： 要求： （1） 利用极大极小算法及a-b 剪枝策略，用你所熟悉的计算机语言， 编程解决上述一字棋问题。 （2） OPEN表中棋局排列次序：从左上到右下排列，即：（1，1）（1,2） （1,3）（2,1）（2,2）⋯⋯（3,2）（3,3） （3）根据深度 K=4 的程序运行结果，说明： 3.1 是否发生剪枝，发生几次 a 剪枝，几次 b 剪枝，分别列出 a， b 剪枝节点 3.2 截取程序运行结果的屏幕图片 程序清单： codeblocks12.11 g++编译器 Ubuntu 13.04 #include #include #include #include #include #include #include #include #include using namespace std; struct node //节点 {
    int mat[3][3]; //棋盘 int vis,value;//vis记录当前节点是否一游value int next;//当前节点选取的下一个节点 int pre;//当前节点的父亲节点 int id;//当前节点id int d;//当前节点的深度 }; int ans; int tot; int sum1,sum2; int suma,sumb;// a，b剪枝的次数 vector v; //记录所有节点 vector a,b; //记录a，b剪枝的节点 int s0[3][3]={1,2,3,10,20,30,100,200,300}; int s1[3][3]={1000,2000,3000,10000,20000,30000,100000,200000,300000}; int ok1(int mat[3][3],int x,int y) //判断mat【x】【y】是否是1 { } if(mat[x][y]==1||mat[x][y]==-1) return 1; return 0; int ok2(int mat[3][3],int x,int y)//判断mat【x】【y】是否是1 { } if(mat[x][y]==0||mat[x][y]==-1) return 1; return 0; int cal(int mat[3][3]) //计算某个节点的f函数 { int i,j,k; int sum1=0,sum2=0; for(i=0;i<3;i++) { } if(ok1(mat,i,0)&&ok1(mat,i,1)&&ok1(mat,i,2)) sum1++; if(ok2(mat,i,0)&&ok2(mat,i,1)&&ok2(mat,i,2)) sum2++; if(ok1(mat,0,i)&&ok1(mat,1,i)&&ok1(mat,2,i)) sum1++; if(ok2(mat,0,i)&&ok2(mat,1,i)&&ok2(mat,2,i)) sum2++; if(ok1(mat,0,0)&&ok1(mat,1,1)&&ok1(mat,2,2)) sum1++;
    if(ok2(mat,0,0)&&ok2(mat,1,1)&&ok2(mat,2,2)) sum2++; if(ok1(mat,0,2)&&ok1(mat,1,1)&&ok1(mat,2,0)) sum1++; if(ok2(mat,0,2)&&ok2(mat,1,1)&&ok2(mat,2,0)) sum2++; return sum2-sum1; } int get_value(int mat[3][3])//给每一个棋局都定义一个值，用来判断对称局的出现 { } int sum=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) { } if(mat[i][j]==0) sum+=s0[i][j]; else if(mat[i][j]==1) sum+=s1[i][j]; return sum; void sym1(int a[3][3],int b[3][3])//竖着对称 { } for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i][j]=a[i][2-j]; void sym2(int a[3][3],int b[3][3]) //横着对称 { } for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i][j]= a[2-i][j]; void sym3(int a[3][3],int b[3][3])// 左对角线对称 { } for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i][j]=a[j][i]; void sym4(int a[3][3],int b[3][3]) //右对角线对称 { for(int i=0;i<3;i++) for(int j=0;j<3;j++)
    b[i][j]=a[2-j][2-i]; } void sym5(int mat[3][3],int b[3][3])//旋转90 { } for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i][j]=mat[2-j][i]; void sym6(int mat[3][3],int b[3][3]) //180 { } for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i][j]=mat[2-i][2-j]; void sym7(int mat[3][3],int b[3][3])// 270 { } for(int i=0;i<3;i++) for(int j=0;j<3;j++) b[i][j]=mat[j][2-i]; int Visit(int mat[3][3],set &s) //判断一个棋盘的对称局是否曾经出现过 { } int b[3][3]; int sum = get_value(mat); if(s.find(sum)!=s.end()) return 1; return 0; int Insert(int mat[3][3],set &s) //如果某个棋盘没出现过，连同它的对称局一起放入set 中保存 { int b[3][3]; int sum = get_value(mat); if(s.find(sum)!=s.end()) return 1; s.insert(sum); sym1(mat,b); // a[get_value(b)]=1; s.insert(get_value(b)); sym2(mat,b); //a[get_value(b)]=1; s.insert(get_value(b));
    sym3(mat,b); //a[get_value(b)]=1; s.insert(get_value(b)); sym4(mat,b); // a[get_value(b)]=1; s.insert(get_value(b)); sym5(mat,b); s.insert(get_value(b)); sym6(mat,b); s.insert(get_value(b)); sym7(mat,b); s.insert(get_value(b)); return 0; } int dfs(node now) { set s; //用来保存now节点生成的是否出现的值 s.clear(); int i,j,k; int fa=0,fb=0; v.push_back(now); tot++; if(now.d==4) //深度为4，直接计算节点f值 { } now.value=cal(now.mat); now.vis=1; v[now.id]=now; return now.value; for(i=0;i<3;i++) for(j=0;j<3;j++) { node tmp=now; //生成新的节点 tmp.d++; tmp.pre=now.id; tmp.id=tot; tmp.vis=0; if(tmp.mat[i][j]==-1) { tmp.mat[i][j]=now.d%2;//先手放0，后手放1 if(Visit(tmp.mat,s)) //当前棋局出现过，跳过 {
    tmp.mat[i][j]=-1; continue; } if(fa) //now节点存在a剪枝 { } { } suma++; fa=fb=0; a.push_back(now); //cout<<"a:"<=p.value)//判断now节点是否可以 剪枝 //sumb++; //return now.value; fb=1; { } }
    else { { } if(now.vis&&now.value>tmp.value) //极小 now.value=tmp.value; now.next=tmp.id; v[now.id]=now; else if(!now.vis) now.value=tmp.value; now.next=tmp.id; now.vis=1; // cout<
    now.pre=0; ans=-1; sum1=sum2=0; suma=sumb=0; dfs(now);//对根节点进行dfs cout<<"alpha "<
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料