反常游戏

反常游戏、反 Nim 游戏的定义。

以反 Nim 游戏为例，这里给出反 Nim 游戏的结论以及证明：

规定：字母 N 和 P 分别代表先手必胜与必败。

一个局面为 N 态的充要条件是有至少一条出边连接至 P 态。

一个局面为 P 态的充要条件是每一条出边都连接到 N 态。

反 Nim 游戏

为方便书写，用字母表示 $\oplus_{i=1}^{n}a_{i}$ 。

结论：

当全部 $a_{i}=1$ ，如果有奇数堆石子就为 P 态，有偶数堆则为 N 态。
当至少一个 $a_{i}>1$ ， $T\neq 0$ 时为 N 态，否则为 P 态。

证明 1：显然。

证明 2：

情况 A：若只有一个 $a_{i}>1$ （此时一定 $\neq 0$ ），则先手选择转移到全部 $a_{i}=1$ 的局面，并且先手可以在这次决策中控制转移后堆数的奇偶。

故这种情况 是 N 态。

情况 B：（不考虑取值）有至少个 $a_{i}>1$ 。

小情况 B1： $T\neq 0$ ：通过 Nim 游戏可知一定能够转移到且至少有个 $a_{i}>1$ 的局面（小情况 B2）。

证明：显然可以转移到，如果此时只剩一堆 $a_{i} > 1$ ，由于这堆的最高位不能被异或消去，故 $T\ne 0$ ，于是这种情况不会发生。

小情况 B2：：

一方面可以转移到至少个 $a_{i}>1,T\neq 0$ 的局面，即情况 B1。

另一方面随着游戏进行（B1, B2 循环），数量大于 1 的堆会逐渐减少，最终只剩一堆，这就变成了情况 A，为 N 态。

观察情况 B，小情况 B2 能给对面 N 态或至少个 $a_{i}>1,T\neq 0$ 的局面，而小情况 B1 仅能给对面的局面。

所以在情况 B 下，小情况 B2 为 N 态，B1 为 P 态。

也就是说 当至少个 $a_{i}>1,T\neq 0$ 时为 N 态，否则为 P 态。

综合情况 A 和情况 B 的结论，结论 2 得证。

综上，结论 1 和 2 皆得证。结论得证。

本页面最近更新：2024/11/14 11:42:15，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：2008verser, Backl1ght, billchenchina, Enter-tainer, FFjet, Ir1d, Molmin, ouuan, SamZhangQingChuan, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用