博弈论: 公平组合游戏

公平组合游戏

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

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

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

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

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

  • 结论：在巴什博弈中，这个特征是(m+1)|n
  • 一个结点n = k的所有前置状态为n ∈ [k+1,k+m]、所有后置状态为n ∈ [k−m,k−1] 很明显，只有一个出度为零的状态，即n = 0时，先手必输 因此n = 0的所有前置状态n ∈ [1,m]均为必胜状态 ⇒ n = m + 1是必输状态、所有n ∈ [m+2,2m+1]是必胜的(因为后续状态包含n = m + 1) 递推得到，所有n = k(m+1), k ∈ 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}$，则先手必输；否则先手必胜(其中⊕表异或) 证明这个定理，需要证明当异或和为0时，不存在任何操作使其异或和仍未0；且当异或和不为0时，总是存在操作使其异或和变为0

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

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

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

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

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

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