博弈论: 公平组合游戏

公平组合游戏

• 一个博弈游戏是公平组合游戏意味着，场上所有物品对于所有玩家都是可操作的，且玩家们必须遵循同样的操作规则；即对于操作(无论是操作规则还是操作对象)来说是公平的 但玩家总会有操作的顺序，事实上许多游戏先手和后手的胜利期望是不同的，博弈论研究的就是，当场上所有玩家都作出最“合理”的操作时，某个玩家必胜/必输的情况；不难得到，一个玩家在一局游戏里，要么必胜、要么必输 这里的合理，意味着玩家总是枚举完所有的结局，再选出最有利的那个选择；这里有一个很直观的结论就是，如果后续所有结局都是输，那么此时一定是必输的；否则，此时一定是必胜的 那么有没有办法，不需要枚举所有的结局，而只需要知道后续状态的必胜、必输，就可以递推出当前的必胜/必输呢？当然是可以的

• 实际上，对于双人的游戏而言，先手必胜意味着后手必输，因此我们只讨论先手必胜/先手必输的情况 一个约定：先手必胜/先手必输此后简称必胜/必输；能使先手必胜/必输的操作对象的初始状态(例如数量为$n$)此后简称必胜/必输状态 对操作规则不会因操作对象状态改变的游戏而言，必胜、必输只和操作对象的状态有关，那么一个脑筋急转弯的思考就是：

  • 一个状态是必胜状态，当且仅当存在一个后续状态是必输状态(这里的后续指的是只通过一次操作转移到的状态) 充分性：如果存在一个后续的必输状态，那么此时先手可以选择转移到这个状态，此时后手变成了“先手”，于是必输 必要性显然
  • 一个状态是必输状态，当且仅当没有后续状态、或所有后续状态是必胜状态 这个命题的一部分是上述命题的逆否命题；特别地，如果没有后续状态，说明此时的先手已经无法再操作了，意味着先手必输

• 对于博弈问题，可以将上述状态视作结点，并画成一个有向无环图，标记所有无出度的节点为必输结点，然后经过一次dfs即可得到所有结点的必胜/必输性质 而在一些简单的脑筋急转弯题目中更常见的做法是，对所有状态进行归纳，即找到一个特征$A$，使该特征满足$A$无论如何都无法变为$A$、而$\bar A$总存在一种操作使得$\bar A$变为$A$

• 巴什博弈：有$n$个物品，两个人轮流取物，每次只能取$[1,m]$个物品，最后取光者胜利

  • 结论：在巴什博弈中，这个特征是$(m+1)|n$
  • 一个结点$n=k$的所有前置状态为$n\in[k+1,k+m]$、所有后置状态为$n\in[k-m,k-1]$ 很明显，只有一个出度为零的状态，即$n=0$时，先手必输 因此$n=0$的所有前置状态$n\in[1,m]$均为必胜状态$\Rightarrow n=m+1$是必输状态、所有$n\in[m+2,2m+1]$是必胜的(因为后续状态包含$n=m+1$) 递推得到，所有$n=k(m+1),k\in N$均为必输状态，其余为必胜状态
  • 如果先手必胜，那么先手的操作就应是：使操作后$n=k(m+1)$，即取$n\%(m+1)$个

• Nim游戏：共$n$堆物品，每堆有$a_i$个，两个玩家轮流取任意一堆的任意数量个物品，最后取光者胜利

  • 在Nim游戏中，这个特征是各堆数量的异或和(也称Nim和)为零，Nim和定理：若

    $$\begin{align}\bigoplus_{1\le i\le n}a_i=0\end{align}$$

    ，则先手必输；否则先手必胜(其中$\oplus$表异或) 证明这个定理，需要证明当异或和为$0$时，不存在任何操作使其异或和仍未$0$；且当异或和不为$0$时，总是存在操作使其异或和变为$0$

    • 对于第一个命题：假设玩家将$a_i$改为$a_i'$，那么由异或操作可以得出$a_i=a_i'$，即不取，明显不符合规则，因此不存在这样的操作
    • 对于第二个命题：假设当前异或和为$k$，那么异或上$k$即为$0$，我们取合适的$a_i$，使其变为$a_i\oplus k$即可 假设$k$的最高的为$1$的位是第$j$位，那么至少存在一个$a_i$，它的第$j$位也为$1$，选取这个$a_i$，可以得到$a_i\oplus k<2^j\le a_i$，因此这个操作是合法的

    先手必胜的操作就是，不断地使操作后的Nim和为$0$，此时后手的任何操作只会让Nim和再变为非$0$，直到最后一次使Nim和为$0$，此时所有堆的数量均为$0$，先手玩家得到胜利 也就是检查所有$a_i$(或检查所有满足第$\_\_lg(k)$位为$1$的)，找到任意一个异或$k$后不超过$a_i$的，取$a_i-(a_i\oplus k)$即可

• Roy&October之取石子 Roy&October之取石子II

  • 可以发现，$0$是必输的，而$n\in[1,5]$是必胜的，然后$n=6$是必输的 然后我们假设特征是$6|n$，即$n=6k$
  • 它是否无论如何都无法使下一个状态为$6|n$：这需要证明任意质数的幂$p^k$不是$6$的倍数 除了$2$以外的质数，它们的幂都是奇数，因此不可能是$6$的倍数 $2$的幂不含$3$的因子，因此也不可能是$6$的倍数，得证
  • 它的补，即$6\nmid n$是否总存在一种取法使得下一个状态为$6|n$：因为$6\nmid n$，我们取$n\%6$即可
  • 因此答案是：若$6|n$，则先手必输；否则先手必胜
  • 后题与前题类似，只不过特征变成了$4|n$

• 欧几里德的游戏：有些时候，答案不能简单地归纳，而必须通过递归得到

  • 取$m$为两数中较小者，$n$为较大者，并改写为$n=km+r$，$r$为$n\ {\rm mod}\ k$ 可以得到退出递归的情况：$r==0$或$k\ge 2$，此时操作者必胜 前者显然，而后者总是可以一步(直接减去$km$)或两步(先减去$(k-1)m$，此时数对为$(m,m+r)$，后手只能减去$m$)使数对变为$(m,r)$；由于$(m,r)$一定是必胜或必败的，它必胜就两步变换、必败就一步变换，就能保证数对为$(m,n)$时的操作者必胜了
  • 否则，只能进行递归：$f(m,n,player)==f(r,m,\neg\ {player})$