1

我一直在阅读这个关于 Nimbers 和博弈论的小教程。

有人可以解释为什么mex 规则支配游戏位置的 nimber 吗？

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

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

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

4

2 回答 2

4

Nimber 的整个想法是与众所周知的 Nim 游戏进行类比。所以除非你理解那个游戏，否则它对你没有意义。

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

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

  1. 在 Nim 中，单堆的长度就是那堆的大小。
  2. 如果我们有一个 2 堆游戏，则位置的数目是两堆大小的异或。（您需要进行双重归纳。）
  3. 如果我们把这组桩一分为二，那么整个位置的位数就是这两个子集的位数的异或。

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

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

于 2014-09-04T16:36:37.317 回答
0

对我来说，是这样的：

  1. 了解 Nim，以及该策略为何有效
  2. 了解 Poker Nim，以及为什么策略是相同的
  3. 了解为什么 mex 是重要的数字

Poker Nim 就像 Nim 一样，除了玩家握住他们移除的“硬币”，轮到他们时，他们可以将任意正数的硬币从一堆硬币移到手中，或者将任意正数的硬币移到手中。硬币从他们的手到一叠。

最初，这感觉非常不同。游戏甚至可以进行无限多步！但如果鲍勃和爱丽丝玩得很努力，这不会发生。假设 Bob 查看筹码，发现如果他们玩 Nim 而不是 Poker Nim，他会有一个获胜策略。他可以将该策略应用于 Nim，如下所示：如果 Alice 将硬币从桌子上拿走，他就好像他在玩 Nim；如果爱丽丝将硬币放在桌子上，他会立即取出她刚刚放置的硬币。由于她手中只能有有限多的硬币，她只能在有限的时间内停止多次，然后才被迫让她输掉的 Nim 移动。

在 Poker Nim 中，如果我手头有 5 个硬币并且我查看一叠 3 个硬币，我可以在移动时将其更改为任何有 0、1、2、4、5、6、7 或 8 个硬币。我不能做的就是把它留在mex，也就是3。如果我把它往下移，我就是在玩Nim。我将它向上移动，您可以立即将其反转回 3，我面临着与我相同的情况，只是现在我手头的硬币少于 5 个。

这就是 Poker Nim，以及 mex 如何变得相关的本质。高于 mex 的移动是可逆的，因此永远不能将失败的位置变成获胜的位置。超越墨西哥永远不会有帮助。除非你试图压倒对手的计算能力，否则就是这样。

于 2014-12-24T16:23:49.750 回答