从一个策略游戏谈搜索算法优化.doc

从一个策略游戏谈搜索算法优化从一个策略游戏谈搜索算法优化对于策略游戏性质的二人博弈问题，比如黑白棋，五子棋等，一般的解答方法就是搜索；但搜索算法的原理不同，其性能就大不一样。一般来说，如果我们对问题的本质把握的越深，算法的设计就会相对的复杂，但是效率会高很多。下面我们就通过一个二人游戏来谈这方面的体会。一.问题的提出问题：TwoFour罗马尼亚奥林匹克,via Stroe,2002Bessie有一个新的两人游戏：TwoFour.她有N(3=N=30)堆球,每堆有nballs(0=nballs=4)个.球的总数为2*N.玩这个游戏时,游戏者轮流执行一个有效移动.一个有效移动由下列动作组成：*第一,游戏者选择不同的两堆球.*第二,把一个球从一堆拿到另一堆.她可以这样做的前提是运完球后第二堆的球数(包括新放上的球)不大于第一堆剩下的球的数目.当没有移动可做时,游戏结束.实际上,在游戏的末尾,每堆将包含恰好两个球.游戏的胜者拥有多数球堆.平局是可能的.当某堆有两个球并且是由于某游戏者最近对它的的一次移动(不管移走还是放入)使其变为两个球的,我们就说她拥有这堆球.看看这些例子：*如果一个游戏者从有四个球的某球堆中移走一个球,放到有一个球的某球堆中,那么它拥有了第二堆(有两个球).*如果一个游戏者从有三个球的某球堆中移走一个球,放到有零个球的某球堆中,那么它拥有了第一堆,现在这堆有两个球.*如果一个游戏者从有三个球的某球堆中移走一个球,放到有一个球的某球堆中,那么它拥有了这两堆(他们都有两个球).拥有权能够变化.设想一个游戏者拥有两个球的一个球堆,如果另一个游戏者选了一个有四个球的堆并把一个球移到此两个球的堆中,那么这堆球谁也不属于了.如果,在游戏的开头,存在有两个球的一些球堆,那么这些堆被平分给两个游戏者,剩余的堆则分给游戏者2.游戏者1先移动.你的程序必须判断,对一个初始的游戏状态,谁将获胜或者会否出现平局.你的程序将处理G(1=G=1000)个游戏状态.该问题要求使用不超过1.00 MB的内存.问题名：twofour输入格式：*行1：用空格隔开的两个整数：N和G.*行2.G+1：每行包含空格隔开的N个整数用于描述该游戏.第一个整数是堆1的球数,第二个整数是堆2的球数,.行2描述了游戏1,行3描述了游戏2,.你的程序应该计算每个特定游戏的胜者.输入样例(文件twofour.in)：5 40 34 12 22 22 21 12 24 43 21 0输出格式：*行1.G：每个游戏的结果.行1给出游戏1的结果,.结果是一个整数：1代表第一个游戏者获胜,2代表第二个获胜,以及0代表平局.输出样例(文件twofour.out)：1 21 1二.问题的初步分析和第一种解答从问题的描述来看，我们可以得到如下的一些基本信息：1)player1总是先手的，问题也是求player1的胜负情况；player2在瓜分最初的2堆的时候具有优先权。2)整个的游戏过程，就是把不均有分布的堆，逐步均匀化，直至所有的堆都是2堆，由于2N个球，放置在N堆上，这是个必然。3)2堆在游戏过程中会变化成1堆或者3堆；每堆的球数不超过4，允许0堆。4)如果两堆之间的球数目差1，就可以进行球的移动，这是我们在程序中判断可行步的依据。在上面的基本信息的基础上，我们就要决定用什么搜索算法，用广度优先搜索还是深度优先搜索呢?如果用广度优先搜索的话，一般的方法是从根节点出发，平行的推进所有从根节点衍生出来的子节点，每个节点都要保存当前棋局的状态,同时还要记住父节点的索引；子节点需要父节点的信息来进行衍生，而父节点需要子节点的结果来决定本节点的结果。一般我们用一个队列来实现这个过程；由于所有的节点都需要保存，一些废节点也被保存了，而对于奇偶深度的节点的处理还不一样(奇偶深度，对应player1还是player2)，下面会具体讲到，节点所要保存和处理的信息都比较复杂，另外针对这个问题的广度优先搜索的剪枝工作也是个问题，因为广搜的处理方式是先把子节点全部入队列，然后从队头逐个再扩展，一些无用的节点就占用了宝贵的队列空间。比如player1的任何一步移动，只要能胜利，其它方式的移动都不需要考虑了；然而对于走法的判断是在所有子节点入队之后，所以其他废节点就占用了多余的空间。综合上面的讨论，我认为本问题不太适合使用基于广度优先搜索的算法。下面考虑深度优先搜索。深度优先搜索有一个好处就是占用的空间少。先讲讲我们的思路，请大家注意对于player1和player2的处理的不同。1)我们对所有棋局的考虑都以player1为中心，不论当前棋局是由player1的移动还是player2的移动造成的.2)如果相对与当前棋局，对于player1的所有移动中，有一种能导致player1胜利，则当前节点就能导致player1胜利，也就是不需要再扩展了,直接返回结果到上层父节点；如果对于player1的所有移动，全都导致player1失败，才能说本节点导致player1失败；如果没有走法能胜利，但有一种走法能使得player1和局，那么player1会选择和局。3)同样的道理，如果相对与当前棋局，对于player2的所有移动中，有一种能导致player2胜利，则当前节点就能导致player1失败，也就是不需要再扩展了，直接返回结果到上层父节点；如果对于player2的所有移动，全都导致player2失败，才能说本节点导致player1胜利；如果没有走法能使得player2胜利，但有一种走法能使得player2和局，那么player2会选择和局，也就是导致player1和局。4)由于player1先手，从初始棋局出发，逐个扩展出子节点，并递规的调用自身来扩展子节点，直到无法再深度扩展为止。下面来看我们的第一个版本的解答。#define QMAX 30 typedef structint qn；/球的个数int owner；/所有者，0：没有所有者,1：属于player1,-1：属于player2sq_str；/上面的数据结构用来描述堆的属性。sq_str aQMAX；/用来描述棋局状态int n；/记录堆的个数，全局变量int depthmax=-1；/用来记录最深的递规深度，以便了解堆栈内存的使用使用下面的代码得到输入，当然后面我们会讨论随机生成棋局的方式，初始的棋局在这里就准备好void test1()int i,j；int G,c；scanf(%d%d,&n,&G)；for(i=0；i G；i+)c=0；for(j=0；j n；j+)scanf(%d,&aj.qn)；if(aj.qn=2)if(c&1)=0)aj.owner=-1；/由player2所有else aj.owner=1；/由player1所有c+；else aj.owner=0；/无人所有depthmax=-1；c=qiuv0(0)；printf(result：%d.depthmax=%d.n,c,depthmax)；/求解棋局的函数，胜负是指player1的胜负。depth表示当前迭代的深度，同时也表示当前执子的玩家，depth为偶数，表示player1执子，depth为奇数，表示player2执子。/返回1：胜利，-1：失败,0：和局int qiuv0(int depth)int i,j,k=0,s,tx=0；int ret0；int fu=0；/会导致player1失败的节点的个数int shen=0；/会导致player1胜利的节点的个数sq_str savei,savej；if(depth depthmax)depthmax=depth；for(i=0；i n；i+)for(j=0；j n；j+)if(ai.qn-aj.qn 1)/判断可行移动步的标准，从第i堆到第j堆k+；/记录子节点的个数/保留被修改的堆，方便以后恢复savei=ai；savej=aj；ai.qn-；aj.qn+；if(ai.owner)ai.owner=0；if(aj.owner)aj.owner=0；if(ai.qn=2)if(depth&1)=0)ai.owner=1；else ai.owner=-1；if(aj.qn=2)if(depth&1)=0)aj.owner=1；else aj.owner=-1；ret0=qiu(depth+1)；/递规调用/恢复被修改的棋局ai=savei；aj=savej；/请大家注意下面的不同处理，所有的胜负都是对于player1来说的if(depth&1)=0)/player1的局势if(ret0=1)return 1；else if(ret0=-1)fu+；else/player2的局势if(ret0=-1)return-1；else if(ret0=1)shen+；if(k=0)/如果没有子节点可以扩展，那么这是个终局for(i=0；i n；i+)k+=ai.owner；if(k=0)return 0；if(k 0)return 1；if(k 0)return-1；else/否则是扩展了子节点的if(depth&1)=0)if(fu=k)return-1；/所有的走法都导致输else return 0；/至少有一种走发可以保证平局elseif(shen=k)return 1；/player2所有的走法都导致player1胜利else return 0；/player2会选择平局三.初步的优化和剪枝好了程序很简单，应该很容易理解，但是效率也很低！下面我们来逐步分析优化，看看问题在哪里。首先我们发现，同层扩展出的各棋局的状态只和各堆的状态有关，而和各堆的排列没有关系，所以在同一层我们就可以进行剪枝，把那些本质上是一样的子节点剪掉。考虑所有的走法一共有8种：4-2(-1,1),4-1,4-0,3-1,3-0,2(-1,1)-0,括号里的数表示2堆的归属情况。新的程序如下：int qiuv1(int depth)int i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；sq_str savei,savej；sq_str tt82；/一共有8种不同的移动方式int re8；/8种移动方式带来的结果int ti=0；if(depth depthmax)depthmax=depth；for(i=0；i n；i+)for(j=0；j n；j+)if(ai.qn-aj.qn 1)k+；for(s=0；s ti；s+)if(ai.owner=tts0.owner)&(ai.qn=tts0.qn)&(aj.owner=tts1.owner)&(aj.qn=tts1.qn)break；if(s！=ti)ret0=res；if(depth&1)=0)/player1的局势if(ret0=1)return 1；else if(ret0=-1)fu+；else/player2的局势if(ret0=-1)return-1；else if(ret0=1)shen+；continue；elsettti0=ai；ttti1=aj；savei=ai；savej=aj；ai.qn-；aj.qn+；if(ai.owner)ai.owner=0；if(aj.owner)aj.owner=0；if(ai.qn=2)if(depth&1)=0)ai.owner=1；else ai.owner=-1；if(aj.qn=2)if(depth&1)=0)aj.owner=1；else aj.owner=-1；ret0=qiu(depth+1)；reti=ret0；ti+；ai=savei；aj=savej；if(depth&1)=0)/player1的局势if(ret0=1)return 1；else if(ret0=-1)fu+；else/player2的局势if(ret0=-1)return-1；else if(ret0=1)shen+；if(k=0)for(i=0；i n；i+)k+=ai.owner；if(k=0)return 0；if(k 0)return 1；if(k 0)return-1；elseif(depth&1)=0)if(fu=k)return-1；/所有的走法都导致输else return 0；/至少有一种走发可以保证平局elseif(shen=k)return 1；/player2所有的走法都导致player1胜利else return 0；/player2会选择平局四、进一步的优化和剪枝经过上面的优化，程序的性能有所提升，但是还不够快，问题出在哪里呢?我们知道深度优先搜索的一大缺点就是对已有的计算结果没有继承，造成了大量的计算浪费；qiuv1已经做了一点工作，但还不够；我们需要记录所有的已经访问过的棋局和相应的结果，方便在后续的搜索中进行剪枝。这就需要对以往结果的记录。定义如下数据结构：#define STAMAX 11000 unsigned char x_staSTAMAX8；/player1的2就在2，player2的2在5,局势的结果放在7,depth的奇偶性放在6里int x_inx=0；/x_sta中的下一个空位置我们知道棋局只和堆本身有关，而和堆的排列顺序无关，进一步，两个相同的堆也是无区别的，这样我们只需要记录一个棋局中0堆的个数，1堆的个数,2(1)堆的个数，2(-1)堆的个数,3堆的个数，4堆的个数，以及当前棋局对应的执子方，这种棋局的结果。由于最多也就30堆，所以1个字节足以存放相关的信息。算算上面的空间才不到90KB，离1MB尚远。还有一个问题，那就是棋局的对偶性，棋局A的对偶棋局，就是把depth的奇偶性取反，把相应的2堆的归属性取反，相应的棋局结果自然取反。这个很容易理解，相当与player2和player1交换位置，下对方的棋。这样我们每求得一个棋局，实际上是得到了两个棋局的结果。好了还是看看新程序吧.int qiuv2(int depth)int i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；int old_xinx；unsigned char x7；sq_str savei,savej；if(depth depthmax)depthmax=depth；for(i=0；i n；i+)for(j=0；j n；j+)if(ai.qn-aj.qn 1)k+；memset(x,0,7)；savei=ai；savej=aj；ai.qn-；aj.qn+；if(ai.owner)ai.owner=0；if(aj.owner)aj.owner=0；if(ai.qn=2)if(depth&1)=0)ai.owner=1；else ai.owner=-1；if(aj.qn=2)if(depth&1)=0)aj.owner=1；else aj.owner=-1；for(s=0；s n；s+)if(as.qn！=2)xas.qn+；elseif(as.owner=1)x2+；else x5+；x6=depth&1；/开始搜索以前保存的结果for(s=0；s x_inx；s+)if(memcmp(x,x_stas,7)=0)break；if(s！=x_inx)/找到了！ai=savei；aj=savej；ret0=(char)x_stas7；if(depth&1)=0)/player1的局势if(ret0=1)return 1；else if(ret0=-1)fu+；else/player2的局势if(ret0=-1)return-1；else if(ret0=1)shen+；continue；elsememcpy(x_stax_inx,x,7)；/每找到，把当前棋局添加进去old_xinx=x_inx；/记录自己的位置，后面好吧结果填进去，因为下面的递规会加入新的内容到存储队列x_inx+；ret0=qiuv1(depth+1)；x_staold_xinx7=ret0；ai=savei；aj=savej；/把对偶的情况放进去memcpy(x_stax_inx,x_staold_xinx,8)；x_stax_inx2=x_staold_xinx5；x_stax_inx5=x_staold_xinx2；x_stax_inx6=！x_staold_xinx6；x_stax_inx7=-x_staold_xinx7；x_inx+；if(depth&1)=0)/player1的局势if(ret0=1)return 1；else if(ret0=-1)fu+；else/player2的局势if(ret0=-1)return-1；else if(ret0=1)shen+；if(k=0)for(i=0；i n；i+)k+=ai.owner；if(k=0)return 0；if(k 0)return 1；if(k 0)return-1；elseif(depth&1)=0)if(fu=k)return-1；/所有的走法都导致输else return 0；/至少有一种走发可以保证平局elseif(shen=k)return 1；/player2所有的走法都导致player1胜利else return 0；/player2会选择平局好了，这下我们的程序有了质的飞跃，速度提高很多，比v1版本提高了几个数量级！很开心-。五.HASH函数的应用但是当我们加大测试强度，把堆的数量推到顶，达到30之后，我们的程序还是不够快，对有的棋局，几乎半分钟内都解不出来，这是不能接受的。那好吧，看来我们还需要进一步优化。还有什么地方值得优化呢?就是下面这个地方！/开始搜索以前保存的结果for(s=0；s x_inx；s+)if(memcmp(x,x_stas,7)=0)break；通过测试发现，对于30堆的情况，我们的存储会有超过10000的情况，一般也会超过5000！对于这么大的存储空间，如果向上面那样每次都进行线性匹配，效率是很低下的，这也就是为什么在堆变多之后，我们的程序变慢的原因。好了问题找到了，那么如何解决呢?还是有办法的，那就是hash表！通过hash表就可以一步定位到我们需要的位置，只要hash函数设置的好，就可以尽量减少碰撞的产生；即使有了碰撞也不怕，搞个拉链链接起来就可以了，经过测试新的程序，使用hash表，最多也就产生两三次碰撞，一般都能一击中的！#define STAMAX 0x4000 typedef structunsigned char x_sta8；/player1的2就在2，player2的2在5,局势的结果放在7,depth的奇偶性放在6里unsigned short pr；/低14bit是索引，高2bit：00(空项目),01(低14bit表示下一个的位置)，10(没有下一个了)X_sta；/hash表X_sta hashSTAMAX；/占用160KB空间，实际测试，可以处理的堆数达35堆的情况/返回14bit的HASH值，我自己构造的hash函数unsigned short cal_hash(unsigned char*in,int len)unsigned short x1=0；int i；for(i=0；i len；i+)x1=(x1*11)+ini)0x3d；return(x1&0x3fff)；int qiuv3(int depth)int i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；int old_xinx；unsigned char x8；/把结果也含进来了unsigned short s_indx；int nexti；int find；sq_str savei,savej；if(depth depthmax)depthmax=depth；for(i=0；i n；i+)for(j=0；j n；j+)if(ai.qn-aj.qn 1)k+；memset(x,0,8)；savei=ai；savej=aj；ai.qn-；aj.qn+；if(ai.owner)ai.owner=0；if(aj.owner)aj.owner=0；if(ai.qn=2)if(depth&1)=0)ai.owner=1；else ai.owner=-1；if(aj.qn=2)if(depth&1)=0)aj.owner=1；else aj.owner=-1；for(s=0；s n；s+)if(as.qn！=2)xas.qn+；elseif(as.owner=1)x2+；else x5+；x6=depth&1；find=0；s_indx=cal_hash(x,7)；/计算hash值作为索引nexti=s_indx；switch(hashs_indx.pr 14)/查看高两bit属性值case 0：/空项，直接填入memcpy(hashnexti.x_sta,x,8)；hashnexti.pr=0x8000；old_xinx=nexti；x_inx+；break；case 1：/碰撞，那就顺着链条往下查找吧doif(memcmp(x,hashnexti.x_sta,7)=0)find=1；break；nexti=hashnexti.pr&0x3fff；while(hashnexti.pr 14)！=2)；/这里直接滑入case2，因为到这里处理是一样的了case 2：/和最后一个进行比较if(memcmp(x,hashnexti.x_sta,7)=0)find=1；if(find=1)/找到了一模一样的ai=savei；aj=savej；ret0=(char)hashnexti.x_sta7；if(depth&1)=0)/player1的局势if(ret0=1)return 1；else if(ret0=-1)fu+；else/player2的局势if(ret0=-1)return-1；else if(ret0=1)shen+；continue；/否则就是没有找到，那么就只能拉拉链了，找一个空地方塞进去for(s=0；s STAMAX；s+)if(hashs.pr 14)=0)break；if(s=STAMAX)/hash表满了！printf(error hashtable full！)；return-2；memcpy(hashs.x_sta,x,8)；hashs.pr=0x8000；/这几行就是在接拉链old_xinx=s；hashnexti.pr=s|0x4000；x_inx+；break；default：printf(error in pr！)；break；ret0=qiuv1(depth+1)；hashold_xinx.x_sta7=ret0；ai=savei；aj=savej；/把对偶的情况放进去find=x2；x2=x5；x5=find；find=0；x6=！x6；x7=-ret0；s_indx=cal_hash(x,7)；/查找对偶情况，如果对偶情况已经在里面了，就不用添加了，否则就需要添加nexti=s_indx；switch(hashs_indx.pr 14)case 0：x_inx+；memcpy(hashnexti.x_sta,x,8)；hashnexti.pr=0x8000；break；case 1：doif(memcmp(x,hashnexti.x_sta,7)=0)find=1；break；nexti=hashnexti.pr&0x3fff；while(hashnexti.pr 14)！=2)；case 2：/和最后一个进行比较if(memcmp(x,hashnexti.x_sta,7)=0)find=1；if(find=0)/否则就是没有找到for(s=0；s STAMAX；s+)if(hashs.pr 14)=0)break；if(s=STAMAX)printf(error hashtable full！)；return-2；memcpy(hashs.x_sta,x,8)；h