反常游戏

反常游戏、反 游戏的

定义。

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

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

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

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

反 Nim 游戏

为方便书写，用字母 表示 。

结论：

• 1、当全部 ，如果有奇数堆石子就为 态，有偶数堆则为 态。

• 2、当至少一个 ， 时为 态，否则为 态。

证明 1：显然。

证明 2：

情况 ：若只有一个 （此时 一定 ），则先手选择转移到全部 的局面，并且先手可以在这次决策中控制转移后堆数的奇偶。

故这种情况 是 态。

情况 ：（不考虑 取值）有至少 2 个 。

小情况 ：：通过 游戏可知一定能够转移到 的局面（小情况 ）。

小情况 ：：

一方面可以转移到至少 2 个 的局面，即 。

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

观察情况 ， 能给对面 态或至少 2 个 的局面，而 仅能给对面 的局面。

所以在情况 下，小情况 为 态， 为 态。

也就是说 当至少 2 个 时为 N 态，否则为 态。

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

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