实验二：利用α-β搜索过程的博弈树搜索算法编写一字棋游戏
一、实验目的与要求
（1）了解极大极小算法的原理和使用方法，并学会用α-β剪枝来提高算法的效率。
（2）使用C语言平台，编写一个智能井字棋游戏。
（3）结合极大极小算法的使用方法和α-β剪枝，让机器与人对弈时不但有智能的特征，而且计算的效率也比较高。
二、实验原理
一字棋游戏是一个流传已久的传统游戏。游戏由两个人轮流来下，分别用“X”和“O”来代替自身的棋子。棋盘分9个格，双方可以在轮到自己下的时候，可以用棋子占领其中一个空的格子。如果双方中有一方的棋子可以连成一条直线，则这一方判胜，对方判负。当所有的格子都被占领，但双方都无法使棋子连成一条直线的话，则判和棋。
这是一个智能型的一字棋游戏，机器可以模拟人与用户对弈。当轮到机器来下的时候，机器会根据当前棋局的形势，利用极大极小算法算出一个评价值，判断如何下才对自身最有利，同时也是对方来说对不利的，然后下在评价值最高的地方。另外利用α-β剪枝，使机器在搜索评价值的时候不用扩展不必要的结点，从而提高机器计算的效率。
在用户界面方法，用一个3×3的井字格来显示用户与机器下的结果。当要求用户输入数据的时候会有提示信息。用户在下的过程中可以中途按下“0”退出。当用户与计算机分出了胜负后，机器会显示出比赛的结果，并按任意键退出。如果用户在下棋的过程中，输入的是非法字符，机器不会做出反应。
三、实验步骤和过程
1.α-β搜索过程
在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？设某博弈问题如下图所示，应用极小极大方法进行搜索
MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。如图1中，其中一个MIN节点要全部生成A、B、C、D四个节点，然后还要逐个计算其静态估值，最后在求倒推值阶段，才赋
给这个MIN节点的倒推值－∞。其实，如果生成节点A后，马上进行静态估值，得知f（A）＝－∞之后，就可以断定再生成其余节点及进行静态计算是多余的，可以马上对MIN节点赋倒推值－∞，而丝毫不会影响MAX的最好优先走步的选择。这是一种极端的情况，实际上把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝，同样可获得类似的效果，这就是α-β过程的基本思想。
2.利用α-β搜索过程的一字棋的实例
图2一字棋第一阶段α-β剪枝方法
为了使生成和估值过程紧密结合，采用有界深度优先策略进行搜索，这样当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值。从图2中标记的节点生成顺序号（也表示节点编号）看出，生成并计算完第6个节点后，第1个节点倒推值完全确定，可立即赋给倒推值－1。这时对初始节点来说，虽然其他子节点尚未生成，但由于s属极大值层，可以推断其倒推值不会小于－1，我们称极大值层的这个下界值为α，即可以确定s的α＝－1。这说明s实际的倒推值决不会比－1更小，还取决于其他后继节点的倒推值，因此继续生成搜索树。当第8个节点生成出来并计算得静态估值为－1后，就可以断定第7个节点的倒推值不可能大于－1，我们称极小值层的这个上界值为β，即可确定节点７的β＝－1。有了极小值层的β值，很容易发现若α≥β时，节点7的其他子节点不必再生成，这不影响高一层极大值的选取，因s的极大值不可能比这个β值还小，再生成无疑是多余的，因此可以进行剪枝。这样一来，只要在搜索过程记住倒推值的上下界并进行比较，就可以实现修剪操作，称这种操作为α剪枝。类似的还有β剪枝，统称为α-β剪枝技术。在实际修剪过程中，α、β还可以随时修正，但极大值层的倒推值下界α永不下降，实际的倒推值取其后继节点最终确定的倒推值中最大的一个倒推值。而极小值层的倒推值上界β永不上升，其倒推值则取后继节点最终确定的倒推值中最小的一个倒推值。
2.1 在进行α-β剪枝时，应注意以下几个问题：
（1）比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点和极小节点间的比较是无意义的。
（2）在比较时注意是与"先辈层"节点比较，不只是与父辈节点比较。当然，这里的"先辈层"节点，指的是那些已经有了值的节点。
（3）当只有一个节点的"固定"以后，其值才能够向其父节点传递。
（4）α-β剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，α-β剪枝并没有因为提高效率，而降低得到最佳走步的可能性。
（5）在实际搜索时，并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。如果这样，
就失去了α-β剪枝方法的意义。在实际程序实现时，首先规定一个搜索深度，然后按照类似于深度优先搜索的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了。
2.2 α-β剪枝搜索过程(如图3)
在搜索过程中，假定节点的生成次序是从上到下，从左到右进行的。图中带圈的数字，表示节点的计算次序，在叙述时，为了表达上的方便，该序号也同时表示节点。当一个节点有两个以上的序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果。过程如下：
图3 α-β搜索过程的博弈树
图3给出一个d＝4的博弈树的α-β搜索过程，其中带圆圈的数字表示求静态估值及倒推值过程的次序编号。该图详细表示出α-β剪枝过程的若干细节。初始节点的最终倒推值为1，该值等于某一个端节点的静态估值。最好优先走步是走向右分枝节点所代表的棋局，要注意棋局的发展并不一定要沿着通向静态值为1的端节点这条路径走下去，这要看对手的实际响应而定。
2.3剪枝的效率问题
若以最理想的情况进行搜索，即对MIN节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），MAX先扩展最高估值的节点（设估计值从左向右递减排序），则当搜索树深度为D，分枝因数为B时，若不使用α-β剪枝技术，搜索树的端节点数；若使用α-β剪枝技术．可以证明理想条件下生成的端节点数最少，有
（D为偶数）
（D为奇数）
比较后得出最佳α-β搜索技术所生成深度为D处的端节点数约等于不用α-β搜索技术所生成深度为D／2处的端节点数。这就是说，在一般条件下使用α-β搜索技术，在同样的资源限制下，可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优势。
四、基于α-β剪枝的一字棋源代码
#include
using namespace std;
int num=0; //记录棋盘上棋子的个数
int p,q;
int tmpQP[3][3]; //表示棋盘数据的临时数组，其中的元素0表示该格为空，
int cur[3][3]; //存储当前棋盘的状态
const int depth=3; //搜索树的最大深度
void Init() //初始化棋盘状态
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cur[i][j]=0;
}
}
void PrintQP() //打印棋盘当前状态
{
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
cout< cout< } } void UserInput()//用户通过此函数来输入落子的位置，比如：用户输入31，则表示用户在第3行第1列落子。 { int pos,x,y; L1: cout<<"Please input your qizi (xy): "; cin>>pos; x=pos/10,y=pos%10; if(x>0&&x<4&&y>0&&y<4&&cur[x-1][y-1]==0) { cur[x-1][y-1]=-1; } else { cout<<"Input Error!"; goto L1; } } int CheckWin() //检查是否有一方赢棋（返回0：没有任何一方赢；1：计算机赢；-1：人赢） { //该方法没有判断平局 for(int i=0;i<3;i++) { if(cur[i][0]==1&&cur[i][1]==1&&cur[i][2]==1) { return 1; } if(cur[i][0]==-1&&cur[i][1]==-1&&cur[i][2]==-1) { return -1; } } for(i=0;i<3;i++) { if(cur[0][i]==1&&cur[1][i]==1&&cur[2][i]==1) { return 1; } if(cur[0][i]==-1&&cur[1][i]==-1&&cur[2][i]==-1) { return -1; } } if((cur[0][0]==1&&cur[1][1]==1&&cur[2][2]==1)||(cur[2][0]==1&&cur[1][1]==1&&cur[0][2]==1 )) { return 1; } if((cur[0][0]==-1&&cur[1][1]==-1&&cur[2][2]==-1)||(cur[2][0]==-1&&cur[1][1]==-1&&cur[0][2 ]==-1)) { return -1; } return 0; } int value()//评估当前棋盘状态的值（同时可以用p或q判断是否平局） { p=0; q=0; for(int i=0;i<3;i++) //计算机一方 { //将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1 for(int j=0;j<3;j++) { if(cur[i][j]==0) { tmpQP[i][j]=1; } else { tmpQP[i][j]=cur[i][j]; } } } for(i=0;i<3;i++) //计算共有多少连成3个1的行 { p+=(tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2])/3; } for(i=0;i<3;i++) //计算共有多少连成3个1的列 { p+=(tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i])/3; } p+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2])/3;//计算共有多少连成3个1的对角线 p+=(tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2])/3; for(i=0;i<3;i++) //人一方 { //将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1 for(int j=0;j<3;j++) { if(cur[i][j]==0) { tmpQP[i][j]=-1; } else { tmpQP[i][j]=cur[i][j]; } } } for(i=0;i<3;i++) //计算共有多少连成3个-1的行 { q+=(tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2])/3; } for(i=0;i<3;i++) //计算共有多少连成3个1的列 { q+=(tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i])/3; } q+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2])/3;//计算共有多少连成3个1的对角线 q+=(tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2])/3; return p+q; //返回评估出的棋盘状态的值 } int cut(int &val,int dep,bool max)//主算法部分，实现a-B剪枝的算法，val为上一层的估计值，dep 为搜索深度，max记录上一层是否为极大层 { if(dep==depth||dep+num==9) //如果搜索深度达到最大深度，或者深度加上当前棋子数已经达到9，就直接调用估计函数 { return value(); } int i,j,flag,temp; //flag记录本层的极值，temp记录下层求得的估计值 bool out=false; //out记录是否剪枝，初始为false /*if(CheckWin()==1) //如果计算机赢了，就置上一层的估计值为无穷（用很大的值代表无穷） { val=10000; return 0; }*/ if(max) //如果上一层是极大层，本层则需要是极小层，记录flag为无穷大；反之，则为记录为负无穷大 { flag=10000; //flag记录本层节点的极值 } else { flag=-10000; } for(i=0;i<3 && !out;i++) //双重循环，遍历棋盘所有位置 { for(j=0;j<3 && !out;j++) { if(cur[i][j]==0) //如果该位置上没有棋子 { if(max) //并且上一层为极大层，即本层为极小层,轮到用户玩家走了。 { cur[i][j]=-1; //该位置填上用户玩家棋子 if(CheckWin()==-1) //如果用户玩家赢了 { temp=-10000; //置棋盘估计值为负无穷 } else { temp=cut(flag,dep+1,!max); //否则继续调用a-B剪枝函数 } if(temp { flag=temp; } if(flag<=val) //如果本层极值已小于上一层的估计值，则不需搜索下去，剪枝 { out=true; } } else //如果上一层为极小层，即本层为极大层,轮到计算机走了。 { cur[i][j]=1; //该位置填上计算机棋子 if(CheckWin()==1) //如果计算机赢了 { temp=10000; //置棋盘估计值为无穷 } else { temp=cut(flag,dep+1,!max);//否则继续调用a-B剪枝函数 } if(temp>flag) { flag=temp; } if(flag>=val) { out=true; } } cur[i][j]=0; //把模拟下的一步棋还原，回溯 } } } if(max) //根据上一层是否为极大层，用本层的极值修改上一层的估计值 { if(flag>val) { val=flag; } } else { if(flag { val=flag; } } return flag; //函数返回的是本层的极值 } int main()//主程序 { int m=-10000,val=-10000,dep=1; //m用来存放最大的val int x_pos,y_pos; //记录最佳走步的坐标 Init(); cout<<"Qipan: "< PrintQP(); char IsFirst; cout<<"Do you want do first?(y/n)"; cin>>IsFirst; while(IsFirst!='y'&&IsFirst!='n') { cout<<"ERROR!"<<"Do you want do first?(y/n)"; cin>>IsFirst; } if(IsFirst=='n')//---------------------------------计算机先走-------------------------------------- { L5: for(int x=0;x<3;x++) { for(int y=0;y<3;y++) { if(cur[x][y]==0) { cur[x][y]=1; cut(val,dep,1);//计算机试探的走一步棋，棋盘状态改变了，在该状态下计算出深度为dep-1的棋盘状态估计值val if(CheckWin()==1) { cout<<"The computer put the qizi at:"< PrintQP(); cout<<"The computer WIN! GAME OVER."< return 0; } if(val>m) //m要记录通过试探求得的棋盘状态的最大估计值 { m=val; x_pos=x;y_pos=y; } val=-10000; cur[x][y]=0; } } } cur[x_pos][y_pos]=1; val=-10000; m=-10000; dep=1; cout<<"The computer put the qizi at:"< PrintQP(); cout< num++; value(); if(p==0) { cout<<"DOWN GAME!"< return 0; } UserInput(); //玩家走一步棋 PrintQP(); cout< num++; value(); if(p==0) { cout<<"DOWN GAME!"< return 0; } if(CheckWin()==-1) { cout<<"Conguatulations! You Win! GAME OVER."< return 0; } goto L5; } else //--------------------------------人先走----------------------------------- { L4: UserInput(); PrintQP(); cout< num++; value(); if(q==0) { cout<<"DOWN GAME!"< return 0; } if (CheckWin()==-1) { cout<<"You Win! GAME OVER."< return 0; } for(int x=0;x<3;x++) { for(int y=0;y<3;y++) { if(cur[x][y]==0) { cur[x][y]=1; cut(val,dep,1); if(CheckWin()==1) { cout<<"The computer put the qizi at:"< PrintQP(); cout<<"The computer WIN! GAME OVER."< return 0; } if(val>m) { m=val; x_pos=x;y_pos=y; } val=-10000; cur[x][y]=0; } } } cur[x_pos][y_pos]=1; val=-10000; m=-10000; dep=1; cout<<"The computer put the qizi at:"< PrintQP(); cout< num++; value(); if(q==0) { cout<<"DOWN GAME!"< return 0; } goto L4; } return 0; } 五实验数据 六实验心得 通过本次试验，初步了解了博弈树算法的基本过程，知道了博弈树算法的原理与步骤，能简单的运用它来设计棋牌游戏，了解极大极小算法的原理和使用方法，并学会用α-β剪枝来提高算法的效率。对一些简单的棋牌游戏能大概上看懂它们的运行过程。在编程序的过程中，我们也遇到了很多困难，比如，对这新知识的不熟练，掌握的不够好，有些问题不能很好的理解，但经过我们的努力，最终还是能很好的解决了。 五子棋JAVA实验报告 目录 五子棋JA V A实验报告 (1) 一、实验目的和要求 (2) 二、五子棋的基本常识与原理 (2) 三、五子棋的系统设计 (3) 四、五子棋的实现与测试 (7) 五、分析与总结 (10) 六、附录 (12) 一、实验目的和要求 1、能够用编程语言实现一个简单的五子棋程序 2、在实际系统中使用、实现人工智能的相关算法 3、进一步加深对人工智能算法的理解 二、五子棋的基本常识与原理 1、五子棋的起源 五子棋，是一种两人对弈的纯策略型棋类游戏，亦称“串珠”、“连五子”；是中国民间非常熟知的一个古老棋种。相传，它起源于四千多年前的尧帝时期，比围棋的历史还要悠久。亦有传说，五子棋最初流行于少数民族地区，以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。 五子棋发展于日本，流行于欧美。容易上手，老少皆宜，而且趣味横生，引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。 传统五子棋的棋具与围棋相同，棋子分为黑白两色，棋盘为19X19，棋子放置于棋盘线交叉点上。两人对局，各执一色，轮流下一子，先将横、竖或斜线的5个或5个以上同色棋子连成不间断的一排者为胜。因为传统五子棋在落子后不能移动或拿掉，所以也可以用纸和笔来进行游戏。 2、五子棋的基本常识 与任何一种竞技棋一样，五子棋的每一局棋也分为三个阶段：开局，中局和残局。 五子棋的开始阶段称为开局，或称布局。其开局阶段是十分短暂的，大约在七着与十几着之间。在这一阶段的争夺中，双方的布局，应对将对以后的胜负起着极为关键的作用。在开局阶段取得的形势好坏，主动与被动，先手与后手的优劣程度，往往直接影响中局的战斗。因此积极处理好开局和开局向中局的过渡十分重要。 五子棋是从一至五，逐渐布子，发展连系，同时运用限制和反限制的智慧，在连子的过程中为自己的棋子争得相对的主动权和优势，逐步扩展优势，或者从劣势转化为优势，击溃对方的防线，最后连五取胜或抓禁手取胜或迫使对方投子认负。 3、五子棋比赛的相关规定 (1) 职业连珠规则 a. 黑方先下子，白后下，从天元开始相互顺序落子。 b. 最先在棋盘横向、竖向、斜向形成连续的相同色五个棋子的一方为胜。 c. 黑棋禁手判负，白棋无禁手。黑棋禁手包括“三三”(包括“四三三”)、“四四”(包括“四四三”)、 人工智能实验报告大 全 人工智能课内实验报告 （8次） 学院：自动化学院 班级：智能1501 姓名：刘少鹏（34） 学号： 06153034 目录 课内实验1：猴子摘香蕉问题的VC编程实现 (1) 课内实验2：编程实现简单动物识别系统的知识表示 (5) 课内实验3：盲目搜索求解8数码问题 (18) 课内实验4：回溯算法求解四皇后问题 (33) 课内实验5：编程实现一字棋游戏 (37) 课内实验6：字句集消解实验 (46) 课内实验7：简单动物识别系统的产生式推理 (66) 课内实验8：编程实现D-S证据推理算法 (78) 人工智能课内实验报告实验1：猴子摘香蕉问题的VC编程实现 学院：自动化学院 班级：智能1501 姓名：刘少鹏（33） 学号： 06153034 日期： 2017-3-8 10:15-12:00 实验1：猴子摘香蕉问题的VC编程实现 一、实验目的 （1）熟悉谓词逻辑表示法； （2）掌握人工智能谓词逻辑中的经典例子——猴子摘香蕉问题的编程实现。 二、编程环境 VC语言 三、问题描述 房子里有一只猴子（即机器人），位于a处。在c处上方的天花板上有一串香蕉，猴子想吃，但摘不到。房间的b处还有一个箱子，如果猴子站到箱子上，就可以摸着天花板。如图1所示，对于上述问题，可以通过谓词逻辑表示法来描述知识。要求通过VC语言编程实现猴子摘香蕉问题的求解过程。 图1 猴子摘香蕉问题 四、源代码 #include 人工智能αβ剪枝实现的一字棋实验报告 The document was prepared on January 2, 2021 实验5： -剪枝实现一字棋 一、实验目的 学习极大极小搜索及 - 剪枝算法实现一字棋。 二、实验原理 1.游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋" 的棋盘很简单，是一个 3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 2.极小极大分析法 设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就 用圆圈表示 MAX，用叉号代表 MIN 比如左图中就是 MAX 取胜的棋局。 估价函数定义如下设棋局为 P，估价函数为 e(P)。 (1) 若 P 对任何一方来说都不是获胜的位置，则 e(P)=e(那些仍为 MAX 空着的完全的行、列或对角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数) (2) 若 P 是 MAX 必胜的棋局，则 e(P)＝+ （实际上赋了 60）。 (3) 若 P 是 B 必胜的棋局，则 e(P)＝- （实际上赋了-20）。 e(P)=5-4=1 需要说明的是，+赋60，-赋-20的原因是机器若赢了， 则不论玩家下一步是否会赢，都会走这步必赢棋。 3. -剪枝算法 上述的极小极大分析法，实际是先生成一棵博弈树，然后 再计算其倒推值，至使极小极大分析法效率较低。于是在极 小极大分析法的基础上提出了- 剪枝技术。 - 剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1) 对于一个与节点 MIN，若能估计出其倒推值的上确界，并且这个值不大于MIN 的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该MIN 节 五子棋实训报告 五子棋实训报告 篇一： （3）棋子的绘制与存储棋子的绘制用实心圆模式，颜色为黑色及 白色两种。 棋子在内存中的存储方式： 因为表示各个棋子的数据类型都相同，所以考虑用数组存储，因 为棋盘是二维的，因此棋子用二维数组a存储。 a{ setTitle{ Objet obj = e.getSoure } toolbar = ne JPanel{ } publi int getX{ } publi int getY{ } publi Color getColor{ } return olor; return ; return x; this.x = x; this. = ; this.olor = olor;篇 四： 实习报告-五子棋 信息工程学院 201X年毕业实习报告 班级： 计科XX 姓名： XXX 实习地点： XXXXXX 实习12周-19周 一、实习目的 1. 夯实专业基础，提高动手能力。 把专业知识应用于实践，找出专业薄弱环节加强巩固。 3. 了解就业单位的计算机技术的应用情况、需求情况和发展方向及前景，培养实践能力、分析问题和解决问题的能力以及综合运用所学基础知识和基本技能的能力，同时也增强了适应社会的能力和就业竞争力。 4. 挖掘自身潜力，寻找自身不足，通过实践对未来做出合理规划。 二、实习任务 在MElipse的平台上运用java语言，学习开发一个常用小游戏：五子棋。 三、实习计划 5. 基础夯实，联系实践。 在信息高速发展的今天，计算机科学技术的重要性也在人们的日常生活中日益突显。不管是从事理论教学还是从事软件的设计和开发，基础都是最有力的保障。思想决定行动，认识决定成败。没有正确的思想作为指导，行动就会陷入盲目和被动。缺乏正确的认识基础，前途就会迷茫，方向就会迷失，机会就会丧失。所以说，理论学习是我增强行动自觉的重要保证。人常说:“经济基础决定上层建筑”专业基础对我来说就是经济基础，而上层建筑就是我们所从事的相关工作。但是只拥有专业基础还是不行的，所以，我必须要把理论应用于实践。这也是此次实习课程的重要所在，以专业基础知识为重要依托，以专 西南交通大学 程序语言综合课程设计 五子棋游戏 课程《程序语言综合课程设计》 学院信息科学与技术学 专业软件工程 姓名 学号 20119050 日期 2016年月日 目录 第一章课程设计的目的和要求 (3) 1.1 课程设计的目的 (3) 1.2 课程设计的要求 (3) 1.3 课程设计的实验环境 (3) 第二章功能描述 (4) 第三章总体设计 (5) 3.1 功能模块设计 (5) 3.1.1 任务执行流程图 (5) 3.1.2 下棋函数流程图 (6) 3.2 数据结构设计 (7) 3.2.1 定义结构体 (7) 3.2.2 定义数组 (7) 3.2.3 全局变量 (7) 3.3 函数功能描述 (7) 第四章程序实现 (8) 4.1源码分析 (8) 4.2运行结果及界面介绍 (25) 第五章后记 (30) 第一章课程设计的目的和要求 1.1 课程设计的目的 1.加深对C语言数据类型，运算，语句结构及其程序设计的基本方法理解和掌握； 2.熟练掌握流程图的绘制、程序设计文档的书写； 3.通过编写一个完整的程序，一方面可以检查我们这学期的学习情况，为以后的学习打下坚实的基础； 4.熟悉C语言游戏编程，掌握五子棋游戏开发的基本原理，从而为以后的程序开发奠定基础。 1.2 课程设计的要求 1、编写程序代码，调试所写程序使其能够正确运行； 2、能进行基本的五子棋操作，有图形界面，能够用键盘操作； 3、能够实现悔棋、存档和读档等附加功能 1.3 课程设计的实验环境 该课程设计在设计与实验过程中需要在windows XP系统/windows 2000以上系统中进行，程序设计要求在visual C++6.0平台中进行，完成代码的编写、编译、调试、测试等工作。本游戏对计算机硬件和操作系统要求极低，所以在这里只是把自己的电脑硬件参数和系统参数列下： 硬件：Cpu:2.1GHZ，内存，2GB，硬盘：320GB，操作系统：windows xp 软件环境：安装VC++6.0 实验5：? -?剪枝实现一字棋 一、实验目的 学习极大极小搜索及?-?剪枝算法实现一字棋。 二、实验原理 1.游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋" 的棋盘很简单，是一个 3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 2.极小极大分析法 设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就 用圆圈表示 MAX，用叉号代表 MIN 比如左图中就是 MAX 取胜的棋局。 估价函数定义如下设棋局为 P，估价函数为 e(P)。 (1) 若 P 对任何一方来说都不是获胜的位置，则 e(P)=e(那些仍为 MAX 空着的完全的行、列或对角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数) (2) 若 P 是 MAX 必胜的棋局，则 e(P)＝+?（实际上赋了 60）。 (3) 若 P 是 B 必胜的棋局，则 e(P)＝-?（实际上赋了-20）。 e(P)=5-4=1 需要说明的是，+?赋60，-?赋-20的原因是机器若赢了， 则不论玩家下一步是否会赢，都会走这步必赢棋。 3. ? -?剪枝算法 上述的极小极大分析法，实际是先生成一棵博弈树，然后 再计算其倒推值，至使极小极大分析法效率较低。于是在极小 极大分析法的基础上提出了?-?剪枝技术。 ? -?剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1) 对于一个与节点 MIN，若能估计出其倒推值的上确界?，并且这个?值不大于 MIN 的父节点(一定是或节点)的估计倒推值的下确界?，即???，则就不必再扩展 五子棋游戏实验报告 课程名称计算机程序设计(VB) 学号______________________ 姓名______________________ 班级______________________ 提交时间 五子棋软件设计 一、实验目的 1?通过五子棋软件设计或者自拟题目设计，巩固本课程所学的各个章节重点知识，自拟题目的同学需尽早向教师提岀自己的想法及设计方案。 2?通过开发一个较大的系统，增强软件开发能力。 3?通过调试系统，增强逻辑思维能力。 二、实验内容 1.基本要求： (1)输入两个对手名字，然后进入游戏界面。 (2)用鼠标点击的方式在棋盘上摆放棋子，黑白交替。(棋盘15*15 ) (3)可以悔棋。 (4)五子连在一起的时候能判断胜利，并且显示出胜利者的名字。 (5)能够将棋局的结果保存，保存该棋局 结束的状态、对手名字、棋局名字(棋局名字在保存时由用户在相应的界面下添入)(此功能要求用数据库和文件两种技术实现)。 因为棋盘上空点居多，大部分点的信息为0,因此只需保存有棋子的点的信息 用文件技术进行棋局保存，思路相同。 （7）五子棋恢复棋局 思路：首先从数据库文件中找到要恢复棋局的数据（即曾经保存的数据），然后把这些数据赋值给内存中相应的数组或者变量中，按照这些数据重新绘制棋盘和棋子，即完成了对棋局的恢复。 窗体启动事件应该完成的事情： 组合框中应该显示曾经保存的棋局名。因为每次保存棋局时，都是将棋局所有棋子的记录添加在表的最 后，因此表中关于棋局名的记录只能是类似于aaabbbbccccc的形式，而不可能是abbcacc的形式，根据 这个特点编程序取出表中不同的棋局名。 具体算法： 用一个字符串变量strfile初始值为空，从表的顶端向下依次移动记录指针，如果当前记录的棋局名字段和strfile不相等，说明进入另一个棋局的记录中，将该棋局记录的棋局名赋值给strfile，并加入到组合 框中，一直到表中最后一个记录 因为要从数据库中取岀相关数据到a数组中，因此要将a数组所有数据清零。 要建立一个data控件，与数据库连接起来，而后识别棋局（即表中的棋局名字段与在列表框中选择的棋 局名比较），将数据库该棋局中所有信息都赋值给a数组及相关变量。 刚才仅仅是数据的恢复，即将数据库中已经保存过的数据恢复到内存中，下一步应该根据内存中的数据重新绘制棋盘以及棋子。 重新绘制棋盘是独立的一块功能，因此考虑用全局子过程来实现，该子过程定义在模块中。思路如下： 清屏一绘制棋盘一根据a数组中的每一项的两个下标来决定绘制棋子的位置，根据每一项的值是1还是 2来决定在该位置绘制何颜色的棋子。 决定该黑白方走的blackwhite变量当时没有保存，可以采用在数据库中保存的方式来解决，本例中解决方法是通过数黑白棋子个数来决定恢复棋局后该谁走的。 因此设置了一个变量做计数器，每走一步棋计数器的值加一。 用文件技术实现棋局恢复，思路相同。 （8）悔棋 悔一步棋：用几个变量来表示关于一步棋的几个信息，每次下子都将该子的信息赋值给那几个变量，悔 一步棋即将那几个变量所表示的点的a数组信息清零。而后调用paint （）过程重画。 以上是教师带着学生完成的软件功能。 遗留问题：保存棋手姓名和棋局名并在恢复棋局的时候显示。（需要同学们自己完成）思路：在数据表中多建立两个字段，分别表示两个棋手姓名，同其它数据的保存类似。 三、设计日期 十二月 四、完成日期 十二月 五、实验体会 其实，一开始学习vb我就对它不抱有一定的热情，可能是因为要用到计算机以及编程问题，当时一想到有代码，就会无比的苦恼，但是为了让这门课顺利通过，我还是怀着一颗必须要学的心情。起初，我对待这门新课程和其他课 、实验目的 学习极大极小搜索及〉「 剪枝算法实现一字棋 、实验原理 1. 游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。 "井字棋"的棋盘很简单，是一个 3X 3的格子，很像中国文字中的"井"字，所 以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是 一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 2. 极小极大分析法 设有九个空格，由 MAX ，MIN 二人对弈，轮到谁走棋谁就往空格上放一 只自己的棋子，谁先使自己的棋子构成 "三子成一线"（同一行或列或对角线全是 用圆圈表示 MAX ，用叉号代表 MIN 比如左图中就是MAX 取胜的棋局。 估价函数定义如下设棋局为 P,估价函数为 （1） 若P 对任何一方来说都不是获胜的位置，贝U e （P ）=e （那些仍为MAX 空 着的完全的行、列或对角线的总数）-e （那些仍为MIN 空着的完全的行、列或对 角线的总数） （2） 若P 是MAX 必胜的棋局，则 e （P ）= +：：（实际上赋了 60）。 ⑶ 若P 是B 必胜的棋局，则e （P ）=-：：（实际上 赋了 -20） e(P)=5-4=1 需要说明的是，赋60,二赋-20的原因是机器 若赢 了，则不论玩家下一步是否会赢，都会走这步必 赢棋。 3. =-［剪枝算法 实验5:: 八剪枝实现一字棋 e(P)。 某人的棋子），谁就取得了胜 比如P 如下图示，则 上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了剪枝技术。 a邛剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1) 对于一个与节点MIN，若能估计出其倒推值的上确界［，并且这个1值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界「，即、；_「：，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为:-剪枝。 (2) 对于一个或节点MAX，若能估计出其倒推值的下确界:,并且这个: 值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界［，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX 父节点的倒推值已无任何影响了)。这一过程称为一：剪枝。 从算法中看到： (1) MAX节点(包括起始节点)的〉值永不减少； (2) MIN节点(包括起始节点)的一：值永不增加。 在搜索期间，〉和一：值的计算如下： (1) 一个MAX节点的:-值等于其后继节点当前最大的最终倒推值。 (2) 一个MIN节点的一：值等于其后继节点当前最小的最终倒推值。 4. 输赢判断算法设计 因为每次导致输赢的只会是当前放置的棋子，输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。 (此文档为word格式，下载后您可任意编辑修改！) 一、需求分析 1.1开发背景 电脑游戏行业经过二十年的发展，已经成为与影视、音乐等并驾齐驱的全球最重要的娱乐产业之一，其年销售额超过好莱坞的全年收入。互联网的出现为电脑游戏行业发展注入了新的活力，凭借信息双向交流、速度快、不受空间限制等优势，让真人参与游戏，提高了游戏的互动性、仿真性和竞技性，使玩家在虚拟世界里可以发挥现实世界无法展现的潜能，改变了单机版游戏固定、呆板、与机器对话的状况。网络游戏的这些优势不仅使其在电脑游戏行业中异军突起并在某种程度上取代了单机版游戏，而且成为网络业三大（网上金融、网上教育和网络游戏）赢利且利润优厚的领域之一。 网络作为一种新兴的传播方式，主要包括三大内容：娱乐、资讯、通讯。提到网络娱乐，过去主要指的是单机版游戏，没有引入网络的概念但随着科技的发展，游戏娱乐产业也在成长目前，国内的游戏娱乐产业正处于起步阶段，特点表现为：第一，它是一种文化的传播。娱乐产业可以潜移默化地改变人的观念，当前，很多多媒体的播放已被电脑网络所取代。第二，网络游戏加强了人与人的沟通。第三，网络游戏具有一定的教育意义。网络游戏所具有的角色扮演的功能，使得玩家能通过互助更好地完成游戏中的各项任务。网络无国界，游戏在网络文化产业世界的发展中地位会越来越高。 目前在国外，休闲游戏如棋类等，玩家的年龄跨度非常大，这和我国目前网游市场以青少年为主要消费人群的状况截然不同。其实，网络可以解决空间的问题，网络和生活越来越息息相关，因此，开辟适合各个年龄层的游戏产品迫在眉睫。同时，这也涉及到一个企业开发的能力。娱乐产业发展到一定程度，通过不断锻炼和经验的积累，完全可以通过融入娱乐的成分把教条的东西深入浅出地展现给消费者。 就国内的发展来看，最近這两三年内国内的游戏公司如雨后春笋般的成立，所开发或代理的网络游戏更是不胜枚举。以全球游戏业界的发展来看，這几年韩国的表现最为突出，特別是在网络游戏的技术研发兴游戏制作，其所发行的网络游戏更成为全球游戏产业重要的指标之一。去年在美国洛杉矶所举行的 E3（Electronic Entertainment Exposition）展中，已经有几家的韩国厂商挤入世界第一线的游戏开发厂商之列。 近几年来，由于 3D 硬体绘图技术的突破，使得即时描绘的书面越来越精致，而且3D遊戏性更多元化更逼近真实世界，因此在遊戏产业中，3D 游戏已经逐渐取代2D游戏为游戏市场的主流，即使是网络游戏，也慢慢趋向3D化。然而游戏3D化将会带来的游戏开发上的困难等问题，这些问题以后都需要逐步解决。 人们面对电脑的时间越来越多，面对身边的人的时间越来越少，所以我们游戏所要达到的目的就是加大人们之间的沟通，让大家随时随地都可以体验到玩游戏的乐趣。而三子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。同样的，通过这个游戏，既能在休闲时刻娱乐一下，也能在压力面临的时候放松一刻。 人工智能课内实验报告 （8次） 学院：自动化学院 班级：智能1501 姓名：刘少鹏（34） 学号： 06153034 目录 课内实验1：猴子摘香蕉问题的VC编程实现 (1) 课内实验2：编程实现简单动物识别系统的知识表示 (5) 课内实验3：盲目搜索求解8数码问题 (18) 课内实验4：回溯算法求解四皇后问题 (33) 课内实验5：编程实现一字棋游戏 (37) 课内实验6：字句集消解实验 (46) 课内实验7：简单动物识别系统的产生式推理 (66) 课内实验8：编程实现D-S证据推理算法 (78) 人工智能课内实验报告实验1：猴子摘香蕉问题的VC编程实现 学院：自动化学院 班级：智能1501 姓名：刘少鹏（33） 学号： 06153034 日期： 2017-3-8 10:15-12:00 实验1：猴子摘香蕉问题的VC编程实现 一、实验目的 （1）熟悉谓词逻辑表示法； （2）掌握人工智能谓词逻辑中的经典例子——猴子摘香蕉问题的编程实现。 二、编程环境 VC语言 三、问题描述 房子里有一只猴子（即机器人），位于a处。在c处上方的天花板上有一串香蕉，猴子想吃，但摘不到。房间的b处还有一个箱子，如果猴子站到箱子上，就可以摸着天花板。如图1所示，对于上述问题，可以通过谓词逻辑表示法来描述知识。要求通过VC语言编程实现猴子摘香蕉问题的求解过程。 图1 猴子摘香蕉问题 四、源代码 #include 实验5：α-β剪枝实现一字棋 一、实验目的 学习极大极小搜索及α-β剪枝算法实现一字棋。 二、实验原理 1.游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋" 的棋盘很简单，是一个 3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 2.极小极大分析法 设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使 "(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用圆圈表示 MAX，用叉号代表 MIN 比如左图中就是 MAX 取胜的棋局。 估价函数定义如下设棋局为 P，估价函数为 e(P)。 (1) 若 P 对任何一方来说都不是获胜的位置，则 e(P)=e(那些仍为 MAX 空着的完全的行、列或对角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数) (2) 若 P 是 MAX 必胜的棋局，则 e(P)＝+∞（实际上赋了 60）。 (3) 若 P 是 B 必胜的棋局，则 e(P)＝-∞（实际上赋了-20）。 e(P)=5-4=1 需要说明的是，+∞赋60，-∞赋-20的原因是机器若赢了，则不论玩 家下一步是否会赢，都会走这步必赢棋。 3. α -β剪枝算法 上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒 推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上 提出了α-β剪枝技术。 α -β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1) 对于一个与节点 MIN，若能估计出其倒推值的上确界β，并且这个β值不大于 MIN 的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该MIN 节点的其余子节点了(因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了)。这一过程称为α剪枝。 (2) 对于一个或节点 MAX，若能估计出其倒推值的下确界α，并且这个α值不小于 MAX 的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该 MAX 节点的其余子 湖南工业大学 课程设计任务书 2015—2016学年第2 学期 计算机与通信学院（系、部）计算机科学与技术专业计算机1502班级课程名称：面向对象程序设计 设计题目：五子棋 完成期限：自2016年6月13日至2016年6月19日共1周 指导教师（签字）：年月日 系（教研室）主任（签字）：年月日 面向对象程序设计课程设计 设计说明书 五子棋 起止日期： 2016年6月13日至 2016年6月18日 学生姓名王回 班级计算机1502学号15408100209成绩 指导教师(签字) 计算机与通信学院 2016年 6 月 18日 五子棋 一、课题的介绍和课题的任务 设计的课题名称：五子棋 实现以下功能： 功能1、模拟真实棋盘棋子 功能2、模拟人与人对战下棋 功能3、模拟实时胜负判断 功能4、模拟棋局的存储与读取 二、设计的要求 具有动画功能（即图像能即时移动），能实现人与人进行简单的对玩，能实现简单的胜负判断 三、系统的分析和系统中类的设计 CWZQApp类作用：初始化应用程序及运行该程序的所需要的成员函数CWZQDoc类作用：存放应用程序的数据以及实现文件的保存，加载功能 CMainFrame类作用：管理应用程序的窗口，显示标题栏，状态栏，工具栏等，同时处理针对窗口操作的信息 CAboutDlg类作用：向导自动生成对话框类 CWZQView类作用：管理视图窗口，在框架窗口中实现用户数据的显示和打印，存放添加的功能模块 CWZQView类中的成员函数与数据成员： void Save(); //**** //保存文件 void OnOpen() //打开文件 void over(CPoint point);//**** //检查是否结束voidOnDraw(CDC* pDC) //画棋盘函数 void OnLButtonUp(UINT nFlags, CPoint point)//模拟下棋函数 HCURSOR hcursorwhite; //**** //两个鼠标 HCURSOR hcursorblack; //**** intwzq[19][19]; //**** //棋盘数组 boolcolorwhite; //**** // colorwhite TRUE时白棋下， 否则黑棋下 CBitmapm_bmblack; //**** //棋子位图 CBitmapm_bmwhite; //**** void CWZQView::OnDraw(CDC* pDC) //构造棋盘，显示白棋以及黑棋 GetDocument() //获取文档指针，在视图中显示文档内容 CBrush //用于构造CBrush对象，然后传给需要画 刷的CDC成员函数 pDC->FillRect(myrect1,&mybrush1) // 画黑框线 四、系统的实现及调试 添加的功能： 1.图标，光标以及位图的绘制 程序运行开始鼠标在进入棋盘界面未放下棋子时变为类似棋子光标，此处需要描绘2种棋子光标： 黑白鼠标Cursor以替换当前鼠标： IDC_CURSOR1 黑棋子 IDC_CURSOR2 白棋子 说明： 由于下棋时我们必须把鼠标热点设置在中间，点击下图（图3-1-3）最右边按扭，然后把鼠标移动到图像中你想设置为热点的地方，按下鼠标左键。 人工智能αβ剪枝实现的一字棋实验报告 LELE was finally revised on the morning of December 16, 2020 实验5：-剪枝实现一字棋 一、实验目的 学习极大极小搜索及-剪枝算法实现一字棋。 二、实验原理 1.游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋"的棋盘很简单，是一个3×3的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 2.极小极大分析法 设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋 用圆圈表示MAX，用叉号代表MIN 比如左图中就是MAX取胜的棋局。 估价函数定义如下设棋局为P，估价函数为 e(P)。 (1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数) (2)若P是MAX必胜的棋局，则e(P)＝+（实际上赋了60）。 (3)若P是B必胜的棋局，则e(P)＝-（实际上赋了-20）。 需要说明的是，+赋60，-赋-20的原因是机器若赢 了，则不论玩家下一步是否会赢，都会走这步必赢棋。 3.-剪枝算法 上述的极小极大分析法，实际是先生成一棵博弈树， 然后再计算其倒推值，至使极小极大分析法效率较低。 于是在极小极大分析法的基础上提出了-剪枝技术。 -剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该MIN 一．实验目的： 1.理解和掌握博弈树的启发式搜索过程 2.学习极大极小搜索α–β剪枝 3.能够用选定的编程语言设计简单的博弈游戏 二．实验环境及工具 1.硬件环境：网络环境中的微型计算机 2.软件环境：Windows操作系统，VC++语言 三．实验原理 1. 游戏规则 “一字棋”游戏（又叫“三子棋”或“井字棋”），是一款十分经典的益智小游戏。“井字棋”的棋盘很简单，是一个 3×3 的格子，很像中国文字中的“井”字，所以得名“井字棋”。“井字棋”游戏的规则与“五子棋”十分类似，“五子棋”的规则是一方首先五子连成一线就胜利；“井字棋”是一方首先三子连成一线就胜利。 2.井字棋（英文名 Tic-Tac-Toe） 井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。 3.极大极小分析法 设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用圆圈表示 MAX，用叉号代表 MIN。 比如下图中就是 MAX取胜的棋局。 a)估价函数 设棋局为 P，估价函数为 e(P)。 (1) 若 P 对任何一方来说都不是获胜的位置，则 e(P)=e(那些仍为 MAX 空着的完全的行、列或对 角线的总数)-e(那些仍为 MIN 空着的完全的行、列或对角线的总数) (2) 若 P 是 MAX 必胜的棋局，则 e(P)＝+∞（实际上赋了 60）。 (3) 若 P 是 B 必胜的棋局，则 e(P)＝-∞（实际上赋了-20）。 比如 P 如下图示,则 e(P)=5-4=1 4.α–β剪枝算法 上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。 α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1) 对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这 个β值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了)。这一过程称为α剪枝。 (2) 对于一个或节点 MAX，若能估计出其倒推值的下确界α，并且这 个α值不小于 MAX 的父节点(一定是与节点)的估计倒推值的上确界 井字棋实验报告 篇一：井字棋实验报告 课程：班别小组成员 人工智能原理及其应用 12商本学号及姓名 指导老师 实验02井字棋 1、总体要求：1.1总体功能要求： 利用不同的方法，实现人机对战过程中呈现出不同程度的智能特征：（1）利用极大极小算法、α-β剪枝来提高算法的效率。（2）使用高级语言，编写一个智能井字棋游戏。 （3）结合极大极小算法的使用方法和α-β剪枝，让机器与人对弈时不但有智 能的特征，而且计算的效率也比较高。 1.2．开发平台要求： 开发者开发的软件必须能够在不同系统的电脑上正常运行，因此开发平台为：开发环境：JDK1.6 开发工具和技术体系： 为了此游戏能够很好的在不同系统中运行，因选择javaee进行开发，利用eclipse 1.3项目管理要求： （1）项目程序编写过程中要适当的写一些注释，以便下次作业时能够快速的上手和以后的修改： （2）项目程序要保存在一个固定的工作区间；（3）确保代码不要太多冗余 2、需求分析： 2.1软件的用户需求： 井字棋游戏的用户希望游戏除了有一般的功能之外，还可以通过极大极小算法、α-β剪枝等方法是的井字棋游戏能够拥有智能特征，并是的电脑在人机对弈的过程中因玩家的难度选择而体现不同程度的智能状况。 2.2软件的功能需求： 本游戏需要实现功能有：（1）游戏的重新设置 （2）游戏统计（如：人赢的次数、电脑赢的次数等）（3）游戏的退出 （4）不同智能程度下（脑残、懵懂、正常、智能），人 机对弈（5）既可以选择难度，也可以选择谁走第一步（人or电脑） 2.3软件的性能需求： 井字棋游戏需要以图形界面的形式表现出来，通过点击图标就可以进入游戏；在游戏进行时，人机对弈时电脑能够快速的反应并根据人的上一步动作作出，通过选择“脑残、懵懂、正常、智能”难度选择，电脑以不同程度的智能与人进行游戏对弈。 2.4 运行环境：能够运行java程序的环境（装有jdk 或者jre） 2.5 用户界面设计：用gridlayout进行用户界面的设计把界面中分为不同的模块。 3、软件概要设计 3.1 软件的逻辑设计：就是系统的功能模块结构图 4、软件详细设计 4.1 开发平台与环境 Eclipse; JDK1.6 4.2 用户界面的详细设计 4.3 各个模块的具体设计 游戏界面主要是利用GridLayout来进行布局管理，把整个JFrame分成左右两部分pwleft和pwright。 public void Layout() { 人工智能大作业——极大极小算法和α -β剪枝实现一字棋 学院： 班级： 姓名： 学号： 辅导老师： 日期： 目录 一、实验目的 (3) 二、实验环境 (3) 三、实验原理 (3) 3.1 游戏规则 (3) 3.2 极小极大分析法 (3) 3.3 α -β剪枝算法 (4) 3.4 输赢判断算法设计 (5) 四、数据结构 (5) 4.1 程序流程 (5) 4.2 主要成员函数 (5) 4.2.1 估值函数 (5) 4.2.2 Alpha-Beta 剪枝算法 (6) 4.2.3 判断胜负 (6) 4.2.4 鼠标左键响应 (6) 4.2.5 Draw 系列函数 (6) 4.2.6 COMPUTER or PLAYER 先走 (7) 五、实验内容 (7) 5.1 基本功能简介 (7) 5.2 流程图 (8) 5.2.1 估价函数 (8) 5.2.2 Alpha-Beta 剪枝 (9) 六、实验小结 (10) 七、实验源代码 (10) 一、实验目的 (1) 学习极大极小搜索及α-β剪枝。 (2) 利用学到的算法实现一字棋。 二、实验环境 (1) 硬件环境：网络环境中的微型计算机。 (2) 软件环境：Windows 操作系统，Microsoft Visual C++语言。 三、实验原理 3.1 游戏规则 "一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋" 的棋盘很简单，是一个3×3 的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。 井字棋（英文名Tic-Tac-Toe） 井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。 3.2 极小极大分析法 设有九个空格，由MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用圆圈表示MAX，用叉号代表MIN。 比如左图中就是MAX 取胜的棋局。 C语言程序设计报告 题目: 五子棋 班级: 电气Q1041班 人数: 3人 小组成员: 周啸天、万广富、黄山奇 指导老师：桂超 时间: 2011.11.30 目录 第一章课程设计的目的和要求 (3) 1.1 课程设计的目的 (3) 1.2 课程设计的要求 (3) 1.3 课程设计的实验环境 (3) 第二章功能描述 (4) 第三章总体设计 (5) 3.1 功能模块设计 (5) 3.1.1 任务执行流程图 (5) 3.1.2 下棋函数流程图 (6) 3.2 数据结构设计 (7) 3.2.1 定义结构体 (7) 3.2.2 定义数组 (7) 3.2.3 全局变量 (7) 3.3 函数功能描述 (7) 第四章程序实现 (8) 4.1源码分析 (8) 4.2运行结果及界面介绍 (22) 第五章后记 (27) 第一章课程设计的目的和要求 1.1 课程设计的目的 1.加深对C语言数据类型，运算，语句结构及其程序设计的基本方法理解和掌握； 2.熟练掌握流程图的绘制、程序设计文档的书写； 3.通过编写一个完整的程序，一方面可以检查我们这学期的学习情况，为以后的学习打下坚实的基础； 4.熟悉C语言游戏编程，掌握五子棋游戏开发的基本原理，从而为以后的程序开发奠定基础。 1.2 课程设计的要求 1、编写程序代码，调试所写程序使其能够正确运行； 2、能进行基本的五子棋操作，有图形界面，能够用键盘操作； 3、能够实现悔棋、存档和读档等附加功能 1.3 课程设计的实验环境 该课程设计在设计与实验过程中需要在windows XP系统/windows 2000以上系统中进行，程序设计要求在visual C++6.0平台中进行，完成代码的编写、编译、调试、测试等工作。本游戏对计算机硬件和操作系统要求极低，所以在这里只是把自己的电脑硬件参数和系统参数列下： 硬件：Cpu:2.1GHZ，内存，2GB，硬盘：320GB，操作系统：windows xp 软件环境：安装VC++6.0五子棋Java实验报告
人工智能实验报告大全
人工智能αβ剪枝实现的一字棋实验报告
五子棋实训报告
五子棋课程设计实验报告
人工智能α β剪枝实现的一字棋实验报告
五子棋游戏实验报告
人工智能α-β剪枝实现的一字棋实验报告重点讲义资料
五子棋C++实验报告
人工智能实验报告大全
人工智能αβ剪枝实现的一字棋实验报告
五子棋系统实验报告
人工智能αβ剪枝实现的一字棋实验报告
一字棋实验报告
井字棋实验报告
α-β剪枝实现的一字棋实验报告
五子棋课程设计实验报告
相关主题
文本预览