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

1、.从一个策略游戏谈搜索算法优化从一个策略游戏谈搜索算法优化对于策略游戏性质的二人博弈问题，比方黑白棋，五子棋等，一般的解答方法就是搜索；但搜索算法的原理不同，其性能就大不一样。一般来说，假设我们对问题的本质把握的越深，算法的设计就会相对的复杂，但是效率会高很多。下面我们就通过一个二人游戏来谈这方面的体会。一.问题的提出问题：TwoFour罗马尼亚奥林匹克,via Stroe,2002Bessie有一个新的两人游戏：TwoFour.她有N3=N=30堆球,每堆有nballs0=nballs=4个.球的总数为2*N.玩这个游戏时,游戏者轮流执行一个有效挪动.一个有效挪动由以下动作组成：*第一,游戏

2、者选择不同的两堆球.*第二,把一个球从一堆拿到另一堆.她可以这样做的前提是运完球后第二堆的球数包括新放上的球不大于第一堆剩下的球的数目.当没有挪动可做时,游戏完毕.实际上,在游戏的末尾,每堆将包含恰好两个球.游戏的胜者拥有多数球堆.平局是可能的.当某堆有两个球并且是由于某游戏者最近对它的的一次挪动不管移走还是放入使其变为两个球的,我们就说她拥有这堆球.看看这些例子：*假设一个游戏者从有四个球的某球堆中移走一个球,放到有一个球的某球堆中,那么它拥有了第二堆有两个球.*假设一个游戏者从有三个球的某球堆中移走一个球,放到有零个球的某球堆中,那么它拥有了第一堆,如今这堆有两个球.*假设一个游戏者从有三

3、个球的某球堆中移走一个球,放到有一个球的某球堆中,那么它拥有了这两堆他们都有两个球.拥有权可以变化.设想一个游戏者拥有两个球的一个球堆,假设另一个游戏者选了一个有四个球的堆并把一个球移到此两个球的堆中,那么这堆球谁也不属于了.假设,在游戏的开头,存在有两个球的一些球堆,那么这些堆被平分给两个游戏者,剩余的堆那么分给游戏者2.游戏者1先挪动.你的程序必须判断,对一个初始的游戏状态,谁将获胜或者会否出现平局.你的程序将处理G1=G=1000个游戏状态.该问题要求使用不超过1.00 MB的内存.问题名：twofour输入格式：*行1：用空格隔开的两个整数：N和G.*行2.G+1：每行包含空格隔开的N

4、个整数用于描绘该游戏.第一个整数是堆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二.问题的初步分析和第一种解答从问题的描绘来看，我们可以得到如下的一些根本信息：1player1总是先手的，问题也是求player1的胜负情况；player2在瓜分最初的

5、2堆的时候具有优先权。2整个的游戏过程，就是把不均有分布的堆，逐步均匀化，直至所有的堆都是2堆，由于2N个球，放置在N堆上，这是个必然。32堆在游戏过程中会变化成1堆或者3堆；每堆的球数不超过4，允许0堆。4假设两堆之间的球数目差1，就可以进展球的挪动，这是我们在程序中判断可行步的根据。在上面的根本信息的根底上，我们就要决定用什么搜索算法，用广度优先搜索还是深度优先搜索呢?假设用广度优先搜索的话，一般的方法是从根节点出发，平行的推进所有从根节点衍生出来的子节点，每个节点都要保存当前棋局的状态,同时还要记住父节点的索引；子节点需要父节点的信息来进展衍生，而父节点需要子节点的结果来决定本节点的结果

6、。一般我们用一个队列来实现这个过程；由于所有的节点都需要保存，一些废节点也被保存了，而对于奇偶深度的节点的处理还不一样奇偶深度，对应player1还是player2，下面会详细讲到，节点所要保存和处理的信息都比较复杂，另外针对这个问题的广度优先搜索的剪枝工作也是个问题，因为广搜的处理方式是先把子节点全部入队列，然后从队头逐个再扩展，一些无用的节点就占用了珍贵的队列空间。比方player1的任何一步挪动，只要能成功，其它方式的挪动都不需要考虑了；然而对于走法的判断是在所有子节点入队之后，所以其他废节点就占用了多余的空间。综合上面的讨论，我认为本问题不太适宜使用基于广度优先搜索的算法。下面考虑深度

7、优先搜索。深度优先搜索有一个好处就是占用的空间少。先讲讲我们的思路，请大家注意对于player1和player2的处理的不同。1我们对所有棋局的考虑都以player1为中心，不管当前棋局是由player1的挪动还是player2的挪动造成的.2假设相对与当前棋局，对于player1的所有挪动中，有一种能导致player1成功，那么当前节点就能导致player1成功，也就是不需要再扩展了,直接返回结果到上层父节点；假设对于player1的所有挪动，全都导致player1失败，才能说本节点导致player1失败；假设没有走法能成功，但有一种走法能使得player1和局，那么player1会选择和局

8、。3同样的道理，假设相对与当前棋局，对于player2的所有挪动中，有一种能导致player2成功，那么当前节点就能导致player1失败，也就是不需要再扩展了，直接返回结果到上层父节点；假设对于player2的所有挪动，全都导致player2失败，才能说本节点导致player1成功；假设没有走法能使得player2成功，但有一种走法能使得player2和局，那么player2会选择和局，也就是导致player1和局。4由于player1先手，从初始棋局出发，逐个扩展出子节点，并递规的调用自身来扩展子节点，直到无法再深度扩展为止。下面来看我们的第一个版本的解答。#define QMAX 30

9、typedef structint qn；/球的个数int owner；/所有者，0：没有所有者,1：属于player1,-1：属于player2sq_str；/上面的数据构造用来描绘堆的属性。sq_str aQMAX；/用来描绘棋局状态int n；/记录堆的个数，全局变量int depthmax=-1；/用来记录最深的递规深度，以便理解堆栈内存的使用使用下面的代码得到输入，当然后面我们会讨论随机生成棋局的方式，初始的棋局在这里就准备好void test1int i,j；int G,c；scanf%d%d,&n,&G；fori=0；i G；i+c=0；forj=0；j n；j+scanf%d,

10、&aj.qn；ifaj.qn=2ifc&1=0aj.owner=-1；/由player2所有else aj.owner=1；/由player1所有c+；else aj.owner=0；/无人所有depthmax=-1；c=qiuv00；printfresult：%d.depthmax=%d.n,c,depthmax；/求解棋局的函数，胜负是指player1的胜负。depth表示当前迭代的深度，同时也表示当前执子的玩家，depth为偶数，表示player1执子，depth为奇数，表示player2执子。/返回1：成功，-1：失败,0：和局int qiuv0int depthint i,j,k=0

11、,s,tx=0；int ret0；int fu=0；/会导致player1失败的节点的个数int shen=0；/会导致player1成功的节点的个数sq_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1/判断可行挪动步的标准，从第i堆到第j堆k+；/记录子节点的个数/保存被修改的堆，方便以后恢复savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifde

12、pth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；ret0=qiudepth+1；/递规调用/恢复被修改的棋局ai=savei；aj=savej；/请大家注意下面的不同处理，所有的胜负都是对于player1来说的ifdepth&1=0/player1的局势ifret0=1return 1；else ifret0=-1fu+；else/player2的局势ifret0=-1return-1；else ifret0=1shen+；ifk=0/假设没有子节点可以扩展，那么这是个终局fo

13、ri=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；else/否那么是扩展了子节点的ifdepth&1=0iffu=kreturn-1；/所有的走法都导致输else return 0；/至少有一种走发可以保证平局elseifshen=kreturn 1；/player2所有的走法都导致player1成功else return 0；/player2会选择平局三.初步的优化和剪枝好了程序很简单，应该很容易理解，但是效率也很低！下面我们来逐步分析优化，看看问题在哪里。首先我们发现，同层扩展出的各棋局的状态只和各堆的状态有关

14、，而和各堆的排列没有关系，所以在同一层我们就可以进展剪枝，把那些本质上是一样的子节点剪掉。考虑所有的走法一共有8种：4-2-1,1,4-1,4-0,3-1,3-0,2-1,1-0,括号里的数表示2堆的归属情况。新的程序如下：int qiuv1int depthint 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；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=

15、0；j n；j+ifai.qn-aj.qn 1k+；fors=0；s ti；s+ifai.owner=tts0.owner&ai.qn=tts0.qn&aj.owner=tts1.owner&aj.qn=tts1.qnbreak；ifs！=tiret0=res；ifdepth&1=0/player1的局势ifret0=1return 1；else ifret0=-1fu+；else/player2的局势ifret0=-1return-1；else ifret0=1shen+；continue；elsettti0=ai；ttti1=aj；savei=ai；savej=aj；ai.qn-；aj.q

16、n+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；ret0=qiudepth+1；reti=ret0；ti+；ai=savei；aj=savej；ifdepth&1=0/player1的局势ifret0=1return 1；else ifret0=-1fu+；else/player2的局势ifret0=-1return-1；else ifret0=1shen+；if

17、k=0fori=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；elseifdepth&1=0iffu=kreturn-1；/所有的走法都导致输else return 0；/至少有一种走发可以保证平局elseifshen=kreturn 1；/player2所有的走法都导致player1成功else return 0；/player2会选择平局四、进一步的优化和剪枝经过上面的优化，程序的性能有所提升，但是还不够快，问题出在哪里呢?我们知道深度优先搜索的一大缺点就是对已有的计算结果没有继承，造成了大量的计算浪费；qiuv

18、1已经做了一点工作，但还不够；我们需要记录所有的已经访问过的棋局和相应的结果，方便在后续的搜索中进展剪枝。这就需要对以往结果的记录。定义如下数据构造：#define STAMAX 11000 unsigned char x_staSTAMAX8；/player1的2就在2，player2的2在5,局势的结果放在7,depth的奇偶性放在6里int x_inx=0；/x_sta中的下一个空位置我们知道棋局只和堆本身有关，而和堆的排列顺序无关，进一步，两个一样的堆也是无区别的，这样我们只需要记录一个棋局中0堆的个数，1堆的个数,21堆的个数，2-1堆的个数,3堆的个数，4堆的个数，以及当前棋局对应

19、的执子方，这种棋局的结果。由于最多也就30堆，所以1个字节足以存放相关的信息。算算上面的空间才不到90KB，离1MB尚远。还有一个问题，那就是棋局的对偶性，棋局A的对偶棋局，就是把depth的奇偶性取反，把相应的2堆的归属性取反，相应的棋局结果自然取反。这个很容易理解，相当与player2和player1交换位置，下对方的棋。这样我们每求得一个棋局，实际上是得到了两个棋局的结果。好了还是看看新程序吧.int qiuv2int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；int shen=0；int old_xinx；unsigned char x7；sq

20、_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1k+；memsetx,0,7；savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；fors=0；s n；s+ifas.qn！=2xas

21、.qn+；elseifas.owner=1x2+；else x5+；x6=depth&1；/开场搜索以前保存的结果fors=0；s x_inx；s+ifmemcmpx,x_stas,7=0break；ifs！=x_inx/找到了！ai=savei；aj=savej；ret0=charx_stas7；ifdepth&1=0/player1的局势ifret0=1return 1；else ifret0=-1fu+；else/player2的局势ifret0=-1return-1；else ifret0=1shen+；continue；elsememcpyx_stax_inx,x,7；/每找到，把当

22、前棋局添加进去old_xinx=x_inx；/记录自己的位置，后面好吧结果填进去，因为下面的递规会参加新的内容到存储队列x_inx+；ret0=qiuv1depth+1；x_staold_xinx7=ret0；ai=savei；aj=savej；/把对偶的情况放进去memcpyx_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+；ifdepth&1=0/playe

23、r1的局势ifret0=1return 1；else ifret0=-1fu+；else/player2的局势ifret0=-1return-1；else ifret0=1shen+；ifk=0fori=0；i n；i+k+=ai.owner；ifk=0return 0；ifk 0return 1；ifk 0return-1；elseifdepth&1=0iffu=kreturn-1；/所有的走法都导致输else return 0；/至少有一种走发可以保证平局elseifshen=kreturn 1；/player2所有的走法都导致player1成功else return 0；/player2

24、会选择平局好了，这下我们的程序有了质的飞跃，速度进步很多，比v1版本进步了几个数量级！很开心-。五.HASH函数的应用但是当我们加大测试强度，把堆的数量推到顶，到达30之后，我们的程序还是不够快，对有的棋局，几乎半分钟内都解不出来，这是不能承受的。那好吧，看来我们还需要进一步优化。还有什么地方值得优化呢?就是下面这个地方！/开场搜索以前保存的结果fors=0；s x_inx；s+ifmemcmpx,x_stas,7=0break；通过测试发现，对于30堆的情况，我们的存储会有超过10000的情况，一般也会超过5000！对于这么大的存储空间，假设向上面那样每次都进展线性匹配，效率是很低下的，这也

25、就是为什么在堆变多之后，我们的程序变慢的原因。好了问题找到了，那么如何解决呢?还是有方法的，那就是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是索引，高

26、2bit：00空工程,01低14bit表示下一个的位置，10没有下一个了X_sta；/hash表X_sta hashSTAMAX；/占用160KB空间，实际测试，可以处理的堆数达35堆的情况/返回14bit的HASH值，我自己构造的hash函数unsigned short cal_hashunsigned char*in,int lenunsigned short x1=0；int i；fori=0；i len；i+x1=x1*11+ini0x3d；returnx1&0x3fff；int qiuv3int depthint i,j,k=0,s,tx=0；int ret0；int fu=0；in

27、t shen=0；int old_xinx；unsigned char x8；/把结果也含进来了unsigned short s_indx；int nexti；int find；sq_str savei,savej；ifdepth depthmaxdepthmax=depth；fori=0；i n；i+forj=0；j n；j+ifai.qn-aj.qn 1k+；memsetx,0,8；savei=ai；savej=aj；ai.qn-；aj.qn+；ifai.ownerai.owner=0；ifaj.owneraj.owner=0；ifai.qn=2ifdepth&1=0ai.owner=1；

28、else ai.owner=-1；ifaj.qn=2ifdepth&1=0aj.owner=1；else aj.owner=-1；fors=0；s n；s+ifas.qn！=2xas.qn+；elseifas.owner=1x2+；else x5+；x6=depth&1；find=0；s_indx=cal_hashx,7；/计算hash值作为索引nexti=s_indx；switchhashs_indx.pr 14/查看高两bit属性值case 0：/空项，直接填入memcpyhashnexti.x_sta,x,8；hashnexti.pr=0x8000；old_xinx=nexti；x_in

29、x+；break；case 1：/碰撞，那就顺着链条往下查找吧doifmemcmpx,hashnexti.x_sta,7=0find=1；break；nexti=hashnexti.pr&0x3fff；whilehashnexti.pr 14！=2；/这里直接滑入case2，因为到这里处理是一样的了case 2：/和最后一个进展比较ifmemcmpx,hashnexti.x_sta,7=0find=1；iffind=1/找到了一模一样的ai=savei；aj=savej；ret0=charhashnexti.x_sta7；ifdepth&1=0/player1的局势ifret0=1return

30、 1；else ifret0=-1fu+；else/player2的局势ifret0=-1return-1；else ifret0=1shen+；continue；/否那么就是没有找到，那么就只能拉拉链了，找一个空地方塞进去fors=0；s STAMAX；s+ifhashs.pr 14=0break；ifs=STAMAX/hash表满了！printferror hashtable full！；return-2；memcpyhashs.x_sta,x,8；hashs.pr=0x8000；/这几行就是在接拉链old_xinx=s；hashnexti.pr=s|0x4000；x_inx+；break

31、；default：printferror in pr！；break；ret0=qiuv1depth+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_hashx,7；/查找对偶情况，假设对偶情况已经在里面了，就不用添加了，否那么就需要添加nexti=s_indx；switchhashs_indx.pr 14case 0：x_inx+；memcpyhashnexti.x_sta,x,8；hashnexti.pr=0x8000；break；case 1：doifmemcmpx,hashnexti.x_sta,7=0find=1；break；nexti=hashnexti.pr&0x3fff；whilehashnexti.pr 14！=2；case 2：/和最后一个进展比较ifmemcmpx,hashnexti.x_sta,7=0find=1；iffind=0/否那么就是没有找到fors=0；s STAMAX；s+ifhashs.pr 14=0break；ifs=STAMAXprintferror hashtable full！；return-2；memcpyhashs.x_sta,x,8；hashs.pr