尼姆变异游戏的策略- StoneGameStrategist - SRM 309

Question

我对博弈论相当陌生，并且只理解正常的尼姆游戏，在这种游戏中，你用、无条件和最后一个移除胜利的玩家从堆中移除石头。但是在阅读Topcoder博弈论教程时，我遇到了一个很好的问题。要点如下：

你和一个朋友在玩一个游戏，你轮流从堆里搬石头。最初，每一堆至少有与左边的堆一样多的石头。此属性必须在整个游戏过程中维护。每次转弯时，你都会从一堆石头中取出一颗或多块石头。你和你的朋友轮流转，直到不再可能采取有效的行动。最后一个移动的球员赢得了这场比赛。注意，如果你把所有的石头从一堆，它仍然被认为是一堆。据说你已经做了一个“胜利的一步”，如果在采取这一行动后，你最终可以赢，无论你的朋友做什么。您将得到一个int[]桩，表示从左到右的每一堆石头的数量。该你行动了。找到一个获胜的移动，并将其返回为一个字符串格式为“采取s石头从桩k”(引号仅为清晰)，其中s和k(一个0的索引)是每个整数没有前导零。如果有多个获胜的动作，选择一个最小化的移动。如果仍然有一个平分，选择一个最小化k。如果没有获胜的移动是可能的，返回字符串“你输”(引号仅为清晰)。

移除这里的石头有一个条件，你需要保持整体的不递减顺序，这正成为我想出一个逻辑的障碍。为此，我试着阅读社论，但不幸的是，我无法理解它背后的想法。有谁能用一个更简单的术语来解释这个解决方案吗？

Answer 1

这篇社论并没有解释如何解决尼姆最初的游戏，而只是提供了一个指向维基百科页面的链接(在那里可以找到解决方案)。

这篇社论只是解释了如何将Topcoder问题映射到Nim的常规游戏：

首先，可以将游戏转换为原桩之间存在差异的游戏(因此，3 6 6的例子变成了3 3 0)。

然后，桩的顺序被颠倒(因此例子变成0 3 3)。

然后，这个新游戏中的移动变成了一个两步的过程:从一堆中移除石头，并将其添加到前一堆中(在示例中，获胜的移动从最后一步取3，并将它们添加到中间一堆，变为0 6 0)。

然后，如果你只看奇数堆(#1，#3，#5，等等)，你就会得到Nim的规则游戏，并且可以在上面应用一个有文档的算法(所以03-3和Nim的位置是0)。

因此，对此的解释是：

• 在奇数堆上的任何移动都变成了尼姆正常游戏中的一个动作；
• 在偶数堆上的任何移动都可以通过将相同数量的石头从接收到的奇数堆移动到下一个偶数堆(因此，同样的失败位置可以再次施加到玩家身上)。

​