1

我正在写一篇博文来解释如何使用 Sprague-Grundy 定理来解决各种游戏问题，但我无法理解自己，我们如何定义复合游戏。

这是我到目前为止所得到的：

Sprague grundy theorem，可以用以下几点来概括

  • 公平游戏中的任何位置都可以简化为一个 grundy 数字（或 nimber），其中 grundy 数字 0 是一个失败的位置（也就是说，如果对手完美地发挥，你将永远失败）。

  • 任何位置都可以评估为该位置子节点的最小排他（或 mex）。例如，具有 grundy 值为 0、1、3 的子节点的位置的 grundy 值为 2。具有 grundy 值为 1、2、3 的子节点的位置的 grundy 值为 0。

现在，我想要了解的下一点是，可以将一个位置拆分为复合位置，并将该位置的 grundy 数字评估为这些复合位置的XOR。

例如：对于有两堆的 nim 游戏：

2 xor 1 = 3，因此是一个获胜的位置。

1 xor 1 = 0，因此是一个失败的位置。

我们可以使用mex方法得出这个结论：即。2,1 的子位置是：

1, 1 (0)

2, 0 (2)

0, 1 (1)

墨西哥是 3。

然而，xor 方法的重点是在不必评估子定位的情况下得出这个结论。

我们如何定义这种游戏的复合位置？

4

1 回答 1

0

您所说的“复合位置”是游戏的“（析取）总和”。一个直观的定义是位置的总和是每个玩家可以选择在他们选择的任何组件（“和”）上移动的位置。

像 nim 这样的不偏不倚游戏（可用的移动不取决于玩家，只取决于轮到谁）的精确定义是，如果G和H是位置，那么您可以从G + H移动到的一组位置是集合A和B的并集，其中A是所有g + H的集合（其中g是您可以从G到达的位置），B是所有G + h的集合。

如果您对此材料和相关结果感兴趣，我建议您阅读组合博弈论（CGT），可能在数学堆栈交换上。

于 2016-05-24T01:37:13.020 回答