博弈论

公平组合游戏

• 满足下面三个条件的游戏被认为是公平组合游戏：

  • 1.两个玩家，轮流决策，完全信息。

  • 2.双方的可行操作仅依赖于局面，与是谁无关。

  • 3.同一局面无法多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步数内以非平局结束。

• 任意的博弈游戏具有如下性质：

  • 我们定义先手必败的状态为必败状态，先手必胜的状态为必胜状态。

  • 1.没有后继状态的状态是必败状态。

  • 2.有至少一个后继状态是必败状态的状态是必胜状态。

  • 3.所有后继状态都是必胜状态的的状态是必败状态。

• 在公平组合游戏中：

  • 推论：我们一定可以用 \(O(n+m)\)，即在反图（因为每个点依赖于儿子）上 toposort 的时间来计算出博弈树上每一个点是必胜还是必败（因为同一局面无法多次抵达所以是有向无环图）。

  • 推论推广：对于一个有向有环博弈图，我们也可以使用修改的拓扑排序（下面的所有入队不相容，只能入一次）。

    • 如果任意一个点被确定必胜，入队。

    • 如果一个点已经没有入度，那么它必败，入队。

    • 如果一个点没有入过队，那么这个点处在一个真环上，必平。

MAX-MIN搜索

• 运用类 dp/记搜的方式，博弈双方一方试图使优势最大，另一方试图使对方优势最小。

• 当局面有价值时，通常直接用局面价值作为 dp 内容。注意，这实质上也是逆向 dp，因为转移方程通常是 \(dp_{now}=max/min(dp_{to}\pm cost(now,to))\)，父节点的值由子节点决定。

• 当仅有胜负时，通常使用逆向 dp，即状态定义为离胜还需要多少步。

Alpha_Beta 剪枝：

• 我们给每个节点赋上两个值： \(alpha\) 和 \(beta\) ，分别代表从这个点到结局的价值的下界（最小）（至少能有这么优的决策，无法更劣）和上界（最大）（至多能有这么优的决策，无法更优）。

• 初始时， \(alpha=-inf,beta=inf\) 。

• 首先显然的是，最大层我们更新 \(alpha\)，\(beta\) 不更新；最小层我们更新 \(beta\)，\(alpha\) 不更新。

• \(alpha\) 剪枝：

  • 对于最大决策点，我们肯定是不断地这样操作： \(alpha=max(beta_{son}+value(now,son))\)。

  • 所以我们传给儿子的 \(alpha_{son}\) 应该为 \(alpha-value(now,son)\)。

  • 如此一来，如果儿子搜出来了一个 \(beta_{son}\leqslant alpha_{son}\)，就说明这个节点不能使我们获得更大的 \(alpha\)。所以这个儿子及其子树没有价值，赶紧剪枝。

  • 返回 \(alpha_{son}\) 还是 \(beta_{son}\) 其实是无所谓的，前者使得 \(max\) 的两者相等，后者使得 \(alpha>those\) ，保证 \(alpha\) 不变。

• \(beta\) 剪枝：

  • 操作应该是这样：\(beta=min(beta,alpha_{son}+v(now,son))\) 。

  • 从而下传的 \(beta_{son}\) 应该为 \(beta-v(now,son)\) 。

  • 如果儿子搜到了一个 \(alpha_{son}\geqslant beta_{son}\) ，就说明这个节点不能使我们获得更小的 \(beta\) 。

• 要特别注意，根据最大/最小层的不同，转移式中的 \(value(now,son)\) 的正负号可能会变，取决于所选择的搜索目标。

• 乍一看很强，但以普遍理性而论，大部分博弈论都是结论题。所以，搜索很可能过不了。

Nim 游戏

• 给定 \(n\) 堆数量分别为 \(a_i\) 个的石子。每次可以选择取一堆中的任意个(不能不取)，无法操作的人输。

• 首先这个肯定也是可以拓扑排序的，不过总状态数太大，达到了 \(\prod\limits_{i=1}^n a_i\)，放弃。

• 先给出结论：满足 \(a_1\oplus a_2\oplus\dots\oplus a_n=0\) 的状态为必败状态。

• 想要证明上面的结论，只需证明下面三个定理：

  • 1.无后继状态的状态（最终状态）满足上式。

    • \(a_i=0\) ，很显然，略。

  • 2.对于 \(a_1\oplus a_2\oplus\dots\oplus a_n\ne0\) 的状态，一定存在至少一种决策使得 \(a_1'\oplus a_2'\oplus\dots\oplus a_n'=0\)（有至少一个后继状态是必败状态的状态是必胜状态）。

    • 不妨令 \(a_1\oplus a_2\oplus\dots\oplus a_n=k\)。

    • 显然，\(\exists\ a_i\) 使得 \(a_i\) 在 \(k\) 的二进制下最高位为 \(1\)。

    • 所以把 \(a_i\) 这一位上取成 \(0\)，显然比这一位低的位上是 \(1\) 还是 \(0\) 是任意的。

    • 我们让他和 \(k\) 对位相消，如果 \(k\) 这一位是 \(0\) 就让 \(a_i\) 这一位不变，否则 \(a_i\) 这一位取反。

    • 从而有 \(a_1'\oplus a_2'\oplus\dots\oplus a_n'=0\)。

  • 3.对于 \(a_1\oplus a_2\oplus\dots\oplus a_n=0\) 的状态，一定不存在任意一种决策使得 \(a_1'\oplus a_2'\oplus\dots\oplus a_n'=0\)（所有后继状态都是必胜状态的状态是必败状态）。

    • 这个稍微显然一点。取了之后必然导致某一位上 \(1\) 的个数改变，所以异或值改变，不成立。

• 上述证明即为一般博弈论猜出结论后的证明方式。换句话说...暴力打表猜结论才是重点。

• 实际猜结论时常常利用对称性。即，模仿对方操作来保持某种性质。

SG 定理

• 定义 \(mex\) 函数的值为不属于集合 \(S\) 中的最小自然数，即 \(mex(S)=min(x)(x\notin S,x\in N)\)。

• 如果一个游戏可以被转化为有向图游戏（即，该游戏有有向无环博弈图），那么我们定义它的 SG 值为 \(SG(x)=mex\{SG(son)\},\exists\ e[x][son])\)。

• 特别地，\(SG(0)=0\)，即单个子游戏已经没有可行操作时的 SG 为 \(0\)。

• 从而对于一个由多个有向图游戏组成的 SG 游戏（可行操作集为空的玩家输），假设其当前各子游戏状态集为 \(s_i\)，我们有定理如下：

• 当且仅当 \(SG(x)=SG(s_1)\oplus SG(s_2)\oplus\dots\oplus SG(s_k)\ne 0\)，该状态先手必胜，否则先手必败。其中 \(SG(x)\) 即为这个组合游戏的状态的 SG 值。

• 可以用数学归纳法证，但很长，而且这个我真的没看太懂。

• 以上面的 nim 游戏为例。因为每一堆都可以取任意个，且 \(SG(0)=0\)，所以我们可以推出 \(SG(i)=i\)。从而上面那个结论里面异或的内容就是子局面 SG 。

阶梯 Nim(Staircase Nim)

• 从阶梯上往下移动石子。已经到地面的不能再动。每次可以移动任一层阶梯上的任意个，但不能不移动。无法操作者输。

• 更形式化也更一般化的描述： \(n\) 堆石子，每次可以从第 \(i+1\) 堆中取出任意个放到第 \(i\) 堆，也可以把第 \(1\) 堆的任意个拿走。

• 显然偶数层的石子不影响结果（模仿操作，第一个人移到奇数层，第二个人再移一下）。

• 进一步地，将一个石子从奇数层移到偶数层后，它不再影响胜负。

• 是不是感觉有点什么？换种说法，将一个石子从奇数层移到偶数层，相当于把它扔掉。

• 只考虑奇数层。本质仍然是 nim 游戏。SG 函数同上，其余略。

反 Nim(anti-Nim)

• 规则同 nim ，但最后无法操作的人赢（最后一个操作的人输）。

• 证明非常复杂，我（至少现在）不是很想写。姑且放一下结论：

• 必胜状态必然满足以下两个条件之一：

  • 若所有堆都仅有 \(1\) 个石子，则堆数为偶。

  • 否则，\(a_1\oplus a_2\oplus\dots\oplus a_n\ne0\)。

• 这个结论可以推广。

anti-SG 定理

• 单个游戏的 SG 函数定义不变，但：

• 对于一个由多个有向图游戏组成的 anti-SG 游戏(可行操作集为空的玩家赢)，假设其当前各子游戏状态集为 \(s_i\)，我们有定理如下：

• 当且仅当 \((SG(x)\ne 0\ and\ \exists\ SG(s_i)>1)\ or\ (SG(x)=0\ and\ \nexists\ SG(s_i)>1)\) 时，该状态先手必胜，否则先手必败。其中 \(SG(x)\) 即为这个组合游戏的状态的 SG 值，定义同前。

• 证明略。

• 另：当且仅当只有一个子游戏时， anti-SG 游戏可以通过将总石子数（操作数）减一的方式转化成一个 SG 游戏。有些时候这非常好用，因为 anti-SG 的定理真的很复杂。（e.g.\(\text{P6791 取石子}\)）

  • 证明：

    • 首先非常显然的是，除非我只给你留了一个石子，否则你一定不会输掉。

    • 所以相当于比拼谁能做拿完 \(n-1\) 个的人。

    • 当然从这里我们能看到这个结论是需要游戏的规则合适的。

斐波那契博弈(Fibonacci Nim)

• 有一堆石子，数量为 \(n(n>1)\) ，拿走最后一颗的玩家获胜。

• 第 \(1\) 手不能全部拿完，第 \(i+1\) 手至多拿第 \(i\) 手拿的数量的 \(2\) 倍。

• 先放结论：当且仅当 \(n\) 是 \(fibonacci\) 数，先手必败。

• 证明：(下面认为 \(fib_0=fib_1=1,fib_2=2\) ，但所有 \(i\) 最小从 \(1\) 开始)

  • 引理 \(1\)： \(fib_{i+1}<2fib_i<fib_{i+2}\ (i>1)\)

    • \(2fib_i=fib_i+fib_{i-1}+fib_{i-2}=fib_{i+1}+fib_{i-2},and\ fib_{i-2}<fib_i\ (i>1)\)

  • 引理 \(2\)： \(\frac{4}{3}fib_i<fib_{i+1}\)

    • 显然 \(i=1,2,3\) 时成立。

    • 如果该引理对 \(i=1,2,\dots,m-1\) 成立，则：

    • \(\frac{4}{3}fib_i=\frac{4}{3}fib_{i-1}+\frac{4}{3}fib_{i-2}<fib_i+fib_{i-1}=fib_{i+1}\)

  • 引理 \(3\): \(fib_i\geqslant \frac{1}{3}fib_{i+2}\)

    • 当 \(i=1\) ，显然成立。

    • 当 \(i\geqslant 2\) ，假设不成立，从而 \(fib_{i+2}>3fib_i=2fib_i+fib_{i-1}+fib_{i-2}=fib_{i+1}+fib_i+fib_{i-2}=fib_{i+2}+fib_{i-2}\) ，矛盾。

    • 所以引理 \(3\) 成立。

  • 引理 \(4\)：从小于 \(fib_i\) 的 \(fibonacci\) 数中选取 \(fib_{a_1},fib_{a_2},\dots,fib_{a_k},a_{i+1}>a_i+1\) ，则 \(\sum\limits_{i=1}^k fib_{a_i}<fib_i\) 。

    • 假设 \(\sum\limits_{i=1}^k fib_{a_i}\geqslant fib_i\) ，则我们有 \(\sum\limits_{i=1}^{k'=k-1} fib_{a_i}\geqslant fib_i-fib_{a_k}\geqslant fib_{a_k-1}\) (因为 \(i\geqslant a_k+1\) )，且显然 \(a_k-1>a_{k'}\) 。

    • 反复递降直到 \(k'=1\) ，此时 \(fib_{a_1}\geqslant fib_{a_2-1},a_2-1> a_1\) ，显然不成立。

    • 所以引理 \(4\) 成立。

  • 引理 \(5\)：（齐肯多夫定理）\(x=\sum\limits_{i=1}^k fib_{a_i},a_{i+1}>a_i+1\ (x\in N^* )\)，该拆分唯一存在。

    • 存在性：

      • 若 \(m\) 是 \(fibonacci\) 数，显然成立。

      • 考虑 \(m\) 不是 \(fibonacci\) 数的情况。

      • 如果该引理对 \(i=1,2,\dots,m-1\) 成立，则：

      • 取 \(k_1\) 使 \(fib_{k_1}<m<fib_{k_1+1}\)， 从而记 \(m=delta+fib_{k_1}\) 。

      • 显然我们有 \(delta=m-fib_{k_1}<fib_{k_1+1}-fib_{k_1}=fib_{k_1-1}<m-1\)。

      • 从而 \(delta\) 一定满足该定理。同时， \(delta<fib_{k_1-1}\)，所以 \(delta\) 的拆分的最后一个至多为 \(fib_{k_1-2}\)，而 \(m\) 独立于 \(delta\) 的拆分仅有一个 \(fib_{k_1}\)，两者显然不连续。

    • 唯一性：

      • 假设 \(m\) 是最小的有两种拆分的数， \(a,b\) 分别为其拆分中最大的 \(fibonacci\) 数。

      • 首先假设 \(a\ne b\)。不妨令 \(a<b\)，由引理 \(4\)，第一种拆分所得的和必然 \(<b\)，又 \(b<m\)，所以不成立，从而 \(a=b\) 。

      • 那么 \(m-a\) 必然有两种拆分才能使 \(m\) 的拆分不唯一，但这与 \(m\) 是最小的有两种拆分的数矛盾。所以假设不成立，该拆分一定唯一。

  • 好耶！我们终于可以回到斐波那契博弈了！(雾)

  • 定理 \(1\) ：当 \(n\) 是 \(fibonacci\) 数，先手必败,且后手最后赢的一手拿的数量 \(\leqslant \frac{2}{3}n\) 。

    • 显然我们可以得到 \(n=fib_2,fib_3\) 时成立，且后手最后赢的一手拿的数量 \(\leqslant \frac{2}{3}n\)。

    • 如果该定理对 \(n=fib_2,fib_3,\dots,fib_{k-1}\) 都成立，则取 \(n=fib_k\) 。

    • 首先我们把当前这局游戏分为两个阶段：拿前 \(fib_{k-2}\) 颗石子，和拿后 \(fib_{k-1}\) 颗石子。

    • 我们先来证明两个阶段一定可以相互独立(在后手方的努力下)：

    • 首先，先手方肯定不会拿 \(\geqslant fib_{k-2}\) 个石子。否则根据引理 \(1\)，此时后手方至多能拿 \(2fib_{k-2}>rest=fib_{k-1}\) 颗石子，可以一手拿完。

    • 从而先手方一定不会在第一手离开第一阶段。而第一阶段相当于一个 \(n'=fib_{k-2}<n\) 的子游戏，后手肯定能赢，即后手一定能拿到最后一颗，确保两个阶段相互独立。

    • 于是我们来到了可以作为一个子游戏的第二阶段。显然先手唯一的胜算就是一手全部拿完，但因为后手最后赢的一手拿的数量 \(\leqslant \frac{2}{3}fib_{k-2}\)，所以先手方现在最多拿的数量 \(\leqslant \frac{4}{3}fib_{k-2}\)，由引理 \(2\)，这一数量 \(<fib_{k-1}\) 。可怜的先手方无论如何都一手拿不完！

    • 又由引理 \(3\) ， \(fib_{k-2}\geqslant\frac{1}{3}fib_k\) ，即 \(fib_{k-1}\leqslant\frac{2}{3}fib_k\) 。因为第二阶段先手先拿，所以这一手之后 \(rest<\frac{2}{3}fib_k\) 。所以对于 \(n\) ，后手最后赢的一手拿的数量一定 \(\leqslant \frac{2}{3}n\) 。

  • 定理 \(2\) ：当 \(n\) 不是 \(fibonacci\) 数，先手必胜。

    • 根据引理 \(5\) ，我们把 \(n\) 拆分成 \(\sum\limits_{i=1}^k fib_{a_i}\)。

    • 先手第一次取 \(fib_{a_1}\) 颗。由引理 \(1\)（后半部分），后手无法一手取完 \(fib_{s_2}\)，从而这时的后手相当于上面定理 \(1\) 中的先手。攻守之势异也！