..

博弈论学习笔记

引言及一些定义

博弈论是运筹学的一个重要分支，在现实中有许多应用。OI 中的博弈论问题主要研究在一类组合游戏上的博弈，这类游戏大多满足如下性质：

  • 有两位选手交替对当前局面做出移动（move）使当前局面转移为另一种局面；
  • 对于某一种局面，合法的移动的集合是有限的；
  • 对于当前游戏的一种合法局面，合法的移动的集合只由当前局面确定，与当前操作人、以前的任何操作或其他任何因素均无关；
  • 若当前选手的合法移动集合为空集，则该选手判负；游戏本身一定会在有限步内结束。

满足以上条件的游戏称为公平组合游戏（Impartial Combinatorial Games， ICG）。可以发现，把 ICG 的局面看成点，移动操作看成边，游戏的所有可能局面和移动操作组成了一个单源点单汇点（即入度为零的点和出度为零的店都有且只有一个）的有向无环图。

ICG 的局面分为两类，P-position 与 N-position，其中 P 代表 Previous，N 代表 Next。两种局面的定义如下：

  • 上一个操作的选手必胜（即当前选手必败，或者说先手必败）的局面为 P-position；
  • 将要操作的选手必胜（即当前选手必胜，或者说先手必胜）的局面为 N-position。

除了定义，怎样判断一个局面是 P-position 还是 N-position？我们如下考虑：

  • 无法进行任何移动的局面（即终结局面，terminal position）为 P-position；
  • 能转移到 P-position 的局面为 N-position；
  • 所有合法移动都转移到 N-position 的局面为 P-position。

按照这个定义，我们可以按照拓扑序求出所有局面的类型。但是由于一个游戏的局面数过多，显然直接这样求，时间复杂度是不可接受的。因此我们需要探究怎样快速求出某个局面的类型。

NIM 游戏

游戏定义

我们从一个简单但经典的游戏—— NIM 游戏入手。NIM 游戏的一般定义如下：

甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。两人轮流按下列规则取走一些石子，游戏的规则如下：

  • 每一步应取走至少一枚石子；

  • 每一步只能从某一堆中取走部分或全部石子；

  • 如果谁无法按规则取子，谁就是输家。

我们来研究 NIM 游戏的一些性质，以对其进行简化来在可接受的时间复杂度内解决之。

初步简化

我们用一个 $n$ 元组 $(a_1, a_2, a_3, \cdots, a_n)$ 来描述有 $n$ 堆石子的 NIM 游戏的局面，其中 $a_i$ 表示第 $i$ 堆石子的数量。显然改变这个元组中数的顺序后其表示的局面不变。

让我们从简单开始，逐渐深入。

先来考虑只有一堆石子的情况：显然此时先手必胜。再来考虑只有两堆石子的情况：如果两堆石子数量相等，那么先手必败，因为无论先手怎么操作，后手都可以在另一堆石子上做同样的操作，则取走最后一个石子的一定是后手；如果两对石子数量不相等，那么先手必胜，因为先手可以先从多的那堆石子中取走一些使两堆石子数量相等，这时局面与之前讨论的先手必败等价，但后手却变成了先手。

再考虑三堆石子的局面？好像逐渐变得复杂了起来，我们不能继续这种思路了。

考虑对局面进一步抽象。

定义局面的合并：

$(a_1, a_2, a_3, \cdots, a_n) \oplus (b_1, b_2, b_3, \cdots, b_m) = (a_1, a_2, a_3, \cdots, a_n, b_1, b_2, b_3, \cdots, b_m)$。对于局面 $A, B, S$，如果$A + B = S$，那么称 $S$ 可以分解为子局面 $A$ 和 $B$，或 $A$ 和 $B$ 的和局面是 $S$。

按照与之前两堆石子时的思考方式，我们可以发现对于局面 $S = A + A$，即可以分解成两个相同的子局面的局面 $S$，先手必败，即此局面为 P-position。

考虑对于某个 P-position $A$，怎样判断它和另一个局面 $B$ 的和局面的胜负。我们发现，如果 $B$ 局面为 N-position，那么解决完 $A$ 以后先后手不变，则和局面类型与 $B$ 相同，为 N-position；反之同理可得整个局面为 P-position。因此，P-position 局面 $A$ 和另一个局面 $B$ 的和局面的类型与 $B$ 的类型相同。

于是我们发现，表示一个局面的元组中所有相同的元素可以被简化为一个元素或直接被删掉（取决于这个元素的数量的奇偶性），而所表示的局面的胜负性仍然与之前等价。故若我们只关心局面的胜负，一个局面可以用一个集合来表示。如果我们采用搜索的方法的话，复杂度比用元组表示有所减小但仍难以接受，因此我们考虑进一步简化局面的表示。

类比与联想

我们思考局面的合并这一运算的性质。

  • 相同的两个局面合并后结果为负局面；
  • 任意局面和负局面合并后结果不变；
  • 任意交换合并顺序，合并结果不变；换句话说，“合并”这一操作满足交换律与结合律。

观察这三个性质，是否想到了什么？

我们可以想到，二进制数的异或（$\def\xor{\operatorname{xor}} \xor$）运算有着类似的性质：

  • $\def\xor{\operatorname{xor}} a \xor a = 0$；
  • $\def\xor{\operatorname{xor}} a \xor 0 = a$；
  • 异或运算满足交换律与结合律。

由此我们想到，是否可以用一个数字表示一个局面？设 $f(S)$ 表示集合 $S$ 表示的局面对应的数字，令 $\def\xor{\operatorname{xor}} f(S) = \xor_{x \in S} f(x)$，若 $S$ 为空集则 $f(S) = 0$。这个判断方式是否正确？想要证明一个判断方式的正确性，对应于前面判断一个局面是 P-position 还是 N-position 的方式，只需证如下三点：

  • 该判断方式将所有终结局面判为 P-position；
  • 被这个判断方式判为 N-position 的局面一定可以转移到某个 P-position；
  • 被这个判断方式判为 P-position 的局面一定会转移到 N-position，或者说无法转移到 P-position。

下文中将 $f$ 称为“函数”，但更准确一些的说法应该是“映射”；函数是数集到数集之间的映射。

进行证明

一些引理：

  1. $\def\xor{\operatorname{xor}} a \xor b = s \Leftrightarrow a \xor s = b$。

    证明：

    $\def\xor{\operatorname{xor}} a \xor b = s \Leftrightarrow a \xor b \xor s \xor b = s \xor s \xor b \Leftrightarrow a \xor s = b$。

  2. 若 $\def\xor{\operatorname{xor}} a_1 \xor a_2 \xor a_3 \xor \cdots \xor a_n = p \neq 0$，则必存在一个 $k$ 使 $\def\xor{\operatorname{xor}} a_k \xor p < a_k$。

    证明：因为 $p \neq 0$ 所以 $p$ 的最高位一定是 $1$，设 $p$ 的最高位是第 $q$ 位，至少存在一个 $k$ 使 $a_k$ 的第 $q$ 位也是 $1$，则 $\def\xor{\operatorname{xor}} a_k \xor p$ 的第 $q$ 位是 $0$，因此 $\def\xor{\operatorname{xor}} a_k \xor p < a_k$。

  3. 若 $\def\xor{\operatorname{xor}} a_1 \xor a_2 \xor a_3 \xor \cdots \xor a_n = p = 0$，则不存在一个 $a_k$ 使得将 $a_k$ 减去一个数变为 $a_k’$ 后仍满足 $\def\xor{\operatorname{xor}} a_1 \xor a_2 \xor a_3 \xor \cdots \xor a_n = p = 0$。

    证明：

    若 $\def\xor{\operatorname{xor}} a_1 \xor a_2 \xor \cdots \xor a_k \xor \cdots \xor a_n = a_1 \xor a_2 \xor \cdots \xor a_k’ \xor \cdots \xor a_n$，则由异或运算的消去律可得 $a_k = a_k’$，故不存在所求的 $a_k$。

由此我们可得：

  • 对于终结局面 $T$，$f(T) = 0$。

  • 若 $f(S) \neq 0$，则必存在一种操作使 $S \rightarrow T$，且 $f(T)= 0$。

    证明：

    设 $S = {a_1, a_2, \cdots, a_n}, p = f(S) \neq 0$，因为 $p \neq 0$， 则必然存在 $k$ 使 $\def\xor{\operatorname{xor}} a_k \xor p < a_k$。因为集合中元素是无序的，所以不妨设 $\def\xor{\operatorname{xor}} k = 1, a_1 \xor p = x$；由引理 1 得$\def\xor{\operatorname{xor}} p = a_1 \xor a_2 \xor \cdots \xor a_n \Leftrightarrow a_2 \xor \cdots \xor a_n = a_1 \xor p = x$。

    先手将 $a_i$ 变成 $x$ 后局面变为 $T$，$\def\xor{\operatorname{xor}} f(T) = x \xor (a_2 \xor \cdots \xor a_n) = x \xor x = 0$。

  • 若 $f(S) = 0$，则所有使得 $S \rightarrow T$ 的合法操作都满足 $f(T) \neq 0$。

    证明：由引理 3 易得。

对比我们之前归纳的判断一个局面是 P-position 还是 N-position 的方法：

  • 无法进行任何移动的局面（即终结局面，terminal position）为 P-position；
  • 能转移到 P-position 的局面为 N-position；
  • 所有合法移动都转移到 N-position 的局面为 P-position。

我们可以发现，这三条方法与刚刚得到的三条结论是一一对应的。因此在“判断一个局面的类型”这个问题上，我们找到了一种时间复杂度可以接受的判断方式，即对该局面的集合表示 $S$ 求 $f(S)$ 的值：当 $S$ 为 P-position 时 $f(S) = 0$，否则 $f(S) \neq 0$。

解决问题

于是，对于一个 NIM 游戏的局面，我们只需要把每堆石子的数量异或起来，就可以判断这个局面的类型了。

归纳与推广

另一个游戏

我们尝试玩另外一个游戏。游戏说明如下：

甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。两人轮流按下列规则取走一些石子，游戏的规则如下：

  • 每一步应取走至少一枚石子，至多 $m$ 枚石子；
  • 每一步只能从某一堆中取走部分或全部石子；
  • 如果谁无法按规则取子，谁就是输家。

我们可以发现，这个问题只是在 NIM 游戏上加了一个最多取 $m$ 枚的限制。对于这个问题，似乎不能简单套用之前的结论。思考后发现，是因为 NIM 游戏的 $f$ 函数不能直接适用于这个问题。于是我们考虑这个问题的 $f$ 函数应该如何设计。

我们依然考虑之前的三条依据：

  • 无法进行任何移动的局面（即终结局面，terminal position）为 P-position；
  • 能转移到 P-position 的局面为 N-position；
  • 所有合法移动都转移到 N-position 的局面为 P-position。

我们可以发现，对于完整的问题，我们可以考虑将它分解为许多子局面来计算。在这个问题中，最小的子局面是只有一堆石子的情况。设这堆石子的数量为 $x$，观察后发现：

  • 当 $x = 0$ 时，当前局面为 P-position；
  • 当 $x \le m$ 时，先手总是可以一次取光（即转移到 P-position），因此当前局面为 N-position；
  • 当 $x = m + 1$ 时，先手取完后剩下的石子数 $x’$ 一定满足 $x’ \le m$，所以当前局面无论如何都会转移到 N-position，因此当前局面为 P-position；
  • 当 $x > m + 1$ 时，当前局面又可以分解为许多个大小为 $m + 1$ 的（不影响当前局面胜负性的 P-position）子局面，因此当前局面的胜负性与大小为 $x \bmod (m + 1)$ 的局面相同。

即：对于只有一堆数量为 $x$ 的石子的情况 $S$ ，$f(S) = x \bmod (m + 1)$。

对于原问题，因为这个问题中合并的性质与 NIM 游戏并无区别，因此我们还是可以直接将所有子局面的 $f$ 值异或起来得到此问题的答案。

但是，对于每一个问题，如果我们都这样去“捏”出一个新的 $f$ 函数，显然是费事费力。那么，有没有一个更加抽象但更加普适的 $f$ 函数呢？

我们来看下一个游戏。

又一个游戏

规则如下：

  • 甲乙两人面对若干排石子，其中每一排石子的数目可以任意确定。两人轮流按下列规则取走一些石子，游戏的规则如下：
  • 每一步必须从某一排中取走两枚石子；
  • 这两枚石子必须是紧紧挨着的；
  • 如果谁无法按规则取子，谁就是输家。

在研究这个游戏的问题中，我们还是只关心对于某个局面，先手的胜负性。

可以发现，这个游戏的规则已经和 NIM 游戏不是很相似了。但是 NIM 游戏的一些性质，这个游戏也都具有。因此我们猜想，这个问题也有类似的方法进行求解。

如果要按照之前的方法求解，那么我们就要找到一个合适的 $f$ 函数。

分析问题性质

分析问题并简化之。“从某一排中取走两枚石子”这个操作，实际上是在做什么？思考后发现，这个操作实际上是将一排石子从某个地方分开并取走两枚，分成的两段可以视为新的两排石子。于是，这个问题中，局面的变化不再是一个元素的变化，而是一个元素变成两个新元素。

回忆前面的思考过程，我们构造出的 $f$ 函数仍应满足如下性质：

  • 对于终结局面 $T$，$f(T) = 0$。
  • 若 $f(S) \neq 0$，则必存在一种操作使 $S \rightarrow T$，且 $f(T)= 0$。
  • 若 $f(S) = 0$，则所有使得 $S \rightarrow T$ 的合法操作都满足 $f(T) \neq 0$。

在这里，我们开始考虑局面的转移。设 $N(S)$ 表示局面 $S$ 能转移到的所有局面的集合，$g(S) = {f(x) \mid x \in N(S) }$。逐条考虑上面三条性质。

  • 对于终结局面 $T$，$f(T) = 0$。

$f$ 应满足当 $N(T) = \varnothing, g(T) = \varnothing$ 时，$f(T) = 0$。单这一条好像发现不了什么，我们继续。

  • 若 $f(S) \neq 0$，则必存在一种操作使 $S \rightarrow T$，且 $f(T)= 0$。

首先我们还是可以想到，在这个问题里，子问题的合并性质依然与之前相同。因此我们依然可以将一个局面的 $f$ 值定义为所有子局面的 $f$ 值的异或和，即 $\def\xor{\operatorname{xor}} f(S) = \xor_{x \in S} f(x)$。

设 $S = {a_1, a_2, \cdots, a_n}, p = f(S) \neq 0$，因为 $p \neq 0$， 则必然存在 $k$ 使 $\def\xor{\operatorname{xor}} a_k \xor p < a_k$。因为集合中元素是无序的，所以不妨设 $\def\xor{\operatorname{xor}} k = 1, a_1 \xor p = x$；$\def\xor{\operatorname{xor}} p = a_1 \xor a_2 \xor \cdots \xor a_n \Leftrightarrow a_2 \xor \cdots \xor a_n = a_1 \xor p = x$。

如果先手将子局面 $a_1$ 变为 $B = {b_1, b_2, \cdots, b_m}$，则 $B \in N({a_1}),f(B) \in g({a_1})$。设这时的局面为 $T$，则 $\def\xor{\operatorname{xor}} f(T) = f(B) \xor f({a_2, \cdots, a_m}) = f(B) \xor x$。

$f(T) = 0 \Leftrightarrow f(B) = x$。因为 $B \in N({a_1})$，所以若 $x \in g({a_1})$，则必有一个 $B$ 满足 $f(B) = x$。因为 $x < f({a_1}) = a_1$，所以若 ${0, 1, 2, \cdots, f({a_1}) - 1} \subset g({a_1})$，则 $x \in g({a_1})$。

即：${0, 1, 2, \cdots, f({a_1}) - 1} \subset g({a_1}) \Rightarrow f(T) = 0$。

也就是说，命题“若 $f(S) \neq 0$，则必存在一种操作使 $S \rightarrow T$，且 $f(T)= 0$”的充分条件是 ${0, 1, 2, \cdots, f(S) - 1} \subset g(S)$。

  • 若 $f(S) = 0$，则所有使得 $S \rightarrow T$ 的合法操作都满足 $f(T) \neq 0$。

设 $S = {a_1, a_2, \cdots, a_n}, p = f(S) = 0$。由于先手只能选择一排石子，不妨设他选择了 $a_1$ 并将 $a_1$ 变为了 $B = {b_1, b_2, \cdots, b_m}$。因为 $\def\xor{\operatorname{xor}} f(S) = f({a_1}) \xor f({a_2, \cdots, a_n}) = 0$，所以 $f({a_1}) = f({a_2, \cdots, a_n})$。 设转移后的局面为 $T$，则 $\def\xor{\operatorname{xor}} f(T) = f(B) \xor f({a_2, \cdots, a_m})$。

$f(T) \neq 0 \Leftrightarrow f(B) \neq f({a_2, \cdots, a_m}) \Leftrightarrow f(B) \neq f({a_1})$。又 $B \in N({a_1})$，故 $f(B) \neq f({a_1}) \Leftrightarrow f({a_1}) \notin g({a_1})$。简化一下得 $f(T) \neq 0 \Leftrightarrow f({a_1}) \notin g({a_1})$。

也就是说：命题“若 $f(S) = 0$，则所有使得 $S \rightarrow T$ 的合法操作都满足 $f(T) \neq 0$” 的充要条件是 $f(S) \notin g(S)$。

综上所述，$f$ 函数满足我们要求的充分条件是：

  • $f(S) \notin g(S)$；
  • ${0, 1, 2, \cdots, f(S) - 1} \subset g(S)$。

捏函数

令全集 $U = \mathbb{N}$，设 $\operatorname{mex}(S) = \min(\complement_U S)$，即 $\operatorname{mex}(S)$ 为最小的不属于 $S$ 的自然数，“mex” 是 “minimal excludant” （最小不包含）的缩写。

定义 $f(S) = \operatorname{mex}{g(S)}$，即 $f(S)$ 为所有不是 $S$ 能转移到的局面之一的 $f$ 值的最小的自然数（这句话我做不到简化……）。

我们刚刚捏出来的这个 $f$ 有个更广为人知的名字，叫做 SG（Sprague-Grundy）函数。

有了这个函数，我们就可以用与之前一样的方式求胜负性了。

更进一步的推广

我们考虑刚刚捏 $f$ 函数也就是 SG 函数的过程中，几乎没有涉及到刚才这个游戏本身，而是抽象出了这个过程，在此之上捏出了 SG 函数。因此，SG 函数应当具有较好的普适性。我们唯一用到的性质，就是“将子游戏合并为和游戏”这个过程符合异或形式。因此，只要是满足这个性质的游戏，我们都可以用这种方式解决。那么，什么样的游戏具有这个性质？

我们将问题再次抽象。让我们回到本文开头的有向无环图上，我们来玩一个看起来更一般的游戏：

给定一个有向无环图和一个起始顶点上的一枚棋子，两位选手轮流将这枚棋子沿有向边移动，无法移动者输。

实际上，这个游戏可以认为是所有 ICG 的抽象模型。让我们站在更高的层次定义 SG 函数：

$SG(x) = \operatorname{mex}({SG(y) \mid \textrm{x is a predecessor of y}})$，即 $SG(x)$ 是所有 $x$ 的后继的 $SG$ 值的 $\operatorname{mex}$ 值。

来研究 SG 函数的性质。首先我们发现对于出度为 $0$ 的点，其 $SG$ 值为 $0$；对于 $SG(x) \neq 0$ 的点 $x$，其一定有一个后继 $SG$ 值为 $0$；对于 $SG(x) = 0$ 的点 $x$，其所有后继的 $SG$ 值都不为 $0$。这三句话，恰好与我们之前归纳的三个性质还是一一对应。

我们再来考虑 NIM 游戏，我们可以将其抽象为 $n$ 枚棋子在有向无环图上移动。但是事实上，因为每堆石子互不影响（或者说，每枚棋子互不影响），所以可以再次抽象成许多子游戏：即有 $n$ 个有向无环图，每个图上有一个棋子，这样对结论不会产生变化。我们由此定义有向无环图游戏的和游戏：设 $G_1,G_2,\cdots,G_n$ 是 $n$ 个有向图游戏，定义游戏 $G$ 是 $G_1,G_2,\cdots,G_n$ 的和（Sum），游戏 $G$ 的移动规则是：任选一个子游戏 $G_i$ 并移动上面的棋子。

Sprague-Grundy 定理：对于有向无环图游戏 $G$，若其为有向无环图游戏 $G_1, G_2, \dots, G_n$ 的和游戏，则 $\def\xor{\operatorname{xor}} SG(G) = SG(G_1) \xor SG(G_2) \xor \cdots \xor SG(G_n))$。

于是我们回答了本节开头的问题：能抽象为有向无环图的游戏，都满足该性质。

也就是说，所有 ICG 游戏问题都能这样解决。我们就这样得到了一类组合游戏问题的普适解法。但需要注意的是，我们在解决问题的时候，不应把许多游戏乱捏到一起，而是应该利用之前探究的性质，尝试将复杂、耦合性强的和问题，分解为简单、耦合性弱的子问题，再合并求解。化繁为简，才能感受到问题与解法优美的本质。

例题

1

[POI 2000] Stripes-pas

题目描述

有一排 $m$ 个石子，两个人交替取连续的 $C$ 颗或 $Z$ 颗或 $N$ 颗，不能操作者输，求先手的胜负。

$1 \le C, Z, N \le m \le 1,000$。

题解

局面 ${i}$ 可以转移到的子局面是 ${k - X, i - k}$，其中 $\min(C, Z, N) \le k \le i, X \in {C, Z, N}$，即在第 $k$ 个石子处向左取 $X$ 个后形成的子局面。这样一个子局面的 SG 值 为 $SG(k - X) \operatorname{xor} SG(i - k)$。显然 $0 \le k - x \le i - k \le i$，故从 $1$ 到 $m$ 枚举初始局面计算 SG 值，可以保证中间过程中子局面的 SG 值一定是之前已经求出的。计算初始局面的 SG 值直接按照 SG 函数的定义枚举子局面并保存它们的 SG 值，开个桶标记后找最小的没出现过的值就是当前枚举的这个初始局面的 SG 值。

2

题目描述

有编号为 $0$ 到 $n -1$ 的 $n$ 阶台阶，每个台阶上有一堆石子，两个人交替将某个台阶上的一些石子放到下面一阶上，无法操作者输。

题解

这个问题的简化方式有点特别，不是考虑子局面而是考虑问题本身的性质。我们按照台阶编号的奇偶性讨论，可以发现因为最后一个（无法进行操作的台阶）的编号为 $0$，是一个偶数，所以无论先手后手，如果将偶数号台阶上的石子放到下一个奇数号的台阶上，下一个人总是可以将这些石子再放到下一个偶数号台阶上，直到所有偶数号台阶上的石子都被放到 $0$ 号台阶上，仍保持游戏局面胜负性不变。而在 $0$ 号台阶上的石子对局面没有影响，故所有偶数号台阶上的石子对局面胜负性都没有影响，将奇数号台阶上的石子放到下一个偶数号台阶上等价于将这些石子直接拿走，于是问题转化成对所有奇数号台阶上的石子做一个 NIM 游戏。

3

题目描述

有一排 $n$ 个硬币，有的正面朝上，有的背面朝上。两个人轮流对硬币进行翻转，翻转规则如下：先选一枚正面朝上的硬币翻转，然后如果愿意的话从这枚硬币左边选取一枚硬币（不论哪面朝上）翻转。最后翻转使得所有硬币反面朝上的玩家胜利。

题解

我们考虑将这个问题进行归纳。如果我们将位置在 $i$ 的正面朝上的硬币看作一堆数量为 $i$ 的石子，就可以发现这个游戏与 NIM 游戏的相似之处，即结束条件相似。但问题在于这两个游戏的转移操作不是一一对应的。于是我们来考虑更本质的因素。

只考虑整个局面中的两枚硬币 $i$ 与 $j$，其中 $i < j$，右面的硬币 $j$ 正面朝上。我们考虑从 $j$ 这堆石子中取出 $i$ 个这个操作在硬币游戏中的对应操作。如果 $i$ 反面朝上，那么同时翻转 $i$ 与 $j$ 等价于从 $j$ 这堆石子中取出 $j - i$ 枚；如果 $i$ 正面朝上，那么同时翻转 $i$ 和 $j$ 等价于从 $j$ 中取 $j - i$ 个后将剩下的 $i$ 个与第 $i$ 堆消去。故从 $j$ 中取 $i$ 枚石子对应的操作是将第 $j$ 个硬币与第 $j - i$ 个硬币同时翻转。

也就是说，这个游戏虽然无法实现 NIM 游戏的所有操作，但它的局面能转移到的局面的 SG 函数值与对应的 NIM 游戏局面相同，因此这个游戏的 SG 值与对应的 NIM 游戏 SG 值相同。只需要将在第 $i$ 个位置的正面朝上的硬币看做有 $i$ 枚石子的石子堆，做一遍 NIM 游戏即可。

4

[POI2003/2004] stage I Game

题目描述

有一个 $m \times 1$ 的棋盘，一些格子上有硬币。两个人轮流选择一枚硬币，将它放在右边最近的空格中，如果不存在这样的空格就直接把这个硬币扔掉。无法操作的人负，换句话说把最后一个硬币扔掉的人胜。

题解

在这个题目中，每个硬币之间相互影响，很难分解成关于单个硬币的子游戏的和。我们考虑转换这个游戏。我们发现：对于连续的一段硬币，将它们中的任意一个移到右边的某个空位所需要的操作次数都是相等的，因此尝试将相邻的硬币分为一组。将任意空格与其左边最近的空格之间的空间（也就是两个相邻空格之间的“并不存在的”空间或者某段连续的硬币）**看成一个阶梯，最右面的空格的右边看做第 $0$ 号台阶，某段空间中的硬币数看做石子数，则这个游戏和前文提到的阶梯游戏完全等价。**通过这样构造，我们使一个硬币右边的空格数等价为它所在的阶梯下面的阶梯数。换个角度考虑，将楼梯 $i$ 上的 $t$ 个石子移动 $k$ 个到下层，可以看做将连续的 $t$ 个硬币中的从右向左数第 $k$ 个硬币移动一次，这样被移动的硬币原位置左边的硬币被移出棋盘的步数不变，而被移动的硬币原位置右边的硬币与它本身被移出棋盘的步数都少了 $1$。一个硬币右边的空格数 $+ 1$ 即为该硬币被移出棋盘需要的步数，即它等价所在的楼梯的号数。

这个问题的转化较为抽象，可以画图并结合图片自己手玩一下来理解。

//待补充：无向图删边游戏，Anti-SG 游戏，Multi-SG 游戏，Every-SG 游戏。

参考资料

  1. IOI 2002 中国国家集训队论文《 由感性认识到理性认识——透析一类搏弈游戏的解答过程》，张一飞
  2. IOI 2007 中国国家集训队论文《解析一类组合游戏》，王晓珂
  3. IOI 2009 中国国家集训队论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》，贾志豪
  4. 【算法】 博弈论入门笔记，K-XZY