简单双人组合游戏

《简单双人组合游戏》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、简单的双人组合游戏新疆乌鲁木齐第一中学王栋目录：引言……………………………………………………………….2Nim游戏………………………………………………………….2Nim游戏的类似游戏…………………………………………….4棋盘上的游戏…………………………………………………….5总结……………………………………………………………….7参考文献………………………………………………………….7附录……………………………………………………………….8引言粗糙的说，组合游戏是两个玩家进行的公平游戏，他们会出现胜利(win)，失败(l

2、ose)，或者平局(tie)，和局(draw)。一个平局(tie)说明没有人胜利没有人失败。一个和局(draw)说明没有人再下面的游戏中能够胜利并且也不会失败。从主要的角度来说，一个组合游戏有两种大的形式Nim游戏和棋盘游戏：a.Nim游戏是无环的。而棋盘游戏可能有环，就是说棋盘游戏可能出现重复状态。b.Nim游戏可以不需要交互，而棋盘游戏是交互的。c.Nim游戏是公平的，两个人交换彼此的操作对状态没有影响；棋盘游戏是不公平的，两个人交换操作对最后的结果有影响。d.Nim游戏是有终止的；棋盘游戏基本没有终止。接下来，我们

3、来假设这么几点：设P状态表示刚完成走步的游戏者（PreviousPlayer）一定胜利的状态。设N状态为下一个走步的游戏者（NextPlayer）一定胜利的状态。那么我们可以得到下面这些定理：a.所有的终止状态一定是P状态。b.能到达P状态的状态为N状态。c.每一步都将到达N状态的状态为P状态。这样，有了这么一些定理，我们只要把一个游戏转化成有N个节点M条边有向无环图，就可以在O（m）的时间复杂度内对图拓扑排序，然后直接判断每个状态的胜负。在这里，我们主要讨论的是可以构建有向无环图的游戏。Nim游戏在这里，我们把目光注意

4、到Nim游戏中。首先，我们来观察这个游戏：有两个人A,B在玩游戏，桌上有一堆或者几堆筹码，按约定，两个人轮流取走一些或者全部筹码，取得最后一个筹码的人为胜利者，每个人都按自己最好的方式去玩，谁会胜利？这一类游戏，皆可用斯普拉格（R.Sprague）-格伦迪（P.M.Grundy）数G(0)予以分析。对于空的位置0，那里没有筹码，G(0)=0。对于数目分别为x,y,…的筹码堆的任意组合C=(x,y,…)，假如有容许取法使C变成别的组合D,E…，则G(C)是异于G(D),G(E)…得最小非负整数。这样就以归纳的方式定义了游戏

5、规则所容许的一切组合C的G(C)。若G(C)>0，下一个人，譬如说A,只要取码是局势走向一个“安全的”组合S，使G(S)=0就能确保胜利了。因为按G(S)的定义，或者S是空的位置，此时A已经胜利了，或者对手B必须走到一个新的“不安全”的位置U，G(U)>0，这就回到了讨论开始的情况，游戏以有限的步数结束而A获胜。在Nim游戏里可以有任意堆的筹码，每个参加者轮流选定一堆并从中随意取多少个（至少一个）筹码。G(x,y…)这时就是x,y…的“Nim和”，其中Nim加法的运算相当于计算机当中的“异或”操作。将x,y…换写为二进制

6、数，然后相加而暂无进位，最后将每个位上的数换为用2除后的余数，将此结果视为二进制数。例如求Nim和：，列式如下：十进制3=二进制11十进制7=二进制111十进制9=二进制1001相加但不进位1123Nim和1101为什么这样做是对的呢？我们可以参见一下02年集训队张一飞同学的论文。对于任何一个状态S，如果G(S)=0，那么无论先行者如何取筹码到达状态T，都有，即说明从先行者是必败的，我们来证明一下。a.先行者只能从其中一堆中去若干筹码，不妨设他选择的就是第一堆b.设先行者从第一堆中取了x个筹码，用T表示取完的状态c.设，

7、则d.G（S）=G（）+G（），故G（）=G（）e.G（T）=G（）+G（）=f.对于任何一个状态S，如果,那么先行者必然存在一种方案到达T，使得，即说明先行者必有策略到达安全状态，我们也来参照一下张一飞的证明。a．设，p=G(S)=b．因为p不等于0，所以必然存在k，使得，不妨设k=1，c．先行者将第一筹码的个数从变成x，用T来表示这个局面d．p=G（S）=，故=e．G(T)=G(x)+=x+G(x)=0通过上面两个证明，我们得知用这个游戏满足SG数的条件“对于G(C)>h0，则存在着由C到一个组合D的走动，这里G(D

8、)=h”。Nim和在计算机博弈中应用很多，在这里先给大家看一个小题：山洞里的游戏小林在探险的时候无意中掉进了一个山洞。洞口轰隆的一声被堵上了。他绝望的环顾四周，发现墙角有一个棋盘。棋盘是n*n的网格，旁边有一页说明书。小林仔细看了看，原来这是一个古老的游戏。棋盘的每个格子上都放着一枚硬币，硬币的一面是人、一面是数字。