algorithm - 博弈论 : MEX rule and Nimbers

Question

我一直在读这个小 tutorial关于 Nimbers 和博弈论。

有人可以解释为什么 mex 规则控制游戏位置的数量吗？

参见:http://en.wikipedia.org/wiki/Mex_(mathematics)

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

我在维基百科上看到了一个证明，但我对它一无所知。 http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem#Proof

Answer 1

nimber 的整个概念是与广为人知的 Nim 游戏进行类比。因此，除非您了解该游戏，否则它对您来说毫无意义。

在 Nim 游戏中，我们有一堆东西。在每一轮中，您可以从一堆和一堆中拿取尽可能多的东西。获胜者是从最后一堆中拿走最后一件东西的人。

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

1. 在 Nim 中，单堆的数量就是该堆的大小。
2. 如果我们有一个 2 堆游戏，位置的数量是两堆大小的异或。 (您需要进行双重感应。)
3. 如果我们将一堆堆分成两部分，那么整个位置的数量就是两个子集的数量的异或。

现在重点来了。用保证输赢的任意确定性游戏替换堆。将收藏变成一个游戏，您可以轮流玩不同的游戏，最后一场比赛获胜的人获胜。上面定义的数字告诉你，类比Nim，如何完美地玩组合游戏。

如果您只是玩普通的 2 人游戏，那么您真正需要知道的关于数字的唯一事实是它是 0(您处于亏损状态)还是非零(您处于亏损状态)处于获胜位置)。只有当您可以将一个复杂的游戏分解为您在每个回合中选择的一组单独的游戏时，确切的数字才有用。然而，数量惊人的数学游戏确实承认这种结构。