按照自己的学习顺序写的，可能有点奇怪。这是这个系列中唯一有用的东西了。

ICG 游戏

Nim 游戏

有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 个，每次行动可以从任意一堆中取出任意多个（至少一个），两人轮流行动，先不能行动者输。问谁有必胜策略。

在解决具体的问题前，我们首先关注博弈本身的性质。

用 \(x\) 表示一个局面，用一个局面先手必胜，那么 \(P(x)=1\)，否则 \(P(x)=0\)。类似的，后手必胜时有 \(N(x)=1\)，否则 \(N(x)=0\)。我们有 \(P(x)\oplus N(x)=1\)，这里 \(\oplus\) 表示按位异或运算（也记为 \(\operatorname{xor}\)），也就是说一个局面要么先手必胜，要么后手必胜。这个结论的严谨证明将在后面出现。

更进一步，如果一个局面 \(x\) 存在后续局面 \(y\) 有 \(P(y)=1\)，那么 \(P(x)=1\)，否则 \(P(x)=0\)。类似的，如果一个局面 \(x\) 所有后续局面 \(y\) 都有 \(N(y)=1\)，则 \(N(x)=1\)，否则 \(N(x)=0\)。

基于这样基本的理论，我们可以轻易的写出 dp 转移来解决这个问题，不够这样的复杂度是 \(O(V^n)\) 的，其中 \(V\) 表示 \(a_i\) 的最大取值，这样的复杂度是难以接受的。

试着发掘 Nim 游戏本身的性质，下面是两个例子。此处用 \((a_1,a_2,a_3\ldots a_n)\) 表示有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 个的局面。

  • 一开始，局面为 \((x,x)\)，那么先手后手只需要模仿先手的操作，局面就总是形如 \((x,x)\)，且该先手操作，易知石子个数单减，于是局面 \((x,x)\) 下后手必胜。如果 \(x\) 表示若干堆石子的状态，不难发现上面的过程依然可以使得后手必胜。

  • 一开始，局面为 \((2,3)\)，先手只需从第 \(2\) 堆中取 \(1\) 个，使局面变为 \((2,2)\)，就可以变为上面的情形，故局面 \((2,3)\) 是先手必胜的。

  • 一开始，局面为 \((1,2,3)\)，尝试所有可能后可以发现是后手必胜的。

可以用程序验证更大的例子，观察 \((x,y,z)\) 在 \(1\le x\le y\le z\le6\) 的答案（ Previous 表示先手必胜，Next 表示后手必胜 ）：

(1,1,1)=Previous (1,1,2)=Previous (1,1,3)=Previous (1,1,4)=Previous (1,1,5)=Previous (1,1,6)=Previous
(1,2,2)=Previous (1,2,3)=Next (1,2,4)=Previous (1,2,5)=Previous (1,2,6)=Previous
(1,3,3)=Previous (1,3,4)=Previous (1,3,5)=Previous (1,3,6)=Previous
(1,4,4)=Previous (1,4,5)=Next (1,4,6)=Previous
(1,5,5)=Previous (1,5,6)=Previous
(1,6,6)=Previous
(2,2,2)=Previous (2,2,3)=Previous (2,2,4)=Previous (2,2,5)=Previous (2,2,6)=Previous
(2,3,3)=Previous (2,3,4)=Previous (2,3,5)=Previous (2,3,6)=Previous
(2,4,4)=Previous (2,4,5)=Previous (2,4,6)=Next
(2,5,5)=Previous (2,5,6)=Previous
(2,6,6)=Previous
(3,3,3)=Previous (3,3,4)=Previous (3,3,5)=Previous (3,3,6)=Previous
(3,4,4)=Previous (3,4,5)=Previous (3,4,6)=Previous
(3,5,5)=Previous (3,5,6)=Next
(3,6,6)=Previous
(4,4,4)=Previous (4,4,5)=Previous (4,4,6)=Previous
(4,5,5)=Previous (4,5,6)=Previous
(4,6,6)=Previous
(5,5,5)=Previous (5,5,6)=Previous
(5,6,6)=Previous
(6,6,6)=Previous

我们可以猜测先手必胜的条件是 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n\ne0\)，考虑证明：

等价的命题是：后手必胜的条件是 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n=0\)。下面先给出构造。

我们假设 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n=x\)。

由异或的性质可知，一定存在 \(a_k\)，使得 \(\operatorname{highbit}(a_k)=\operatorname{highbit}(x)\)。从第 \(k\) 堆中取出 \(a_k-(a_k\oplus x)\) 个后，第 \(k\) 堆余下 \(a_k\oplus x\) 个，此时有

\[\begin{align*} a_1\oplus a_2\oplus\cdots\oplus a_k^\prime\oplus \cdots\oplus a_n&=a_1\oplus a_2\oplus\cdots\oplus a_k\oplus x\oplus \cdots\oplus a_n\\ &=x\oplus x\\ &=0\\ \end{align*} \]

如果当前已经有 \(a_1\oplus a_2\oplus \cdots \oplus a_n=0\)，那么不管先手如何操作，之后都有 \(a_1\oplus a_2\oplus \cdots \oplus a_n\ne0\)，因为对于任意的 \(x\)，有且只有 \(x\) 满足 \(x\oplus x=0\)。

而终止局面 \((0)\) 时显然满足 \(a_1=0\)，且这个局面是后手必胜的。那么通过上文的构造方式就可以使得 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n\ne0\) 时先手必胜。

反常 Nim 游戏

Nim 游戏胜负规则相反。

直接上结论了：

满足下列条件之一时先手必胜，否则后手必胜。

  • 有偶数堆 \(1\) 个石子的堆。
  • 有至少一堆石子个数 \(>1\)，且 \(a_1\oplus a_2\oplus \cdots \oplus a_n\ne0\)。

第一个条件显然，考虑第二个条件：

若只有一堆石子个数 \(>1\)，那么我们可以分奇偶讨论。

  • 如果有偶数堆，那么把 \(>1\) 的那堆取完。
  • 如果有奇数堆，那么把 \(>1\) 的那堆取到只有 \(1\) 个。

易知此时先手必胜。

若有多堆石子个数 \(>1\)，考虑 \(a_1\oplus a_2\oplus \cdots \oplus a_n=x\)。

  1. \(x=0\)，考虑可能的转移。
    • 拿走一堆使得其余下的个数 \(\le1\)，那么可以转化为先手必胜的情况。
    • 否则一定有 \(x^\prime\ne0\)，转化为下面的情况。
  2. \(x\ne0\)，用 Nim 游戏一样的构造转移到上面的状态。注意到转移时石子个数递减，最终转移一定变成只有一堆石子时先手必胜。

综上可知先手必胜。

SG 函数

到这里，我们终于可以给出 ICG 游戏的定义：

在一个 DAG 上，有一个棋子，两人轮流移动一步（走过一条边），先不能移动者负。

定义 \(\text{SG}(x)\) 函数，其中 \(x\) 是 DAG 上的一个点。

定义 \(\operatorname{SG}(x)=0\) 当 \(x\) 出度为 \(0\)，否则 \(\operatorname{SG}(x)=\operatorname{mex}(\{\operatorname{SG}(v)\mid x\rightarrow v\})\)，即其所有后继的 \(\operatorname{SG}\) 值的 \(\operatorname{mex}\)。

定义 \(\operatorname{mex}(S)\) 表示最小的集合 \(S\) 中未出现过的自然数，比如 \(\operatorname{mex}(1,2,3)=0,\operatorname{mex}(0,1,2,3)=4,\operatorname{mex}(0,1,2,4)=3\)。

如果一个点 \(x\) 满足 \(\operatorname{SG}(x)=0\)，那么在这个点处后手必胜，否则先手必胜。

证明和 Nim 游戏几乎一模一样：终止处 \(\operatorname{SG}(x)=0\)，而 \(\operatorname{SG}(x)>0\) 意味着可以从这个点走到 \(\operatorname{SG}(x)=0\) 的点，于是只需要把 Nim 游戏中的名词替换一下就可以了。

k-SG

更常见的情形是有多个 ICG 游戏同时存在，每次可以选择其中一个操作。

不加证明的，我们给出 \(\operatorname{SG}(x)=\operatorname{SG}(x_1)\oplus \operatorname{SG}(x_2)\oplus \operatorname{SG}(x_3)\oplus\ldots\oplus \operatorname{SG}(x_n)\)。其中 \(x_1,x_2\ldots x_n\) 表示 \(n\) 个子游戏。

证明过程和上面几乎一致，故略去。

策梅洛定理

就是 Nim 游戏里说后面会证的那个东西。

对于一个博弈，如果满足下列条件，那么任何局面要么先手必胜，要么后手必胜。

  • 两个玩家轮流操作，他们都足够聪明。
  • 下一个局面只和当前局面有关，和谁操作无关。
  • 双方都完全了解这个博弈的所有信息。
  • 博弈过程中不涉及随机变量，且胜负只由局面唯一决定。
  • 终止状态时，一个人赢，另一个人输，且不存在平局。
  • 博弈总会停止。

证明其实很简单，从终止局面向初始局面编号为 \(0,1,2\ldots n\)，在第 \(0\) 个局面时的后手如果输了，说明在 \(1\) 个局面时（此时他是先手）他已经必败了，否则他不是足够聪明的。以此类推，用数学归纳法不难得出正整数时任何局面 \(x\) 都满足 \(P(x)\oplus N(x)=1\)。

习题

新 Nim 游戏

Nim z utrudnieniem

原文地址：http://www.cnblogs.com/efX-bk/p/play_with_1.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性