文档介绍：该【游戏策略】是由【我是药仙】上传分享，文档一共【40】页，该文档可以免费在线阅读，需要了解更多关于【游戏策略】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。游戏策略
Nim问题的扩展
取石子问题
有N堆石子,其中第i堆有Pi颗石子,每次去掉某一堆里最多m棵石子(m>0),两人轮流取石,谁不能继续取谁就输了。
什么情况下先手必胜,什么情况下后手必胜?
示例m=2
a1=7
a2=3
a3=5
1234567
将P1P2P3…Pn对m+1求余得到P1’P2’P3’…Pn’,然后符合定理一的结果,记S=P1’XORP2’XORP3’XOR…XORPn’。若S=0则为P局面,否则为N局面。
证明:
将P1P2P3…Pn分解成为两部分P1’P2’P3’…Pn’和R1R2R3…Rn,其中R1R2R3…Rn都是m+1的倍数。
若对P1’P2’P3’…Pn’部分取子,则按NIM方法走步,若对R1R2R3…Rn部分取子,则后手取k颗,先手方取m-k+1颗,先手始终保持不对R1R2R3…Rn部分先取子。
若初始局面为胜局面,P1’P2’P3’…Pn’部分NIM方法取子必胜,由于R1R2R3…Rn都为m+1的倍数,因此,按m+1互补的取法,先手一定能取到最后K<=m颗石子。
结论
Nimk问题
取石子问题
有N堆石子,其中第i堆有Pi颗石子,每次可以从最多K堆中选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就输了。
什么情况下先手必胜,什么情况下后手必胜?
结论
K=1,为Nim问题。
对于K>1的情况,我们令把P1~Pn这n个数,转成二进制,然后每位分别相加,每位最后结果mod(K+1)即可。如果每一位结果都是0,则为P局面,否则是N局面
示例
P1P2P3P4=3,5,10,15,K=2
3——————11
5——————101
10——————1010
15——————1111
2200
所以这是N局面。
证明与NIM证明类似。下面我们看看具体的取法。
Nimk问题的取石子方法
设P1P2P3…Pn为n堆石子数目。Pi已标记的石子堆,D0[i]和D1[i]分别表示所有已标记的石子堆中第i位为0和1的总数。
,设为W。
、而且未标记的石子堆Pi,将Pi标记,并把它的第W位由1改为0。对于Pi的第1到(W-1)位,逐个判断,第j位如果为0则Inc(D0[j]),否则Inc(D1[j])。
(即S[i]≠0),且S[i]+D0[i]>K,或S[i]-D1[i]<1,可以通过修改以前已标记的石子堆将S[i]修正为0。
,则确认所有已经做的更改,并结束;否则转到1。
MisèreNim问题
取石子问题
有N堆石子,每次从某一堆里选出若干石子去掉(但不能不去石子),两人轮流取石,谁不能继续取谁就赢了。
什么情况下先手必胜,什么情况下后手必胜?
第一堆:a1=3
第二堆:a2=3
第三堆:a3=1
结论
所有石子堆的数目都为1:显然,若有偶数堆石子堆,则必胜,否则必败。
如果恰好只有一堆石子数目大于1。我们可以把这堆石子取完或者取得只剩下1,使得只剩下奇数堆数目为1的石子留给对方,由1),必胜。
如果有至少2堆石子的数目大于1。
考虑异或值:若异或值不为0,则按照Nim走法取石。这样,当对手某次取完石子后,肯定会出现情况2,必胜。
证明:按照Nim走法则取完石子后,必定会给对手留下异或值为0的局面。因此不可能给对手留下情况2的局面(容易证明,情况2局面的异或值肯定不为0),而对手一次最多将一堆石子数大于1的石子堆处理掉。因此情况2的情况肯定会出现。
相反,若异或值为0,则无论如何走都会给对方留下情况2或情况3的情况,必败。
SG函数简介
如果我们把游戏中的某一个局面看作一个顶点,把局面之间的转换用边来表示,那么很多游戏都可以转化成图游戏模型。
图游戏模型给定有向无环图G=(V,E)和一个起始点,双方轮流行动。每个人每次可以从当前点出发沿着一条有向边走到另外一个点。谁无法走了谁就输。
一些图游戏可以通过Sprague-Grundy函数来判定先手的胜负情况(简称SG函数)。
SG函数一个图G=(V,E)的SG函数g,是定义在v上的一个非负整数函数:
g(x)=min{n>=0|n≠g(y)for<x,y>∈E}
如果x的出度为0,那么g(x)=0。(边界条件)