文章目录


由于出题人在膜你赛出了假题，于是就发现了这个坑点……
反正这个出题人出的都是假题
我感觉这个好像大多数人都没有注意到0_0

建议看下贾志豪的组合游戏论文，反正下面大多是贺来的，而且我还懒得贺证明……

先是一些定义和结论

Anti-Nim

定义

  • 桌子上有 N 堆石子，游戏者轮流取石子。
  • 每次只能从一堆中取出任意数目的石子，但不能不取。
  • 取走最后一个石子者败。

结论

先手必胜当且仅当：

  • 所有堆的石子数都为 1 且游戏的 SG 值为 0
  • 有些堆的石子数大于 1 且游戏的 SG 值不为 0

Anti-SG

定义

  • Anti-SG 游戏规定，决策集合为空的游戏者赢。
  • Anti-SG 其他规则与 SG 游戏相同。

SJ 定理

对于任意一个 Anti-SG 游戏，如果我们规定当局面中所有的单一游戏的 SG 值为 0 时，游戏结束，则先手必胜当且仅当：

  • 游戏的 SG 函 数不为 0 且游戏中某个单一游戏的 SG 函数大于 1
  • 游戏的 SG 函数 为 0 且游戏中没有单一游戏的 SG 函数大于 1。

<mark>注意</mark>：加粗部分灰常重要，如果所有单一游戏SG值都为0，而游戏还未结束的话，SJ定理是不适用的。