实验二：利用α

1、实验二：利用aB搜索过程的博弈树搜索算法编写一字棋游戏（3学时）一、实验目的与要求（1）了解极大极小算法的原理和使用方法，并学会用a-B剪枝来提高算法的效率。（2）使用C语言平台，编写一个智能井字棋游戏。（3）结合极大极小算法的使用方法和a-B剪枝，让机器与人对弈时不但有智能的特征，而且 计算的效率也比较高。二、实验原理一字棋游戏是一个流传已久的传统游戏。游戏由两个人轮流来下，分别用“X”和“O”来代 替自身的棋子。棋盘分9个格，双方可以在轮到自己下的时候，可以用棋子占领其中一个空的格 子。如果双方中有一方的棋子可以连成一条直线，则这一方判胜，对方判负。当所有的格子都被 占领，但双方都无法使棋

2、子连成一条直线的话，则判和棋。这是一个智能型的一字棋游戏，机器可以模拟人与用户对弈。当轮到机器来下的时候，机器会 根据当前棋局的形势，利用极大极小算法算出一个评价值，判断如何下才对自身最有利，同时也 是对方来说对不利的，然后下在评价值最高的地方。另外利用a-B剪枝，使机器在搜索评价值的 时候不用扩展不必要的结点，从而提高机器计算的效率。在用户界面方法，用一个3X3的井字格来显示用户与机器下的结果。当要求用户输入数据的 时候会有提示信息。用户在下的过程中可以中途按下“0 ”退出。当用户与计算机分出了胜负后， 机器会显示出比赛的结果，并按任意键退出。如果用户在下棋的过程中，输入的是非法字符，机 器

3、不会做出反应。三、实验步骤和过程1.G-P搜索过程在极小极大搜索方法中，由于要先生成指定深度以内的所有节点，其节点数将随着搜索深度 的增加承指数增长。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下， 利用已有的搜索信息减少生成的节点数呢？设某博弈问题如下图所示，应用极小极大方法进行搜 索MINIMAX过程是把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树， 然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。如图1中，其中一个MIN节点 要全部生成A、B、C、D四个节点，然后还要逐个计算其静态估值，最后在求倒推值阶段，才赋 给这个MIN节点的倒推值一8。

4、其实，如果生成节点A后，马上进行静态估值，得知f (A) = 一8之后，就可以断定再生成其余节点及进行静态计算是多余的，可以马上对MIN节点赋倒推值 一8,而丝毫不会影响MAX的最好优先走步的选择。这是一种极端的情况，实际上把生成和倒 推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝，同样可获得 类似的效果，这就是a-p过程的基本思想。利用a-p搜索过程的一字棋的实例图2 字棋第一阶段a-6剪枝方法为了使生成和估值过程紧密结合，采用有界深度优先策略进行搜索，这样当生成达到规定深 度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计 算赋值

5、。从图2中标记的节点生成顺序号(也表示节点编号)看出，生成并计算完第6个节点后， 第1个节点倒推值完全确定，可立即赋给倒推值一1。这时对初始节点来说，虽然其他子节点尚未 生成，但由于s属极大值层，可以推断其倒推值不会小于一1，我们称极大值层的这个下界值为a， 即可以确定s的a= 1。这说明s实际的倒推值决不会比一1更小，还取决于其他后继节点的倒 推值，因此继续生成搜索树。当第8个节点生成出来并计算得静态估值为一1后，就可以断定第7 个节点的倒推值不可能大于一1，我们称极小值层的这个上界值为P，即可确定节点7的。=一1。 有了极小值层的P值，很容易发现若传P时，节点7的其他子节点不必再生成，这不

6、影响高一层 极大值的选取，因s的极大值不可能比这个p值还小，再生成无疑是多余的，因此可以进行剪枝。 这样一来，只要在搜索过程记住倒推值的上下界并进行比较，就可以实现修剪操作，称这种操作 为a剪枝。类似的还有p剪枝，统称为a-p剪枝技术。在实际修剪过程中，a、p还可以随时修正， 但极大值层的倒推值下界a永不下降，实际的倒推值取其后继节点最终确定的倒推值中最大的一 个倒推值。而极小值层的倒推值上界p永不上升，其倒推值则取后继节点最终确定的倒推值中最 小的一个倒推值。2.1在进行a-p剪枝时，应注意以下几个问题：比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点 和极小节点

7、间的比较是无意义的。在比较时注意是与”先辈层”节点比较，不只是与父辈节点比较。当然，这里的先辈层 节点，指的是那些已经有了值的节点。当只有一个节点的”固定”以后，其值才能够向其父节点传递。a-p剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，a-p剪枝并没 有因为提高效率，而降低得到最佳走步的可能性。在实际搜索时，并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。如果这样， 就失去了 a-p剪枝方法的意义。在实际程序实现时，首先规定一个搜索深度，然后按照类似于深 度优先搜索的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝，则该节 点其余未生成的节点就不再生成了。

8、2.2 a-p剪枝搜索过程（如图3）在搜索过程中，假定节点的生成次序是从上到下，从左到右进行的。图中带圈的数字，表示 节点的计算次序，在叙述时，为了表达上的方便，该序号也同时表示节点。当一个节点有两个以 上的序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果。过程如下：I I. -!：93 -!： n ,，: n -!9!，4-!：!8M -：图3 a-0搜索过程的博弈树图3给出一个d=4的博弈树的a-p搜索过程，其中带圆圈的数字表示求静态估值及倒推值过 程的次序编号。该图详细表示出a-p剪枝过程的若干细节。初始节点的最终倒推值为1，该值等 于某一个端节点的静态估值。最好优先走步是走

9、向右分枝节点所代表的棋局，要注意棋局的发展 并不一定要沿着通向静态值为1的端节点这条路径走下去，这要看对手的实际响应而定。2.3剪枝的效率问题若以最理想的情况进行搜索，即对MIN节点先扩展最低估值的节点（若从左向右顺序进行， 则设节点估计值从左向右递增排序），MAX先扩展最高估值的节点（设估计值从左向右递减排序）， 则当搜索树深度为D，分枝因数为B时，若不使用a-p剪枝技术，搜索树的端节点数若 使用a-p剪枝技术.可以证明理想条件下生成的端节点数最少，有Nd=2Bd-1（d 为偶数）心/心+欧昨_1（D为奇数）比较后得出最佳a-p搜索技术所生成深度为D处的端节点数约等于不用a-p搜索技术所生成

10、 深度为D/2处的端节点数。这就是说，在一般条件下使用a-p搜索技术，在同样的资源限制下， 可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优势。改进方法：其他改善极小极大过程性能的基本方法：不严格限制搜索的深度，当到达深度限制时，如出现博弈格局有可能发生较大变化是， 则应多搜索几层，使格局进入较稳定状态后再终止，这样可使倒推值计算的结果计较 合理，避免考虑不充分产生的影响，这就是等候状态平稳后终止搜索的方法。当算法给出所选的走步后，不马上停止搜索，而是在原先估计可能的路径上再往前搜 索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。某些博弈的开局阶段和残局阶段

11、，往往总结有一些固定的对弈模式，因此可以利用这 些知识编好走不表，以便开局和结局时使用查表法，只是在进入盘中阶段后，再调用 其他有效的搜索算法，来选择最优的走步。结论：a-B剪枝过程是二人博弈问题的一般搜索方法，这种方法基于极小极大过程的一些 方法都设想对手总是走的最优走步，即我方总是应考虑最坏的情况，从而选出我方最优的应对走 法，有效的减少搜索过程中生成的节点数，从而提高了搜索效率。本实验所用的博弈搜索技术可用于求解一些双人博弈问题，但是只是一些简单的推理 技术，未涉及棋局的表示和启发函数问题。一些高明棋局中，在一个短期内短兵相接，进攻和防 御战术变化剧烈，这些情况怎样在搜索策略中加以考虑。

12、这就需要我们在往后的学习中不断深化 了。五、基于a - B剪枝的一字棋源代码#includeusing namespace std;int num=0;记录棋盘上棋子的个数int p,q;int tmpQP33;/表示棋盘数据的临时数组，其中的元素0表示该格为空，int cur33;/存储当前棋盘的状态const int depth=3; /搜索树的最大深度void Init()/初始化棋盘状态for(int i=0;i3;i+)for(int j=0;j3;j+)curij=0;void PrintQP()打印棋盘当前状态for(int i=0;i3;i+)for(int j=0;j3;j+

13、)coutcurijt;coutendl;void UserInput()/佣户通过此函数来输入落子的位置，比如：用户输入31，则表示用户在第3行第1列落子。int pos,x,y;L1: coutpos;x=pos/10,y=pos%10;if(x0&x0&y4&curx-1y-1=0)curx-1y-1=-1;elsecoutInput Error!;goto L1;int CheckWin() /检查是否有一方赢棋(返回0：没有任何一方赢；1：计算机赢；-1：人赢)该方法没有判断平局for(int i=0;i3;i+)if(curi0=1&curi1=1&curi2=1)return 1

14、;if(curi0=-1&curi1=-1&curi2=-1)return -1;for(i=0;i3;i+)if(cur0i=1&cur1i=1&cur i=1)return 1;if(cur0i=-1&cur1i=-1&cur i=-1)return -1;if(cur00=1&cur11=1&cur 2=1)|(cu r0=1&cur11=1&cur02=1 )return 1; if(cur00=-1&cur11=-1&cur 2=-1)ll(cur 0=-1&cur11=-1&cur02 =-1) return -1; return 0; int value()/评估当前棋盘状态的值

15、(同时可以用p或q判断是否平局) p=0; q=0; for(int i=0;i3;i+)计算机一方/将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1for(int j=0;j3;j+) if(curij=0) tmpQPij=1; else tmpQPij=curij; for(i=0;i3;i+)计算共有多少连成3个1的行 p+=(tmpQPi0+tmpQPi1+tmpQPi 皿)/3; for(i=0;i3;i+)计算共有多少连成3个1的列 p+=(tmpQP0i+tmpQP1i+tmpQP i)/3; p+=(tmpQP00+tmpQP11+tmpQP22)/3;/计算共有多少连

16、成 3 个 1 的对角线 p+=(tmpQP20+tmpQP11+tmpQP0)/3; for(i=0;i3;i+)/人一方将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1for(int j=0;j3;j+) if(curij=0) tmpQPij=-1; else tmpQPij=curij; for(i=0;i3;i+)计算共有多少连成3个-1的行 q+=(tmpQPi0+tmpQPi1+tmpQPi 皿)/3; for(i=0;i3;i+)计算共有多少连成3个1的列 q+=(tmpQP0i+tmpQP1i+tmpQP i)/3; q+=(tmpQP00+tmpQP11+tmpQP

17、22)/3;/计算共有多少连成 3 个 1 的对角线 q+=(tmpQP20+tmpQP11+tmpQP0)/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();/flag记录本层的极值，temp记录下层求得的估计值/out记录是否剪枝，初始为false如果计算机赢了，

18、就置上一层的估计值为无穷(用很大的int i,j,flag,temp;bool out=false;/*if(CheckWin()=1)值代表无穷)val=10000;return 0;*/if(max)/如果上一层是极大层，本层则需要是极小层，记录flag为无穷大；反之，则为记录为负无穷大/flag记录本层节点的极值flag=10000;elseflag=-10000;for(i=0;i3 & !out;i+) /双重循环，遍历棋盘所有位置 for(j=0;j3 & !out;j+) if(curij=0)/如果该位置上没有棋子 if(max)/并且上一层为极大层，即本层为极小层，轮到用户玩

19、家走了。 curij=-1;/该位置填上用户玩家棋子if(CheckWin()=-1) /如果用户玩家赢了 temp=-10000;/置棋盘估计值为负无穷 else temp=cut(flag,dep+1,!max)否则继续调用a-B剪枝函数 if(tempflag)/如果下一步棋盘的估计值小于本层节点的极值，则置本层极值为更小者 flag=temp; if(flagflag)flag=temp;if(flag=val)out=true;curij=0;/把模拟下的一步棋还原，回溯if(max) /根据上一层是否为极大层，用本层的极值修改上一层的估计值if(flagval)val=flag;e

20、lseif(flagval)val=flag;return flag; 函数返回的是本层的极值int main()/主 程序int m=-10000,val=-10000,dep=1;/m 用来存放最大的 valint x_pos,y_pos;记录最佳走步的坐标Init();coutQipan: endl;PrintQP();char IsFirst;coutIsFirst;while(IsFirst!=y&IsFirst!=n)coutERROR!IsFirst; if(IsFirst=n)/计算机先走 L5:for(int x=0;x3;x+) for(int y=0;y3;y+) if(

21、curxy=0) curxy=1; cut(val,dep,1);/计算机试探的走一步棋，棋盘状态改变了，在该状态下计算 出深度为dep-1的棋盘状态估计值val if(CheckWin()=1) coutThe computer put the qizi at:x+1y+1endl; PrintQP(); coutThe computer WIN! GAME OVER.m) /m要记录通过试探求得的棋盘状态的最大估计值 m=val; x_pos=x;y_pos=y; val=-10000; curxy=0; curx_posy_pos=1; val=-10000; m=-10000; dep=1; coutThe computer put the qizi at:x_pos+1y_pos+1endl; PrintQP(); coutendl; num+; value(); if(p=0) coutDOWN GAME!endl;re