博弈论：MEX 规则和 Nimbers

Question

我一直在阅读这篇关于尼伯斯和博弈论的小教程。

有人可以解释为什么墨西哥规则管辖游戏位置的数量吗？

请参阅： http: //en.wikipedia.org/wiki/Mex_（数学）

从最小排除序数来看，在我看来，一个状态的 Nimber 实际上是该人“无法”达到的最小状态。这对管理当前游戏的状态有何帮助？

我在维基百科上看到了一个证明，但我不明白其中的任何内容。 http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem#Proof

Answer 1

Nimber 的整个想法是与众所周知的 Nim 游戏进行类比。因此，除非您了解该游戏，否则它对您来说毫无意义。

在 Nim 游戏中，我们有一堆东西。在每一回合中，你可以从一堆中拿取任意数量的东西，并且只能拿取一堆。获胜者是从最后一堆中拿走最后一件东西的人。

现在尝试让自己相信以下事实。

1. 在 Nim 中，单堆的数量就是该堆的大小。
2. 如果我们有 2 堆游戏，则位置的编号是两堆大小的异或。（您需要进行双重诱导。）
3. 如果我们将桩的集合分成两部分，那么整个位置的编号就是两个子集的编号的异或。

现在重点来了。用具有保证赢/输的任意确定性游戏替换桩。将收藏变成一场游戏，轮流玩不同的游戏，赢得最后一场游戏的人获胜。上面定义的 nimber 告诉你，通过与 Nim 类比，如何完美地玩组合游戏。

如果您只玩常规的 2 人游戏，那么您真正需要知道的关于数字的唯一事实是它是 0（您处于失败位置）还是非零（您处于获胜位置）位置）。仅当您可以将复杂的游戏分解为您在每个回合中进行选择的单独游戏的集合时，确切的数字才有用。然而，数量惊人的数学游戏确实承认这种结构。