1

我对博弈论相当陌生，并且只了解正常的 nim 游戏，您可以在没有条件的情况下从堆中移除石头，最后一个移除的玩家获胜。但后来我在阅读Topcoder 上的博弈论教程时遇到了一个很好的问题。要点如下：

你和一个朋友正在玩一个游戏，你轮流从一堆石头中取出石头。最初，每一堆的石头至少与其左边的那堆一样多。在整个游戏过程中必须保持此属性。每回合，你从一堆石头中取出一块或多块石头。您和您的朋友交替轮流，直到无法再进行有效的移动。最后一个采取行动的玩家赢得了比赛。请注意，如果您从一堆石头中取出所有石头，它仍然被视为一堆。如果在采取行动之后，无论您的朋友做什么，您最终都可以获胜，那么您就被称为“获胜的行动”。你得到一个 int[] 堆，代表从左到右每堆中的石头数量。轮到你搬家了。找到一个获胜的举动并将其作为格式为“TAKE s STONES FROM PILE k”的字符串返回 （仅为清晰起见引用），其中 s 和 k（从 0 开始的索引）都是不带前导零的整数。如果有多个获胜动作，请选择最小化 s 的一个。如果仍然存在平局，则选择使 k 最小的那个。如果不可能获胜，则返回字符串“YOU LOSE”（仅为清楚起见而引用）。

这里的去石有一个条件，就是要保持整体的非递减顺序，这成为了我想出一个逻辑的障碍。为此，我尝试阅读社论，但不幸的是无法理解其背后的想法。谁能用更简单的术语解释解决方案？

4

1 回答 1

0

社论没有说明如何解决 Nim 的原始游戏，而只是提供了维基百科页面的链接（可以找到解决方案）。

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

首先，可以将游戏转换为堆与原始堆之间存在差异的游戏（因此 3 6 6 示例变为 3 3 0）。

然后将堆的顺序颠倒（因此示例变为 0 3 3）。

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

然后，如果您只查看奇数堆（#1、#3、#5 等），您会得到 Nim 的常规游戏，并且可以在其上应用记录在案的算法（因此 0 3 3 与Nim 位置为 0 3)。

因此，给出的解释是：

  • 奇数堆上的任何移动都变得就像正常的 Nim 游戏中的移动一样；
  • 只需将相同数量的棋子从接收的奇数堆移到下一个偶数堆，就可以否定偶数堆上的任何移动（因此可以再次将相同的失败位置强加给玩家）。

    • 于 2017-11-18T20:04:30.540 回答