Stone Nim游戏说明
Explanation on Stone Nim Game
我正在做一个编码问题，我以某种方式通过了所有测试用例，但我不明白到底发生了什么。问题是经典 nim 游戏的一个小转折：
There are two players A and B. There are N piles of various stones. Each player can take any amount of stones if the pile is less than K, otherwise they must take a multiple of K stones. The last person to take stones wins.
python
# solution -> will A win the game of piles, k?
def solution(piles, k):
gn = 0 # Grundy number
for pile in piles:
if pile % 2 != 0:
gn ^= pile + 1
else:
gn ^= pile - 1
return gn != 0
我不确定是否有足够的测试用例，但 k 甚至没有在这里使用。老实说，我什至很难理解 gn（Grundy 数字）的真正含义。我知道如果所有堆的异或不为零，就有赢得 Nim 游戏的证据，但我真的不明白为什么这种变化需要检查堆的奇偶校验。
首先，给出的解是不正确的。您注意到它没有使用 k，这确实是一个大危险信号。您还可以查看它给出的单堆游戏的结果，其中似乎说只有当堆的大小是您应该很快能够证明不正确的大小时，玩家 A 才会获胜。
虽然答案的结构有点正确。 Grundy 数的强大之处在于，组合游戏状态的 Grundy 数是各个游戏状态的 Grundy 数的 nim 和（在有限序数的情况下为 XOR）。 （这只适用于一种非常特殊的组合游戏状态的方式，但事实证明这是考虑 Nim 堆在一起的自然方式。）所以，这个问题确实可以通过找到每堆的 Grundy 数来解决（考虑 k) 和 XOR-ing 将它们放在一起以获得完整游戏状态的 Grundy 编号。 （在 Nim 中，你可以从一堆石头中取出任意数量的石头，并通过拿走最后一颗石头获胜，一堆的 Grundy 数就是一堆的大小。这就是为什么那个版本的 Nim 的解决方案只是 XOR-s 桩的大小。）
因此，将理论视为理所当然，您可以通过为给定 k 的单个桩找到正确的 Grundy 值来解决问题。你只需要考虑一堆游戏就可以做到这一点。这实际上是一个非常经典的问题，IMO 比 multi-pile Nim 更容易正确分析。你应该试一试。
至于如何理解 Grundy 数字，有很多地方可以阅读，但这是我的方法。需要理解的是，为什么两种游戏状态的组合允许前玩家 (B) 在 Grundy 数字相等时准确获胜。
为此，我们只需要考虑移动对两个州的 Grundy 数有什么影响。
根据定义为后继状态的最小排除值，总是有一个移动将状态的 Grundy 数更改为任何较低的值（即 n 可以从 0 变成任何数字最多 n - 1)。从来没有一个动作能让 Grundy 号码保持不变。可能有也可能没有增加 Grundy 数的动作。
那么，对于两个相同Grundy数的状态组合的情况，玩家B可以利用"copycat strategy"获胜。如果玩家 A 采取了减少一个状态的 Grundy 数的移动，则玩家 B 可以 "copy" 通过将另一个状态的 Grundy 数减少到相同的值。如果玩家 A 移动增加了一个状态的 Grundy 数，玩家 B 可以 "undo" 通过在相同状态下移动将其减少到与之前相同的值。 （我们的游戏是有限的，所以我们不必担心做和撤消的无限循环。）这些是 A 唯一能做的事情。 （请记住，重要的是，没有任何移动可以使 Grundy 数字保持不变。）
如果各州没有相同的格兰迪号码，那么先手获胜的方式就很明确；他们只是减少了具有较高值的状态的数量以匹配具有较低值的状态。这减少了以前的情况。
这里我们应该注意，最小排除值定义允许我们根据任何状态的后继递归地构造 Grundy 数（至少对于有限游戏）。没有选择，所以这些数字实际上是 well-defined.
下一个要解决的问题是为什么我们可以计算组合状态的 Grundy 数。我不想在这里完全考虑 XOR。我们可以纯粹从最小排除值 属性 来定义这个 nim sum 操作。我们抽象地认为nim_sum(x, y)的后继者是{nim_sum(k, y) for k in 0..x-1}和{nim_sum(x, k) for k in 0..y-1}；换句话说，在一个 sub-state 或另一个上移动。 （我们可以忽略增加 Grundy 数的 sub-state 之一的后继者，因为这样的状态将拥有原始状态的所有后继者加上 nim_sum(x, y) 本身作为另一个后继者，所以它必须有一个严格更大的 Grundy 数。是的，有点 hand-wavy。）这与 XOR 相同。我对此没有特别好的解释，但我觉得这对于基本理解来说并不是必需的。重要的是它是一个well-defined操作。
我正在做一个编码问题，我以某种方式通过了所有测试用例，但我不明白到底发生了什么。问题是经典 nim 游戏的一个小转折：
There are two players A and B. There are N piles of various stones. Each player can take any amount of stones if the pile is less than K, otherwise they must take a multiple of K stones. The last person to take stones wins.
python
# solution -> will A win the game of piles, k?
def solution(piles, k):
gn = 0 # Grundy number
for pile in piles:
if pile % 2 != 0:
gn ^= pile + 1
else:
gn ^= pile - 1
return gn != 0
我不确定是否有足够的测试用例，但 k 甚至没有在这里使用。老实说，我什至很难理解 gn（Grundy 数字）的真正含义。我知道如果所有堆的异或不为零，就有赢得 Nim 游戏的证据，但我真的不明白为什么这种变化需要检查堆的奇偶校验。
首先，给出的解是不正确的。您注意到它没有使用 k，这确实是一个大危险信号。您还可以查看它给出的单堆游戏的结果，其中似乎说只有当堆的大小是您应该很快能够证明不正确的大小时，玩家 A 才会获胜。
虽然答案的结构有点正确。 Grundy 数的强大之处在于，组合游戏状态的 Grundy 数是各个游戏状态的 Grundy 数的 nim 和（在有限序数的情况下为 XOR）。 （这只适用于一种非常特殊的组合游戏状态的方式，但事实证明这是考虑 Nim 堆在一起的自然方式。）所以，这个问题确实可以通过找到每堆的 Grundy 数来解决（考虑 k) 和 XOR-ing 将它们放在一起以获得完整游戏状态的 Grundy 编号。 （在 Nim 中，你可以从一堆石头中取出任意数量的石头，并通过拿走最后一颗石头获胜，一堆的 Grundy 数就是一堆的大小。这就是为什么那个版本的 Nim 的解决方案只是 XOR-s 桩的大小。）
因此，将理论视为理所当然，您可以通过为给定 k 的单个桩找到正确的 Grundy 值来解决问题。你只需要考虑一堆游戏就可以做到这一点。这实际上是一个非常经典的问题，IMO 比 multi-pile Nim 更容易正确分析。你应该试一试。
至于如何理解 Grundy 数字，有很多地方可以阅读，但这是我的方法。需要理解的是，为什么两种游戏状态的组合允许前玩家 (B) 在 Grundy 数字相等时准确获胜。
为此，我们只需要考虑移动对两个州的 Grundy 数有什么影响。
根据定义为后继状态的最小排除值，总是有一个移动将状态的 Grundy 数更改为任何较低的值（即 n 可以从 0 变成任何数字最多 n - 1)。从来没有一个动作能让 Grundy 号码保持不变。可能有也可能没有增加 Grundy 数的动作。
那么，对于两个相同Grundy数的状态组合的情况，玩家B可以利用"copycat strategy"获胜。如果玩家 A 采取了减少一个状态的 Grundy 数的移动，则玩家 B 可以 "copy" 通过将另一个状态的 Grundy 数减少到相同的值。如果玩家 A 移动增加了一个状态的 Grundy 数，玩家 B 可以 "undo" 通过在相同状态下移动将其减少到与之前相同的值。 （我们的游戏是有限的，所以我们不必担心做和撤消的无限循环。）这些是 A 唯一能做的事情。 （请记住，重要的是，没有任何移动可以使 Grundy 数字保持不变。）
如果各州没有相同的格兰迪号码，那么先手获胜的方式就很明确；他们只是减少了具有较高值的状态的数量以匹配具有较低值的状态。这减少了以前的情况。
这里我们应该注意，最小排除值定义允许我们根据任何状态的后继递归地构造 Grundy 数（至少对于有限游戏）。没有选择，所以这些数字实际上是 well-defined.
下一个要解决的问题是为什么我们可以计算组合状态的 Grundy 数。我不想在这里完全考虑 XOR。我们可以纯粹从最小排除值 属性 来定义这个 nim sum 操作。我们抽象地认为nim_sum(x, y)的后继者是{nim_sum(k, y) for k in 0..x-1}和{nim_sum(x, k) for k in 0..y-1}；换句话说，在一个 sub-state 或另一个上移动。 （我们可以忽略增加 Grundy 数的 sub-state 之一的后继者，因为这样的状态将拥有原始状态的所有后继者加上 nim_sum(x, y) 本身作为另一个后继者，所以它必须有一个严格更大的 Grundy 数。是的，有点 hand-wavy。）这与 XOR 相同。我对此没有特别好的解释，但我觉得这对于基本理解来说并不是必需的。重要的是它是一个well-defined操作。