GameTheory

发表于
本文字数： 6k 阅读时长 ≈ 5 分钟

几个博弈论相关的游戏，挺有趣的，随手记录了

Bash Game

桌上有n个苹果，两人轮流从苹果堆中取苹果，规定每次最少取一个，最多取m个。最后取光者获胜

分析

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余苹果，后者必胜

发现取胜法则：如果n=(m+1)*r+s(r为任意自然数，1≤s≤m)，则先取者拿走s个苹果，如果后取者拿走k（1≤k≤m)个，那么先取者再拿走m+1-k个，结果剩下(m+1)*(r-1)个，以后保持这样的取法，那么先取者肯定获胜。总之，保持给对手留下苹果数为(m+1)的倍数，就能最后获胜

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;

int main()
{
	//n为桌上苹果数，m为一次最多拿取苹果数
	cin >> n >> m;
	if (n % (m + 1) == 0)
		cout << "后手胜！" << endl;
	else
		cout << "先手胜！" << endl;
}

Wythoff’s Game

桌上有两堆苹果，两人轮流从中拿取苹果

每一轮，你有两种拿取策略可以选择

第一种策略：你可以选择其中一堆，从中拿取至少一个苹果，至多拿完该堆苹果

第二章策略：你可以从两堆中拿取相同数目的苹果

将桌上苹果全部取完者获胜

示例

起始时，桌上有两堆苹果,第一堆有5个苹果,第二堆有7个苹果(5,7)

第一轮,Mike从第二堆拿走4个苹果,现在桌上苹果为(5,3)

第二轮,Nancy从两堆各拿走2个苹果,现在桌上苹果为(3,1)

第三轮,Mike从第一堆拿走1个苹果,现在桌上苹果为(2,1)

第四轮,Nancy从第一堆拿走1个苹果,现在桌上苹果为(1,1)

第五轮,Mike从两堆各拿走1个苹果,现在桌上苹果为(0,0)

Mike胜利!

分析

设（ai,bi）（ai≤bi ,i=0，1，2，…)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）

任给一个局势（a，b），如下公式判断它是不是奇异局势： ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,方括号表示向下取整）

奇异局势性质

1.任何自然数都包含在一个且仅有一个奇异局势中

由于a[k]是未在前面出现过的最小自然数，所以有ak>ak-1
而bk=ak+k>ak-1+k>ak-1+k−1=bk-1>ak-1

2.任意操作都可将奇异局势变为非奇异局势

这个性质可以简单的理解为：必败态的后继一定都是必胜态

事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势

3.采用适当的方法，可以将非奇异局势变为奇异局势

假设面对的局势是(a,b)，若b=a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）
如果a=ak，b>bk，那么，取走b−bk个物体，即变为奇异局势
如果a=ak，b<bk，则同时从两堆中拿走a−ab-a个物体变为奇异局势（ ab-a, b-a+ab-a）
如果a>ak，b=ak+k，则从第一堆中拿走多余的数量a-ak即可
如果a<ak，b=ak+k，分两种情况
第一种，a=aj（j<k），从第二堆里面拿走b−bj即可
第二种，a=bj（j<k），从第二堆里面拿走b−aj即可

证明

由数学-贝蒂定理结论，考虑

an=[αn],bn=[βn]

an+n =[(α+1)n]=[βn]

取β=α+1

解方程

得

用有序数对（即两堆含石子的个数，规定第一个数不大于第二个数）表示某个状态，显然(0,0)是一个必败态。下面证明，根据下面的方法，可以构造出所有的必败态：

1° (0,0)是必败态

2° 第k个必败态的两个数相差为k（记(0,0)为第0个必败态）

3° 已知前k个必败态，则最小的没出现过的正整数为第k+1个必败态的第一个数

证明：

根据上述构造方法，有一个显然的事实：*每个状态的第一个数比它后面一个状态的第一个数小，对第二个数也如此[1]*。假如说后面状态的第一个数（记为A）比前面的小，那么前面状态的第一个数早就选A了，肯定轮不到后面的状态，与 3°矛盾。而前面状态中第二个数减第一个数的值比后面的小（由 2°），所以前面状态中第二个数当然比后面的小

同时，也可知*不会出现重复的正整数[2]*，因为如果出现重复的正整数，一定是前面状态的第二个数等于后面状态的第一个数（否则，由[1]，将会出现严格不等关系）。而后面状态的第一个数不可能与前面重复，与 3°矛盾

现在，考虑构造出的第n个状态，当n=0时显然是必败态，设n=0,1,2,…,k-1时，这k个状态已经是必败态，下面证明第k个状态也是必败态

记此状态为(A,A+k)。先取者不可能变为前面的必败态，因为如果只动一堆石子而变为前面某个必败态，则两个必败态有重复的正整数，矛盾；如果动两堆石子，则差不变，同样不可能变为前面某个必败态

下面通过证明，先取者不管如何取石子，后取者都能变成前面某个必败态，从而证明(A,A+k)也是必败态

（1）先取者若动第一堆石子，则这个数肯定在前面的必败态中出现过（由 3°），而此时第二堆石子的数目肯定比前面那个必败态的两个数都要大（由 [1]），所以后取者一定可以取第二堆石子，变为前面那个必败态

（2）先取者若动第二堆石子:

​ i .如果取完之后第二堆仍然不小于第一堆，则两堆石子的差减小，恰好和前面某个必败态吻合，而第一堆石子的数目肯定比前面那个必败态的第一个数大（由 [1]），后取者可以同时取两堆石子变为前面那个必败态

​ ii.若小于第一堆，则这个数在前面的必败态中出现过（由 3°），如果这个数是前面必败态的第二个数，则后取者只要动第一堆即可；如果很不巧，这个数是前面必败态的第一个数，而此时第一堆石子的数目又不大于前面必败态的第二个数，那此时两堆石子的差一定比前面那个必败态小，与更靠前的一个必败态吻合。后取者同时动两堆即可

（3）先取者若同时动两堆石子，则第一堆石子数在前面的必败态中出现过（由 3°），后取者动第二堆就行了

证毕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const double r = (sqrt(5) + 1) / 2;

int main(void)
{
    int iNumOfFirst = 0, iNumOfSecond = 0;
	cout << "请输入第一堆苹果个数:";
	cin >> iNumOfFirst;
	cout << "请输入第二堆苹果个数:";
	cin >> iNumOfSecond;
	int tempMax = max(iNumOfFirst, iNumOfSecond);
	int tempMin = min(iNumOfFirst, iNumOfSecond);
	bool ans = ((int)(::r * ((double)(tempMax - tempMin))) == tempMin);
	if (ans)
		cout << "先手胜！" << endl;
	else
		cout << "后手胜！" << endl;
}

Nim Game

桌上有三堆苹果，两人轮流从中拿取苹果

每一轮，只能选择从期中某一堆拿取至少一个苹果

将桌上苹果全部拿完者获胜

示例

起始时，三堆苹果数量分别为$3$个,$5$个,$2$个$(3,5,2)$

第一轮,Mike从第一堆拿走$3$个苹果,桌上剩余苹果状态$(3,2,2)$

第二轮,Nancy从第一堆拿走$2$个苹果,桌上剩余苹果状态$(1,2,2)$

第三轮,Mike从第三堆拿走$2$个苹果,桌上剩余苹果状态$(1,2,0)$

第四轮,Nancy从第二堆拿走$1$个苹果,桌上剩余苹果状态$(1,1,0)$

第五轮,Mike从第一堆拿走$1$个苹果,桌上剩余苹果状态$(0,1,0)$

第六轮,Nancy从第二堆拿走$1$个苹果,桌上剩余苹果状态$(0,0,0)$

桌上没有苹果剩余,Nancy胜利!

分析

用$（a，b，c）$表示某种局势，显然$（0，0，0）$是第一种奇异局势，无论谁面对奇异局势，必败

第二种奇异局势是$（0，n，n）$，先手从一堆拿取任意数量苹果，后手只需从另一堆中拿取相同数量苹果，最后都将导致先手面对$（0，0，0）$

搞定这个问题需要把必败态的规律找出：$（a，b，c）$是必败态等价于$a$^$b$^$c=0($^$表示异或运算)$

证明

$1$任何$（a，b，c）=0$的局面出发的任意局面$（a，b，c’）$一定有$a$^$b$^$c’ \neq 0$，否则可以得到$c=c’$

$2$任何$（a，b，c）(a$^$b$^$c = 0)$的局面都可以走向$（a，b，c’）(a$^$b$^$c’ \neq 0)$的局面

以具体的例子$（4，9，13）$为例，容易验证此种局势为奇异局势

$$\begin{pmatrix}
4\\
9\\
13\\
\end{pmatrix}$$

可以拆分为

$$\begin{pmatrix}
0&4&0&0\\
8&0&0&1\\
8&4&0&1\\
\end{pmatrix}$$

其中有两个$8$，两个$4$，两个$1$，非零项成对出现，这就是尼姆和为零的本质

对手若拿掉$13$里的$8$或$1$，那我们便拿掉对应的$9$ 中的$8$或$1$

对手若拿掉$13$里的$4$，那我们便拿掉对应的$4$ 中的$8$

对手若拿掉$13$里的$3$，则将剩余的$10$分解后想办法满足非零项成对即可

推广

推广一：如果我们面对的是一个非奇异局势$（a，b，c）$，要如何变为奇异局势呢？

假设 $a < b< c$,我们只要将 $c $变为 $a$^$b$,即可,因为有如下的运算结果: $a$^$b$^$(a$^$b)=(a$^$a)$^$(b$^$b)=0$^$0=0$。要将$c$ 变为$a$^$b$，只从$ c$中减去 $(c-(a$^$b))$

推广二：当石子堆数为$n$堆时，则推广为当对每堆的数目进行异或之后值为零是必败态2

Fibonacci Game

桌上有$n$个苹果，游戏双方轮流取苹果

1.先手不能第一次把所有苹果取完

2.之后每一轮，你所能拿的苹果个数至少$1$个,至多上一轮的两倍

轮到谁将桌上苹果全部拿完,谁获得本轮游戏胜利!

示例

起始时，桌上有$10$个苹果

第一轮,Mike拿走$1$个苹果,桌上还剩下$9$个苹果

第二轮,Nancy拿走$2$个苹果,桌上还剩$7$个苹果

第三轮,Mike拿走$3$个苹果,桌上还剩$4$个苹果

第四轮,Nancy拿走剩下全部$4$个苹果,桌上还剩$0$个苹果

Nancy胜利!

分析

这个博弈叫做Fibonacci博弈，肯定和Fibonacci数列$1,2,3,5,8,13,21,34,55,89,… $有密切的关系

如果试验一番之后，可以猜测：先手胜当且仅当$n$不是Fibonacci数，换句话说，当$n$为Fibonacci数时，先手必败

证明

假设$n$为斐波那契数，记其为$F[i]$

1.当$i=2$时，先手只能取$1$个苹果，显然必败

2.假设当$i\leq k$时，结论成立

则当$i=k+1$时，$F[i]=F[k+1]=F[k]+F[k-1]$，可以把总苹果看为两堆，分别称其为$k$堆和$k-1$堆

(一定可以看成两堆，设先手第一次取的苹果数为$x$，若$x\geq F[k-1]$，则后手可以直接取完$F[k]$，因为$F[k] = F[k-1] + F[k-2] < 2 * F[k-1]$)

而对于$k-1$堆，由假设知，先手必败，后手总能取到最后一个苹果

下面分析如何取$k-1$堆

如果先手第一次取苹果数为$y$，$y \geq \frac{F[k-1]}{3}$，则该堆所剩苹果数小于$2y$，即后手可以直接取完

此时$x=F[k-1]-y$，则$x \leq \frac{2F[k-1]}{3}$

比较$\frac{2F[k-1]}{3}与\frac{F[k]}{2}$的大小

$\frac{F[k]}{2}-\frac{2F[k-1]}{3}=\frac{F[k-1]}{2}+\frac{F[k -2]}{2}-\frac{2F[k-1]}{3}$

$=\frac{F[k -2]}{2}-\frac{F[k-1]}{6}=\frac{F[k -2]}{2}-\frac{F[k-2]}{6}-\frac{F[k-3]}{6}$

$=\frac{F[k -2]}{3}-\frac{F[k-3]}{6}=\frac{F[k -3]}{6}+\frac{F[k -4]}{3}>0$

即$x<\frac{F[k]}{2}$，所以后手取完$k-1$堆后，先手不能一下取完$k$堆，结局没有改变

桌上现剩余苹果数量为$F[k]=F[k-1]+F[k-2]$，又可将其分为两堆，后手可继续上述策略，必胜

那么，当n不是Fibonacci数的时候，情况又是怎样的呢？

由数学-齐肯多夫定理结论：任何正整数$n$可以表示为若干个不连续的Fibonacci数之和

即$n=F[x_1]+F[x_2]+F[x_3]+…+F[x_t]$且$x_1>x_2>x_3>…>x_t$是不连续的正整数

以85为例，将其分解得$85=55+21+8+1$

令先手取完$F[x_t]$，即最小斐波那契堆，由于各$x$不连续，则有$x_{t-1}>x_t + 1$，得$F[x_{t-1}]>2*F[x_t] $

后手只能取$F[x_{t-1}]$这堆，且不能一次取完

此时后手面临这个子游戏：只有$F[x_{t-1}]$这堆苹果，且后手先取，后手必败

同理知对以后的每一堆苹果，后手总是必败

综上，当n不是斐波那契数时，后手必败

1
2
3
输入桌上苹果数n
	if (n是斐波那契数) 后手胜
	else 先手胜