反常游戏

author : 2008verser

反常游戏、反 游戏的 定义

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

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

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

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

反 Nim 游戏

为方便书写,用字母 表示

结论:

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

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

证明 1:显然。

证明 2:

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

故这种情况

情况 :(不考虑 取值)有至少 2 个

小情况 :通过 游戏可知一定能够转移到 的局面(小情况 )。

小情况

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

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

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

所以在情况 下,小情况 态, 态。

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

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

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