必威体育Betway必威体育官网
当前位置:首页 > IT技术

浅谈算法——博弈论

时间:2019-06-25 21:44:18来源:IT技术作者:seo实验室小编阅读:96次「手机版」
 

博弈论论文

转载说明

https://www.cnblogs.com/Wolfycz/p/8430991.html

https://www.luogu.org/blog/Wolfycz/qian-tan-suan-fa-bo-yi-lun-zong-ling-kai-shi-di-bo-yi-lun-post

以上是原文链接,请大家资瓷原创。


网上的博弈博客和论文有很多,但是有些没有详细的证明,仅仅是给出了结论。今天作者将一些常见的博弈论模板集中起来,给大家介绍一下博弈论中一些单一游戏的决策和常见的Nim模板与证明。

注:下列游戏都建立在双方都有最优策略的情况下,若未加以说明,则每人每次至少取一个石子。

例1:取石子游戏之一

有两个游戏者:A和B。有n颗石子。

约定:两人轮流取走石子,每次可取1、2或3颗。A先取,取走最后一颗石子的人获胜。

问题:A有没有必胜的策略?

分析:这是小学必备奥数题之一,我们可以很容易的知道,当n为0,4,8,12……时,A必定会输,因为不论A取多少,B只要和A共同取走4即可;当n不为0,4,8,12……时,A只需要将n取成4的倍数,这样就变成了B先取,B一定会输,所以A一定会赢。

经过我们的分析发现,对这个游戏而言,0,4,8,12……这些状态是对于先手的必败状态,而其他状态是对于先手的必胜状态,因此,我们现在介绍一下有关博弈的一些名词和概念

1、平等组合游戏

  • 两人游戏。
  • 两人轮流走步。
  • 有一个状态集,而且通常是有限的。
  • 有一个终止状态,到达终止状态后游戏结束。
  • 游戏可以在有限的步数内结束。
  • 规定好了哪些状态转移是合法的。
  • 所有规定对于两人是一样的。

因此我们的例1提到的游戏即为一个平等组合游戏,但是我们生活中常见的棋类游戏,如象棋、围棋等,均不属于平等组合游戏,因为双方可以移动的棋子不同,不满足最后一个条件;而我们后续提到的游戏,以及博弈中的其他游戏,基本属于平等组合游戏

2、N状态(必胜状态),P状态(必败状态)

像例1的分析一样,0,4,8,12……等状态就是对于先手的P状态(必败状态),其他的则是对于先手的N状态(必胜状态)。

那么我们定义两个状态之间的转换:

  • 所有的终止状态都为P状态
  • 对于任意的N状态,存在至少一条路径可以转移到P状态
  • 对于任意的P状态,只能转移到N状态

证明过于简单,这里不再赘述,我们只需要明白一点,每个人都会选择最策略即可。

当然这里所说的都是最后走步的人获胜的游戏,至于那些走到最后失败的游戏,我们在最后做了一个简单的讲解(Anti Nim)。

例2:取石子游戏之二

将例1的游戏扩展一下,我们定义一个集合S={p1,p2,...,pk}(kZ)S=\{{p_{1},p_{2},...,p_{k}}\}(k \in Z^*)S={p1​,p2​,...,pk​}(k∈Z∗),A,B在游戏的时候取走的石子数必须是集合里的数,其他条件不变。

那么,A还有必胜策略吗?

有没有必胜策略,我们关键是要找到哪些状态是P状态,哪些状态是N状态,不过,本题没有例1那么容易判断,因此我们需要引入一个新东西——SG函数,它的定义如下:

f(v)=mex{f(u)uv}f(v)=mex\{f(u)|u为v的后继状态\}f(v)=mex{f(u)∣u为v的后继状态}

其中,mex(Minimal excludant)是定义在整数集合上的操作。它的自变量是任意整数集合,函数值是不属于该集合的最小自然数。

mex(A)=min{kkNA}mex(A)=min\{k|k \in \complement_{N}A\}mex(A)=min{k∣k∈∁N​A}

那么,终止状态的SG值显然为0,并且SG值为0的状态就是P状态,SG值不为0的状态就是N状态。

证明则非常显然,SG值为0的状态,说明它的所有后继状态都不为0,也就是它只能转移到非0状态,而SG值不为0的状态则不一样。那么SG值为0的状态就是必败状态的定义,SG值不为0的状态就是必胜状态的定义,所以我们只需要用集合S求出每个状态的SG值即可。

类似代码请见Pku2960 S-Nim

例3:取石子游戏之三

有n个石子,A,B两人轮流取石子,规定他们每次至多只能取当前石子总数s2\lceil \dfrac{s}{2}\rceil⌈2s​⌉个石子,问A先手是否有必胜策略

这题主要是为了加强大家对SG函数的理解,我们考虑从0开始

SG(0)=0,SG(1)=1,SG(2)=0,SG(3)=mex{SG(31),SG(32)}=2SG(0)=0,SG(1)=1,SG(2)=0,SG(3)=mex\{SG(3-1),SG(3-2)\}=2SG(0)=0,SG(1)=1,SG(2)=0,SG(3)=mex{SG(3−1),SG(3−2)}=2

SG(4)=mex{SG(41),SG(42)}=1...SG(4)=mex\{SG(4-1),SG(4-2)\}=1...SG(4)=mex{SG(4−1),SG(4−2)}=1...

我们把他们列出来找下规律:

0,1

0,2,1,3

0,4,2,5,1,6,3,7

0,8,4,9,2,10…

好像有个很奇怪的规律:数列在间隔递增,上一行的数间隔着插在下一行的数中间。没错,这就是本题SG函数的规律,先手必败当且仅当SG值为0。

例4:取石子游戏之四(Nim游戏)

有n堆石子,石子数目分别为x1,x2,...,xnx_{1},x_{2},...,x_{n}x1​,x2​,...,xn​,A,B两人每次可以选一堆石子取走任意多个,问A先手是否有必胜策略。

这题相当于例2的扩展版本,由于这里有多堆石子,因此我们可以得到多个SG值,而且这些SG值必定为x1,x2,...,xnx_{1},x_{2},...,x_{n}x1​,x2​,...,xn​,那么我们怎么由这一些SG值得到整局游戏的SG值呢?

Nim游戏的神奇之处在于它的SG值和异或扯上了关系,Nim游戏中先手必败当且仅当x1x2...xn=0,()x_{1}\oplus x_{2}\oplus...\oplus x_{n}=0,(\oplus 为异或)x1​⊕x2​⊕...⊕xn​=0,(⊕为异或),那么,这个为什么是成立的?

首先,\oplus⊕满足如下定律和性质

  • 交换律:xy=yxx\oplus y=y\oplus xx⊕y=y⊕x
  • 结合律:x(yz)=(xy)zx\oplus(y\oplus z)=(x\oplus y)\oplus zx⊕(y⊕z)=(x⊕y)⊕z
  • 拥有单位元:0x=x0\oplus x=x0⊕x=x
  • 相同两数运算为0:xx=0x\oplus x=0x⊕x=0
  • 消除律:xy=xzy=zx\oplus y=x\oplus z\Rightarrow y=zx⊕y=x⊕z⇒y=z

当Nim游戏的SG值为0时,我们假定取xkx_{k}xk​中的某些石子,使得其变成xkx_{k}'xk′​,我们假设x1x2...xk...xn=0=x1x2...xk...xnx_{1}\oplus x_{2}\oplus...\oplus x_{k}\oplus...\oplus x_{n}=0=x_{1}\oplus x_{2}\oplus...\oplus x_{k}'\oplus...\oplus x_{n}x1​⊕x2​⊕...⊕xk​⊕...⊕xn​=0=x1​⊕x2​⊕...⊕xk′​⊕...⊕xn​,根据消除律可得,xk=xkx_{k}=x_{k}'xk​=xk′​,这与我们的条件相矛盾,因此说明在取了石子之后,SG必然发生了改变;

那么对于一个SG值不为0的状态,我们必然可以通过一个操作,使得SG值变0。我们只需要找到当前SG最左端为1的一列(二进制),任意找到一堆石子使得那一列同样为1,从这堆中取走若干个石子,使得SG’值为0。这是显然可以的,因为将那一列变成0,这个数就必然变小了,对于其他列只需要把0变成1,1变成0即可。

因此,我们得到,对于Nim游戏而言,必败状态当且仅当x1x2...xn=0x_{1}\oplus x_{2}\oplus...\oplus x_{n}=0x1​⊕x2​⊕...⊕xn​=0,对于其他情况,先手必能使当前局面变成必败状态。

代码请见Pku2975 Nim

例5:取石子游戏之五(Wythoff’s Game)

有两堆石子,个数为x1,x2x_{1},x_{2}x1​,x2​;A,B轮流取石子,规定要么只取一堆的任意多个,要么在两堆里取同样任意多个,问A先手是否有必胜策略。

这种情况下是颇为复杂的,普通SG函数已经无法解决这个问题。我们用(ak,bk),(akbk,k[0,n])(a_{k},b_{k}),(a_{k} \le b_{k},k \in [0,n])(ak​,bk​),(ak​≤bk​,k∈[0,n])表示两堆物品的数量并称其为局势,如果甲面对(0,0)(0,0)(0,0),那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是:(0,0)(1,2)(3,5)(4,7)(6,10)(8,13)(9,15)(11,18)(12,20)(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)

可以看出,a0=b0=0a_{0}=b_{0}=0a0​=b0​=0,aka_{k}ak​是未在前面出现过的最小自然数,而bk=ak+kb_{k}=a_{k}+kbk​=ak​+k,奇异局势有如下三条性质:

  • 1.任何自然数都包含在一个且仅有一个奇异局势中。
  • 2.任意操作都可将奇异局势变为非奇异局势。
  • 3.采用适当的方法,可以将非奇异局势变为奇异局势。

证明:

  • 1.由于aka_{k}ak​是未在前面出现过的最小自然数,所以有ak>ak1a_{k}>a_{k-1}ak​>ak−1​ ,而bk=ak+k>ak1+k1=bk1>ak1b_{k}=a_{k}+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}bk​=ak​+k>ak−1​+k−1=bk−1​>ak−1​ 。所以性质1,成立。

  • 2.若只改变奇异局势(ak,bk)(a_{k},b_{k})(ak​,bk​)的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势。如果使(ak,bk)(a_{k},b_{k})(ak​,bk​)的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。

  • 3.假设面对的局势是(a,b)(a,b)(a,b),若 a=ba=ba=b,则同时从两堆中取走aaa 个物体,就变为了奇异局势(0,0)(0,0)(0,0);如果a=ak,b&gt;bka=a_{k},b&gt;b_{k}a=ak​,b>bk​,那么,取走bbkb–b_{k}b–bk​个物体,即变为奇异局势;如果a=ak,b&lt;bka=a_{k},b&lt;b_{k}a=ak​,b<bk​,则同时从两堆中拿走akabaka_{k}–a_{b–ak}ak​–ab–ak​个物体,变为奇异局势(abak,abak+bak);(a_{b–a_{k}},a_{b–a_{k}}+b–a_{k});(ab–ak​​,ab–ak​​+b–ak​);如果a&gt;ak,b=ak+ka&gt;a_{k},b=a_{k}+ka>ak​,b=ak​+k,则从第一堆中拿走多余的数量aaka–a_{k}a–ak​即可;如果a&lt;ak,b=ak+ka&lt;a_{k},b=a_{k}+ka<ak​,b=ak​+k,分两种情况:第一种,a=aj,(j&lt;k)a=a_{j},(j&lt;k)a=aj​,(j<k),从第二堆里面拿走bbjb–b_{j}b–bj​即可;第二种,a=bj,(j&lt;k)a=b_{j},(j&lt;k)a=bj​,(j<k),从第二堆里面拿走bajb–a_{j}b–aj​即可。

从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。

而且,通过如上性质,我们可以发现,an,bna_{n},b_{n}an​,bn​很像Beatty数列。其实,an,bna_{n},b_{n}an​,bn​就是Beatty数列

Beatty数列和Beatty定理:

取正无理数α,β\alpha,\betaα,β,使得1α+1β=1\frac{1}{\alpha}+\frac{1}{\beta}=1α1​+β1​=1

构造两个数列an,bna_{n},b_{n}an​,bn​,它们的通项为an=αn,bn=βna_{n}=\lfloor{\alpha n}\rfloor,b_{n}=\lfloor{\beta n}\rflooran​=⌊αn⌋,bn​=⌊βn⌋

那么这个数列显然是正整数序列,Beatty定理指出,两个数列都是严格递增的,并且每个正整数在两个数列中只出现一次

证明:

  • 1.单调性:因为1α&lt;1,α&gt;1\frac{1}{\alpha}&lt;1,\alpha&gt;1α1​<1,α>1,所以αn1&gt;α(n1)\alpha n-1&gt;\alpha (n-1)αn−1>α(n−1),所以an1&gt;an1a_{n}-1&gt;a_{n-1}an​−1>an−1​,bnb_{n}bn​也亦然如此。
  • 2.完备性:我们要证明这个命题,只需要证明对于任意一个k,(kZ)k,(k \in Z^*)k,(k∈Z∗),小于等于kkk的数在序列中出现了k1k-1k−1次即可。

    设数列ana_{n}an​的前ppp项小于等于kkk(不包括p+1p+1p+1项),又因为每项取整前为无理数,不可能取到整数值,那么就有

    {αp&lt;k+1α(p+1)&gt;k+1\begin{cases}\alpha p&lt;k+1\\\alpha (p+1)&gt;k+1\end{cases}{αp<k+1α(p+1)>k+1​

    合并两式,得到p=k+1αp=\lfloor\frac{k+1}{\alpha}\rfloorp=⌊αk+1​⌋,这就是小于等于kkk的数在ana_{n}an​中的出现次数,同理,我们可以得到其在bnb_{n}bn​中的出现次数,那么我们有小于等于kkk的数在Beatty数列中的总出现数S=k+1α+k+1βS=\lfloor\frac{k+1}{\alpha}\rfloor+\lfloor\frac{k+1}{\beta}\rfloorS=⌊αk+1​⌋+⌊βk+1​⌋

    注意到两个取整函数中的数都是无理数,于是我们就有严格的不等式

    (k+1α1)+(k+1β1)&lt;S&lt;k+1α+k+1β(\frac{k+1}{\alpha}-1)+(\frac{k+1}{\beta}-1)&lt;S&lt;\frac{k+1}{\alpha}+\frac{k+1}{\beta}(αk+1​−1)+(βk+1​−1)<S<αk+1​+βk+1​

    于是有k1&lt;S&lt;k+1k-1&lt;S&lt;k+1k−1<S<k+1,那么S=kS=kS=k,证毕。

我们回到之前的奇异局势,由于奇异局势中的an,bna_{n},b_{n}an​,bn​序列满足Beatty数列,那么同样满足其构造方法,即an=αn,bn=βna_{n}=\lfloor\alpha n\rfloor,b_{n}=\lfloor\beta n\rflooran​=⌊αn⌋,bn​=⌊βn⌋且1α+1β=1\frac{1}{\alpha}+\frac{1}{\beta}=1α1​+β1​=1。

因为an+n=(α+1)n=bna_{n}+n=(\alpha +1)n=b_{n}an​+n=(α+1)n=bn​,所以1α+1α+1=1\frac{1}{\alpha}+\frac{1}{\alpha +1}=1α1​+α+11​=1,解得α=5+12\alpha=\frac{\sqrt{5}+1}{2}α=25​+1​

那么,我们就得到了通项式:ak=k5+12,bk=ak+ka_{k}=\lfloor{k*\frac{\sqrt{5}+1}{2}}\rfloor,b_{k}=a_{k}+kak​=⌊k∗25​+1​⌋,bk​=ak​+k

所以对于任意局势,先手必败当且仅当局势为奇异局势,我们只需要用通项式判断其是否为奇异局势即可。

代码请见[SHOI2002]取石子游戏之三

例6:取石子游戏之六(Fibonacci Nim)

有一堆个数为n的石子,A,B轮流取石子,满足:

  • 先手不能在第一次把所有的石子取完;
  • 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。

约定取走最后一个石子的人为赢家,问A先手是否有必胜策略。

这个和之前的Wythoff’s Game和取石子游戏有一个很大的不同点,就是游戏规则的动态化。之前的规则中,每次可以取的石子的策略集合是基本固定的,但是这次有规则:一方每次可以取的石子数依赖于对手刚才取的石子数。

这个游戏叫做Fibonacci Nim,肯定和Fibonacci数列:1,2,3,5,8,13,21,34,55,89,… 有密切的关系。如果试验一番之后,可以猜测:先手胜当且仅当n不是Fibonacci数。换句话说,必败态构成Fibonacci数列

就像Wythoff博弈需要Beatty定理来帮忙一样,这里需要借助Zeckendorf定理(齐肯多夫定理)

Zeckendorf定理(齐肯多夫定理)

任何正整数可以表示为若干个不连续的Fibonacci数之和。

证明:

我们以FibnFib_{n}Fibn​代表Fibnacci数列的第nnn项,m,(mZ)m,(m \in Z^*)m,(m∈Z∗),易知当m=1,2,3m=1,2,3m=1,2,3时,该定理都成立,那么我们运用数学归纳法:假定该定理对所有小于mmm的数都成立,我们只要证明该定理对mmm成立即可。

  • mmm为FibFibFib数时,该定理成立
  • mmm不为FibFibFib数时,设Fibp1&lt;m&lt;Fibp1+1Fib_{p_{1}}&lt;m&lt;Fib_{p_{1}+1}Fibp1​​<m<Fibp1​+1​。

    m=mFibp1&lt;Fibp1+1Fibp1=Fibp11m&#x27;=m-Fib_{p_{1}}&lt;Fib_{p_{1}+1}-Fib_{p_{1}}=Fib_{p_{1}-1}m′=m−Fibp1​​<Fibp1​+1​−Fibp1​​=Fibp1​−1​,即m&lt;Fibp1m&#x27;&lt;Fib_{p-1}m′<Fibp−1​

    因为m&lt;mm&#x27;&lt;mm′<m,又因为归纳法假设mm&#x27;m′可以表示成不连续的Fibnacci数列之和,即m=Fibp2+Fibp3+...+Fibpt,(p2&gt;p3&gt;...&gt;pt)m&#x27;=Fib_{p_{2}}+Fib_{p_{3}}+...+Fib_{p_{t}},(p_{2}&gt;p_{3}&gt;...&gt;p_{t})m′=Fibp2​​+Fibp3​​+...+Fibpt​​,(p2​>p3​>...>pt​)且不是连续的整数,又因为m&lt;Fibp11m&#x27;&lt;Fib_{p_{1}-1}m′<Fibp1​−1​,所以p2&lt;p11p_{2}&lt;p_{1}-1p2​<p1​−1,即p1,p2p_{1},p_{2}p1​,p2​也不是连续的整数。

    m=m+Fibp1=Fibp1+Fibp2+...+Fibpt,(p1&gt;p2&gt;...pt)m=m&#x27;+Fib_{p_{1}}=Fib_{p_{1}}+Fib_{p_{2}}+...+Fib_{p_{t}},(p_{1}&gt;p_{2}&gt;...p_{t})m=m′+Fibp1​​=Fibp1​​+Fibp2​​+...+Fibpt​​,(p1​>p2​>...pt​)且不是连续的整数,所以该定理成立

所以**Zeckendorf定理(齐肯多夫定理)**对所有的m,(mZ)m,(m \in Z^*)m,(m∈Z∗)都成立

Fibnacci数列的必败证明:

首先给出三个定理,之后证明需要用到:

Fibn+1&lt;2Fibn&lt;Fibn+2Fib_{n+1}&lt;2*Fib_{n}&lt;Fib_{n+2}Fibn+1​<2∗Fibn​<Fibn+2​

Fibn+2&lt;3FibnFib_{n+2}&lt;3*Fib_{n}Fibn+2​<3∗Fibn​

4Fibn&lt;3Fibn+1,(4Fibn&lt;3(Fibn+Fibn1)Fibn&lt;Fibn+1&lt;3Fibn1)4*Fib_{n}&lt;3*Fib_{n+1},(4*Fib_{n}&lt;3*(Fib_{n}+Fib_{n-1})\Rightarrow Fib_{n}&lt;Fib_{n+1}&lt;3*Fib_{n-1})4∗Fibn​<3∗Fibn+1​,(4∗Fibn​<3∗(Fibn​+Fibn−1​)⇒Fibn​<Fibn+1​<3∗Fibn−1​)

同样运用数学归纳法:

  • i=2i=2i=2时,先手只能取1颗,显然必败,结论成立。
  • 假设当iki \leqslant ki⩽k时,结论成立。

    则当i=k+1i=k+1i=k+1时,Fibi=Fibk+Fibk1Fib_{i}=Fib_{k}+Fib_{k-1}Fibi​=Fibk​+Fibk−1​。

    则我们可以把这一堆石子看成两堆,简称kkk堆和k1k-1k−1堆。

    (一定可以看成两堆,因为假如先手第一次取的石子数大于或等于Fibk1Fib_{k-1}Fibk−1​,则后手可以直接取完FibkFib_{k}Fibk​,因为Fibk&lt;2Fibk1Fib_{k}&lt;2*Fib_{k-1}Fibk​<2∗Fibk−1​)

    对于k1k-1k−1堆,由假设可知,不论先手怎样取,后手总能取到最后一颗。下面我们分析一下后手最后取的石子数xxx的情况。

    如果先手第一次取的石子数yFibk13y \geqslant \dfrac{Fib_{k-1}}{3}y⩾3Fibk−1​​,则这小堆所剩的石子数小于2y2y2y,即后手可以直接取完,此时x=Fibk1yx=Fib_{k-1}-yx=Fibk−1​−y,则x2Fibk13x \leqslant \dfrac{2*Fib_{k-1}}{3}x⩽32∗Fibk−1​​。

    我们来比较一下2Fibk13\dfrac{2*Fib_{k-1}}{3}32∗Fibk−1​​与Fibk2\dfrac{Fib_{k}}{2}2Fibk​​的大小。即4Fibk14*Fib_{k-1}4∗Fibk−1​与3Fibk3*Fib_{k}3∗Fibk​的大小,我们已经得出后者大。

    所以我们得到,x&lt;Fibk2x&lt;\dfrac{Fib_{k}}{2}x<2Fibk​​。

    即后手取完k1k-1k−1堆后,先手不能一下取完kkk堆,所以游戏规则没有改变,则由假设可知,对于kkk堆,后手仍能取到最后一颗,所以后手必胜。

    i=k+1i=k+1i=k+1时,结论依然成立。

对于不是Fibonacci数列,首先进行分解。

分解的时候,要取尽量大Fibonacci数

比如分解85:

85在55和89之间,于是可以写成85=55+30,然后继续分解30,30在21和34之间,所以可以写成30=21+9,依此类推,最后分解成85=55+21+8+1。

则我们可以把nnn写成n=Fibp1+Fibp2++Fibpk,(p1&gt;p2&gt;&gt;pk)n=Fib_{p_{1}}+Fib_{p_{2}}+……+Fib_{p_{k}},(p_{1}&gt;p_{2}&gt;……&gt;p_{k})n=Fibp1​​+Fibp2​​+……+Fibpk​​,(p1​>p2​>……>pk​)

我们令先手先取完FibpkFib_{p_{k}}Fibpk​​,即最小的这一堆。由于各个FibFibFib之间不连续,则pk1&gt;pk+1p_{k-1}&gt;p_{k}+1pk−1​>pk​+1,则有Fibpk1&gt;2FibpkFib_{p_{k-1}}&gt;2*Fib_{p_{k}}Fibpk−1​​>2∗Fibpk​​。即后手只能取Fibpk1Fib_{p_{k-1}}Fibpk−1​​这一堆,且不能一次取完。

此时后手相当于面临这个子游戏(只有Fibpk1Fib_{p_{k-1}}Fibpk−1​​这一堆石子,且后手先取)的必败态,即先手一定可以取到这一堆的最后一颗石子。

同理可知,对于以后的每一堆,先手都可以取到这一堆的最后一颗石子,从而获得游戏的胜利。

代码请见[Coci2010]HRPA

例7:取石子游戏之七(Staircase Nim)

有n堆石子,每堆石子的数量为x1,x2,...,xnx_{1},x_{2},...,x_{n}x1​,x2​,...,xn​,A,B轮流操作,每次可以选第k堆中的任意多个石子放到第k-1堆中,第1堆中的石子可以放到第0堆中,最后无法操作的人为输。问A先手是否有必胜策略。

这就是一个Staircase Nim,它其实可以通过一些转化变成我们所熟知的Nim游戏,先手必败当且仅当奇数阶梯上的石子数异或和为0,那么为什么是这样呢?

假如我们是先手,我们就按照这个方法将多余的石子从奇数堆移动到偶数堆里面。此后如果对手移动的是奇数堆,我们就继续移动奇数堆使得SG值重新变为0;如果对手移动的是偶数堆,我们就将他移动到奇数堆中的石子继续往下移。这样经过多次操作我们总能使奇数堆保持必胜状态,最后我们总可以在对手之后将石子从奇数堆移动到偶数堆,最后移动到第0堆,这样对手就不能移动了。

所以通过整个过程我们可以发现,偶数堆中的石子不会影响整个游戏的结果,只有奇数堆中的石子会影响游戏结果。

因此对这个游戏而言,先手必败当且仅当奇数堆中的石子数异或和为0。

类似代码请见Poi2004 GRA

例8:取石子游戏之八(Anti Nim)

本题为例4(Nim 游戏)的变相版本,其他条件均不变,唯独定义:取到最后一个石子的人为输。那么A先手是否有必胜策略?

这题和Nim游戏非常类似,就是输赢的条件不同,但是这个游戏的胜利状态却和Nim有一些区别,这个游戏的的胜利当且仅当:

  • 所有堆石子数都为1且SG值为0
  • 至少有一堆石子数大于1且SG值不为0

我们对这个游戏进行分析,将其分为两种情况:

  • 所有堆的石子数均为1
  • 至少有一堆石子数大于1

对于第一种情况而言,我们可以很容易得到当堆数为奇数时,先手必败,否则先手必胜。

对于第二种情况而言,我们分两种情况进行讨论:

  • 当SG值不为0时:

    若还有两堆石子数目大于1时,我们将SG值变为0即可;若只有一堆石子 数目大于1时,我们总可以让状态变成有奇数个1。所以当SG不为0时,先手必胜。

  • 当SG值为0时:

    这样的话至少会有两堆石子的数目大于1,那么先手决策完之后,必定会使局面的SG值不为0,这样便到了先手必胜局。所以当SG为0时,先手必败。

代码请见[SHOI2008]小约翰的游戏

但是上述有关的推导只对于Anti Nim成立,对与Anti SG-组合游戏这个推论是不成立的,因此Anti SG-组合游戏的推论我们是需要重新证明的。不过这篇博客主要讨论单一游戏的决策问题,因此对于SG-组合游戏不予以讨论,有兴趣的读者可以参考贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》

相关阅读

详细解读百度搜索细雨算法2.0

  对前阵子即将上线的细雨算法2.0,百度官方近日给出了针对细雨算法2.0的具体问题的错误示例和整改建议,帮助站长们具体地理解细雨

启发式算法

现代启发式算法 启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启

MD5算法

MD5算法最近看了一个MD5的视频,突然发现MD5挺意思的,所以记录一下代码(写好封装),没准以后要用。也为一些寻找MD5算法的人提供便利。MD

数据结构与算法(一)---重点复习知识

吐槽 国庆假期第二天,去实验室开门,给猫猫铲丑丑,然后给她换猫粮,换水,喂这货吃的emmmmmm,然后今天就把之前在极客时间上买的数据结构与

模拟退火算法总结

Metropolis准则——以概率接受新状态 固体退火问题介绍 退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温

分享到:

栏目导航

推荐阅读

热门阅读