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

《从一个策略游戏谈搜索算法优化》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、从一个策略游戏谈搜索算法优化从一个策略游戏谈搜索算法优化对于策略游戏性质的二人博弈问题，比如黑白棋，五子棋等，一般的解答方法就是搜索；但搜索算法的原理不同，其性能就大不一样。一般来说，如果我们对问题的本质把握的越深，算法的设计就会相对的复杂，但是效率会高很多。下面我们就通过一个二人游戏来谈这方面的体会。一.问题的提出问题：TwoFour[罗马尼亚奥林匹克,viaStroe,2002]Bessie有一个新的两人游戏：TwoFour.她有N(3=N=30)堆球,每堆有nballs(0=nballs=4)个.球的总数为2

2、*N.玩这个游戏时,游戏者轮流执行一个有效移动.一个有效移动由下列动作组成：*第一,游戏者选择不同的两堆球.*第二,把一个球从一堆拿到另一堆.她可以这样做的前提是运完球后第二堆的球数(包括新放上的球)不大于第一堆剩下的球的数目.当没有移动可做时,游戏结束.实际上,在游戏的末尾,每堆将包含恰好两个球.游戏的胜者'拥有'多数球堆.平局是可能的.当某堆有两个球并且是由于某游戏者最近对它的的一次移动(不管移走还是放入)使其变为两个球的,我们就说她'拥有'这堆球.看看这些例子：*如果一个游戏者从有四个球的某球堆中移走一个球,

3、放到有一个球的某球堆中,那么它拥有了第二堆(有两个球).*如果一个游戏者从有三个球的某球堆中移走一个球,放到有零个球的某球堆中,那么它拥有了第一堆,现在这堆有两个球.*如果一个游戏者从有三个球的某球堆中移走一个球,放到有一个球的某球堆中,那么它拥有了这两堆(他们都有两个球).拥有权能够变化.设想一个游戏者拥有两个球的一个球堆,如果另一个游戏者选了一个有四个球的堆并把一个球移到此两个球的堆中,那么这堆球谁也不属于了.如果,在游戏的开头,存在有两个球的一些球堆,那么这些堆被平分给两个游戏者,剩余的堆则分给游戏者2.游戏

4、者1先移动.你的程序必须判断,对一个初始的游戏状态,谁将获胜或者会否出现平局.你的程序将处理G(1=G=1000)个游戏状态.该问题要求使用不超过1.00MB的内存.问题名：twofour输入格式：*行1：用空格隔开的两个整数：N和G.*行2.G+1：每行包含空格隔开的N个整数用于描述该游戏.第一个整数是堆1的球数,第二个整数是堆2的球数,.行2描述了游戏1,行3描述了游戏2,.你的程序应该计算每个特定游戏的胜者.输入样例(文件twofour.in)：5403412222221122443210输出格式：*行1.G

5、：每个游戏的结果.行1给出游戏1的结果,.结果是一个整数：1代表第一个游戏者获胜,2代表第二个获胜,以及0代表平局.输出样例(文件twofour.out)：1211二.问题的初步分析和第一种解答从问题的描述来看，我们可以得到如下的一些基本信息：1)player1总是先手的，问题也是求player1的胜负情况；player2在瓜分最初的'2'堆的时候具有优先权。2)整个的游戏过程，就是把不均有分布的堆，逐步均匀化，直至所有的堆都是'2'堆，由于2N个球，放置在N堆上，这是个必然。3)'2'堆在游戏过程中会变化成'1'

6、堆或者'3'堆；每堆的球数不超过4，允许'0'堆。4)如果两堆之间的球数目差1，就可以进行球的移动，这是我们在程序中判断可行步的依据。在上面的基本信息的基础上，我们就要决定用什么搜索算法，用广度优先搜索还是深度优先搜索呢?如果用广度优先搜索的话，一般的方法是从根节点出发，平行的推进所有从根节点衍生出来的子节点，每个节点都要保存当前棋局的状态,同时还要记住父节点的索引；子节点需要父节点的信息来进行衍生，而父节点需要子节点的结果来决定本节点的结果。一般我们用一个队列来实现这个过程；由于所有的节点都需要保存，一些废节点也

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

8、面考虑深度优先搜索。深度优先搜索有一个好处就是占用的空间少。先讲讲我们的思路，请大家注意对于player1和player2的处理的不同。1)我们对所有棋局的考虑都以player1为中心，不论当前棋局是由player1的移动还是player2的移动造成的.2)如果相对与当前棋局，对于player1的所有移动中，有一种能导致player1胜利，则当前节点就能导致