三个经典博弈

三个经典博弈

有三个经典的博弈论问题，分别是巴什博弈（Bash Game）、威佐夫博弈（Wythoff Game）和尼姆博弈（Nimm Game），从这三个问题入手，可以对博弈论有一个初步的了解。

巴什博弈

\(n\) 个物品，A 和 B 轮流取，至少取 \(1\) 个，至多取 \(m\) 个，不能取者失败。

可以发现，无论一个人取多少个，另一个人再取总能让两次取的个数之和恰为 \(m+1\) 。

设 \(n=r\times(m+1)+s\) ，有两种情况：

1. \(s=0\) ，假设先手取 \(k\) 个，后手取 \(m+1-k\) 个，总能保持剩下的物品数为 \(m+1\) 的倍数，此时后手必胜。
2. \(s>0\) ，先手先取 \(s\) 个，接下来的情况和 1 一样，此时先手必胜。

因此，\(s>0\) 时先手必胜，\(s=0\) 时后手必胜。

拓展一下，把 “至少取 \(1\) 个” 改成 “至少取 \(t\) 个”，事情会变得如何呢？

实际上，只需将上述解答过程中的 \(1\) 改成 \(t\) ，并把先手必胜状态改为 \(s\ge t\) ，相应的把后手必胜状态改为 \(0\le s\lt t\) 即可。

让我们回到原始的巴什博弈，设当前游戏的状态是 \(S\) ，这里的状态是一个宽泛的概念，对于不同的游戏是不一样的，对于巴什博弈，\(S\) 即剩下的物品数 \(n\) 。再设计一个函数 \(f(S)\) ，用来计算一个游戏状态的值 ，对于巴什博弈，可以是 \(f(n)=n \bmod (m+1)\) 。

1. 当游戏结束时，\(n=0\) ，此时 \(f(n)\) 的值是 \(0\) 。
2. 对于先手必败状态，都有 \(f(n)=0\) 。
3. 对于先手必胜的状态，都有 \(f(n)>0\) 。
4. 对于所有 \(f(n)=0\) 的状态，无论如何操作，后续状态的值都大于 \(0\) 。
5. 对于所有 \(f(n) > 0\) 的状态，总有办法让后续状态的值为 \(0\) 。

以上，其实就是组合游戏定义对于巴什博弈的具体化描述了，也非常接近于后面要说的 \(\text{SG}\) 函数。

威佐夫博弈

两堆物品，分别有 \(n\) 和 \(m\) 个物品，A 和 B 轮流取，每次可以选择从一堆或者同时从两堆中取至少一个物品（若取两堆，取的个数需相同），不能取者失败。

用 \((x,y)\) 表示两堆剩下的物品数（即当前游戏的状态 \(S\) ），并且不失一般性的让 \(x\le y\) 。显然 \((0,0)\) 是一个先手必败状态，接下来为了简化我们称之为必败态。根据组合游戏的定义来继续推导，可以发现 \((1,2)\) \((3,5)\) \((4,7)\) \((6,10)\) \((8,13)\) 等等也是必败态。

这里面似乎有什么规律？两个数之间的差好像每次加 \(1\) ？所有的数都最多出现一次？如果继续暴力往后计算必败态还可以发现，每个正数都恰好出现了一次（没错，找规律也是博弈论中很重要的一部分）。

让我们将所有必败态按 \(x​\) 的从小到大排成一排，设 \((a_i,b_i)​\) 为第 \(i​\) 个必败态，其中 \((0,0)​\) 为第 0 个，那么有 \(b_i=a_i+i​\) ，而 \(a_i​\) 是前面所有必败态中第一个没有出现过的正整数。接下来证明这样的状态都确实是必败态，而其他的所有状态都是必胜态（即先手必胜状态）：

1. 当前是必败态。

   • 若只从一堆中取物，由于每个数只在所有必败态中出现一次，显然不能从一个必败态转移到另一个必败态。
   • 若同时从两堆中取，由于每个必败态两个数的差都是不同的，同时取无法改变差值，也无法转移。

因此，从必败态只能转移到必胜态。

2. 当前是必胜态，设当前状态是 \((x,y)\) ，\(x\) 必然是某个必败态 \((a_i,b_i)\) 中的一个值：

   • \(x=a_i\) ，那么若 \(y>b_i\) ，从第二堆中取 \(y-b_i\) 个即可，若 \(y<b_i\) ，从两堆中同时取 \(x-a_{y-x}\) ，状态变为 \((a_{y-x},a_{y-x}+y-x)\) ，显然为必败态。（注意，此时 \(y-x\lt i\) ，所以 \(a_{y-x}\) 必然是小于 \(a_i\) 的）
   • \(x=b_i\) ，显然 \(y\gt a_i\) ，从第二堆中取 \(y-a_i\) 个即可 。

因此，从必胜态可以转移到必败态。

必败态和黄金分割率有着紧密的联系，设黄金分割率为 \(\phi=\frac{1+\sqrt{5}}{2}\) ，那么有 \(a_i=\lfloor i\phi \rfloor\) ，\(b_i=\lfloor i\phi ^2\rfloor\) ，多么美妙！而黄金分割率和斐波那契又有着关联，所以必败态和斐波那契也应有着某种联系（这一点还是原队友在赛场上发现的，因为我当时忘记这个公式了，我们找了一个小时的规律）。

观察斐波那契数列从第一项开始的数：

\[1, 2, 3, 5, 8, 13, 21, 34, \dots\]

可以发现，相邻两个数放一起，\((1,2),(3,5),(8,13),(21,34)\) 都是必败态！再观察 \((8,13)\) 和 \((21,34)\) 之间的必败态 ：

\[(9,15),(11,18),(12,20),(14,23),\dots ,(19,31)\]

他们的 \(x\) 减去 \(8\) ，\(y\) 减去 \(13\) 后：

\[(1,2),(3,5),(4,7),(6,10),\dots ,(11,18)\]

也都是新的必败态！

那么我们可以得到一个不需要用到实数计算的检验一个状态 \((x,y)\) 是不是必败态的方法（这也是当时我们赛场上的做法）：

1. 二分出最大的奇数项斐波那契数 \(fib_{2k+1}(k\ge 0)\) 使得 \(fib_{2k+1}\le x\) ，令 \(x'=x-fib_{2k+1}\) ，\(y'=y-fib_{2k+2}\)
2. 若 \(x'\neq 0\) ，令 \(x=x'\) ，\(y=y'\) ，重新执行步骤 1
3. 若 \(x'=0\) ，检查是否 \(y'=0\) ，如果是，那么初始的 \((x,y)\) 为必败态，否则为必败态

尼姆博弈

\(n\) 堆物品，其中第 \(i\) 堆的物品数为 \(a_i\) ，A 和 B 轮流取，每次任选一堆取至少一个物品，不能取者失败。

回顾巴什博弈，我们定义了一个计算当前游戏状态 \(S\) 的值的函数 \(f(S)\) ，而现在可以正式介绍 \(\text{SG}\) 函数了。

\(\text{SG}\) 函数是 \(\text{Sprague-Grundy}\) 函数的简称，类似的，一个 \(\text{SG}\) 函数 \(sg(S)\) 也是用来计算当前游戏状态 \(S\) 的值，但相比于 \(f(S)\) ，它直接规定了计算方法：\(sg(S)=\text{mex}\{sg(S')|S \rightarrow S'\}\) ，其中 \(S\rightarrow S'\) 表示状态 \(S\) 能到达 \(S'\) ，\(\text{mex}\) 是 minimum excludant 的简称，即第一个未出现的非负整数。显然，对于结束状态，它不能到达任何其他状态，因此其 \(sg\) 值必然为 \(0\) ，进一步思考可以发现必胜状态的 \(sg\) 值必然大于 \(0\) ，必败状态的 \(sg\) 值必然等于 \(0\) 。总而言之，一个状态能到达任何 \(sg\) 值小于它的状态，不能到达任何 \(sg\) 值等于它的状态。

回到尼姆博弈，我们将状态 \(S\) 定义为 \(\{a_1,a_2,\dots,a_n\}\) ，当 \(n=1\) 时，可以发现 \(sg(\{a_1\})=a_1\) ，但当 \(n>1\) 时呢？显然我们可以通过定义来暴力计算，但这样效率很低，有没有更加高效便捷的办法？答案是 \(\text{SG}\) 定理。

形式化的，定义 \(n\) 个游戏 \(G_1,G_2,\dots ,G_n\) 的和 \(G(V,E)=G_1+G_2+\dots +G_n\) 为：

1. \(V=V_1\times V_2\times \dots \times V_n\) ，这里的 \(\times\) 代表的是笛卡尔积。
2. \(E=\{(x,y)|x=(x_1,x_2,\dots,x_n),y=(y_1,y_2,\dots,y_n),(x_k,y_k)\in E_k,1\le k\le n,y_i=x_i,\forall i\neq k\}\) 。

解释一下，\(V\) 点集代表游戏的状态集合，\(E\) 有向边集代表游戏的状态转移， 对于游戏的和 \(G\) 的转移，即选择一个子游戏 \(k\) 进行状态转移，而其他子游戏状态保持不变。

游戏和的 \(\text{SG}​\) 函数等于各个游戏 \(\text{SG}​\) 函数的 \(\text{nim}​\) 和，而 \(\text{nim}​\) 和，即异或和。证明如下：

不失一般性的，考虑两个游戏的和的 \(\text{SG}\) 函数 \(sg(S)\) ，\(S\) 由两个游戏的状态 \(S_a\) 和 \(S_b\) 组成，并且分别设两个游戏的 \(\text{SG}\) 函数为 \(sg_a(S_a)\) 和 \(sg_b(S_b)\) ，那么要证明 \(sg(S)=sg_a(S_a)\oplus sg_b(S_b)\) 是对的（这里 \(\oplus\) 即代表 \(\text{nim}\) 和），只需证明那句“一个状态能到达任何 \(sg\) 值小于它的状态，不能到达任何 \(sg\) 值等于它的状态”，即满足了 \(\text{SG}\) 的定义。

1. 不能到达任何 \(sg\) 值等于它的状态 ，由于每次操作只可能改变一个游戏的状态，根据异或操作的性质，无论如何都不可能让后续状态的 \(sg\) 值保持不变 。即 \(\forall S' \in \{S'|S\rightarrow S'\}\) ，都有 \(sg(S')\neq sg(S)\) 。
2. 能到达任何 \(sg\) 值小于它的状态 ，假设 \(sg_a(S_a)=a\) ，\(sg_b(S_b)=b\) ，令 \(c=a\oplus b\) ，\(\forall v\lt c\) ，令 \(t=v\oplus c\) ，设 \(t\) 在二进制下最高位为第 \(k\) 位，那么 \(a\) 和 \(b\) 中必然存在一个数第 \(k\) 位为 \(1\) ，假设这个数是 \(a\) ，令 \(a'=t\oplus a\) ，那么有 \(a'\oplus b=t\oplus a\oplus b=v\oplus c\oplus c=v\) ，而显然 \(a'\) 一定是小于 \(a\) 的，根据定义，\(\exists S_a'\in\{S_a'|S_a\rightarrow S_a'\}\) 满足 \(sg_a(S_a')=a'\) 。所以 $S'{S'|SS'} $ 满足 \(sg(S')=v\) 。

当游戏是多个游戏的和时也是一样，不再赘述。

再次回到尼姆博弈，它其实相当于是 \(n\) 个一堆的游戏的和，那么显然有：

\[sg(S)=sg(\{a_1\})\oplus sg(\{a_2\})\oplus \dots \oplus sg(\{a_n\})=a_1\oplus a_2\oplus \dots \oplus a_n\]

当 \(sg(S)>0\) 时先手必胜，当 \(sg(S)=0\) 时先手必败。

参考资料

• 威佐夫游戏
• 斐波那契数列