博弈论

· · 算法·理论

博弈论公平组合游戏从入门到入土。

sbno333 手把手教你 sg 函数。

前言

不是所有游戏都要用到博弈论知识，很多游戏递推解决即可，但有些游戏需要用到，具体按情况而论，一般的，看着像 Nim 游戏的都是递推（诈骗），看着和 Nim 半毛钱没有的是博弈论。

前置知识

异或，\text{mex}，可以上 OI 维基自主学习。

一般公平组合游戏

两个人轮流操作，没有平局，每个人每次能进行的操作与人无关，并且能结束。比如国际象棋就不是这类游戏，因为它有平局，而且你只能动自己的棋子，不能动对方的，无法操作的一方输。

sg 函数

在这之前，我们应当学习 Nim 游戏，这个游戏在博弈论学习中起到极其重要的地位。

Nim 游戏

如题，有 n 堆石子，每堆石子有若干个石子，不能不取，每次可以选取一堆石子，取走若干石头。

下文中用 \oplus 代替按位异或。

这道题有一个必胜策略就是当石子堆石子数量异或和为 0 时，先手必败，否则必胜。

具体的，当异或和为 0 时，显然我们操作后肯定改变了某个石堆，设其它石堆异或和为 x，这个石堆原本也一定为 x，改变后为 y<x，对于两个不同的数，其异或和一定不为 0，因此取完后为异或和不为 0。

对于不为 0，设这个值为 x，其最高位为 1，显然存在一个石堆，其和异或和的最高位对应也是 1，设其有 y 个石子，此时其他石子堆异或和为 x\oplus y，由于 x,y 在 x 最高位都是 1，因此 x\oplus y 那一位为 0。

我们此时只需要将 y 变得使 x=0，即 x\oplus y=y，显然 x\oplus y 不会随操作 y 而改变（操作当前不会改变其他石子），可以这么操作当且仅当原来的 y 比 x\oplus y 大，这样才能将 y 取到 x\oplus y。

问题变成了 y 异或上一个没有 y 位数多，且那个数最高位 y 对应位也是 1 的数（上述提到的 x 具有的性质）与其异或后能否比 y 小。

对于比 x 最高位高的位，显然异或后不改变，不考虑。

对于 x 最高位，异或后 y 对应位减少（从 1 到 0)，其他位怎么增加也比不上，所以正确，即可以将异或和从 \not=0 变为 0。

一个人输的时候显然石子堆异或和为 0，所以 \not=0 时不为输的状态。

所以如果先手时异或和 \not=0，总是可以给到对方 =0，而对方又只能返回 \not=0，这样下先手必胜。

如果先手为 0，则只能把 \not=0 给到对方，对方再采用上述策略，先手必败。

所以结论就是判断异或和是否为 0。

从 Nim 升级开始代入 sg 定理

我们不妨升级 Nim 游戏，每次不但可以取走，还可以放入，但不能不操作，为了游戏的有限，每次放入后如果满足某个条件，之后双方将无法放入，而且每次放入对放入的数量有限制。

对于异或和 \not=0，显然可以看作只能减少，然后显然可以把异或和变为 0。

对于 =0，显然还是要改变，因此还是会重新变为 \not=0 给对方。

因此这个游戏与上述普通 Nim 游戏必胜策略一致，与放入的条件之类无关，但当减少有限制时，游戏结果或受到影响。

sg 函数及定理

对于公平组合游戏，可以分成若干互不影响的子游戏，每次选取一个子游戏进行操作，比如 Nim 取石子可以分成 n 个子游戏，每个子游戏都是一堆石子，显然取走这堆石子不会影响其他石子堆。

我们可以将每个子游戏抽象成有向无环图，一个节点表示当前子游戏状态，比如 Nim 游戏中可以表示当前石子堆石子数量。而每个节点的每个后继边表示一个可以选择的操作，比如在 Nim 游戏的子游戏中，有 3 个石子的节点的后继为 0,1,2 三个石子可能数量的节点，但 3 不是，因为操作后不能变会自己，所以自己不是自己的后继。

我们对于任意公平组合游戏，都可以绘图，我们设一个子游戏的结束节点的 sg 值为 0，比如在 Nim 中某一堆取完的状态其 sg 值为 0。

于是有个有趣的想法：对于每个状态的 sg 值，我们可以将其抽象成 Nim 中的石子数量，我们考虑如何通过后继来转移。

为了保证不能不取，显然 sg 值不能与后继中任何一个相等我们假设当前 sg 值为 x，则可以操作后让 x 增加或减少，上述 Nim 中说与增大无关，为了可以仿照 Nim 游戏的策略，根据上述 Nim 升级版的黑体字，其下降不能受到影响，而 Nim 游戏中下降不受到影响定义为可以在自己操作时在堆数不是 0 时随时下降并且能下降到任意小于原值的自然数。

这个 sg 值非 0 时下降显然是自然的，不需要维护，如果后继不得不上升，记当前 sg 为 0 即可。对于可以下降到任意小于当前值的自然数这个条件，我们倒推，即后继出现过比当前小的所有自然数，考虑到没出现过，所以 sg 值为后继 sg 中未出现过的最小自然数（因为不是最小就不满足可以去任意比自己小的自然数，可以去最小），我们对这个很熟悉啊，就是 \text{mex}！而且前面的情况也可以证明符合这一条。

假设分成了 n 个子游戏，根据 Nim 游戏，所以就是判断每个子游戏起点的 sg 值异或和是否为 0 即可。

我们梳理一下，游戏分成若干子游戏，每个子游戏为一个有向无环图，终点 sg 值为 0，每个节点为其后继的 \text{mex}，如果所有子游戏的起点 sg 值异或和为 0，先手必败，否则必胜。

这里给出一个性质：有 mex 得出某个状态的 sg 值一定在 O(\sqrt m) 以内，其中 m 为状态所在子游戏构成的图的边数。

一些套路

翻格子游戏的性质

我们设每次选择一个白色的格子 i，选择一个满足条件的 k，翻转 S_{i,k} 集合内的格子，保证当前格子一定被翻转，且游戏能结束。

我们可以将游戏转化为每个格子有一个数，原游戏中白色初始是 1，黑色初始为 0。

每次可以选择一个非 0 的数进行操作，当前数的值减一 ，S_{i,k} 的其他数加一。

游戏中，显然白色对应奇数，黑格对应偶数，我们只需要证明这个游戏与原游戏等价（必胜判定相同）。

设原游戏先手为必胜方，显然可以按照原游戏策略进行，只翻转奇数，监督必败方是否也只反转奇数，如果翻转偶数，将其变为奇数，则先手再次对那个格子进行翻转，可以证明奇偶性可以与后手操作前一样，使得后手在奇偶性上操作无效，重新变回自己，而先手由于前提是必生，所以总有奇数可以翻，0 是偶数，于是可以证明新游戏也是必胜方。

如果原先后手必胜，仿照上述，易证。

所以等价。

结论就是可以分成 w 个子游戏，第 i 个子游戏只有第 i 原来的白格是 1 其他都是 0。

而我们每次都是在一个子游戏上进行的，你可以能认为这仍然会互相影响，但其实不是，这个序列在现实中表现为每个子问题的序列对应位置的和，如果这个位置是 0，则子游戏都为 0，不能操作。否则一定能看作一个子游戏进行的一次操作，因此可以分解。

这道题目求 sg 的具体方法

于是这样我们就将其分解成了若干子游戏，并且始终存在分解方案，这时候我们不妨设 sg(x) 表示只有 x 为白格，我们考虑列式子。

我们选择 k=1，此时得到游戏结束状态，sg 为 0。

选择 k=2，此时转化为只有 2x 为白色，为 sg(2x)。

选择 k=3，此时转化为 2x,3x 为白色，不妨再次按照刚刚的结论分解，分解为只有 2x 和只有 3x 为白色两个子游戏，按照 sg 定理，答案为起点 sg 的异或和，所以此时为 sg(2x)\oplus sg(3x)。

以此类推。

于是我们得到了 sg(x)=\text{mex}(0,\text{mex}_{i=2}^{\frac n x}\oplus_{j=2}^i sg(j))，即 sg(x)=\text{mex}(0,sg(2x),sg(2x)\oplus sg(3x),sg(2x)\oplus sg(3x)\oplus sg(4x)\dots)。

我们可以从 n 枚举到 1，暴力求出 sg(i)，可以做到 O(w) 处理询问，但预处理时间复杂度高达 O(n^2)，不能接受。

于是考虑优化。

有一些 sg(i) 可能是相同的，我们考虑这段优化。

题目。

拓展