Nim Game 变化的递归关系

Question

我正在努力获得最佳子结构来解决问题，即必须遵循的循环以及可以构建动态编程解决方案以优化时间复杂度的方法。

假设A和B有2种石头。有第一种石头A和第二种石头B 类型。他们决定根据规则进行游戏，例如在每一轮中可以完成以下有效动作之一：

选择一些第一种石头
选一些第二种石头
两种类型的石头数量相等

他们必须在每一回合中至少挑选一块石头。谁走最后一步，谁就赢得了比赛。两者都发挥最佳。然而，在告诉比赛规则时，爱丽丝作弊以决定谁先走来确保她赢得比赛。

给定石头，确定爱丽丝是否走第一步。

Answer 1

您可以从获胜位置向后工作。

如果所有剩余的棋子都是第一种或第二种，或者如果每种类型的棋子数量相等，则轮到的玩家获胜 - 拾取所有剩余的棋子。
在任何其他位置，轮到的玩家可以将第一种或第二种类型的子数减少一个或更多，或者可以将两种类型的子数减少一个或更多。如果所有结果头寸都赢了，这个头寸就输了。如果至少有一个结果的位置是输的，玩家可以选择那个，所以这个位置是赢的。

更正式地说，对于具有 A 个第一种类型的棋子和 B 个第二种类型的棋子的游戏，创建一个 table N[A+1, B+1] 个布尔值，其中true代表赢，false代表输。

然后像这样填写table：

for (a = 0; a <= A; a++) {
  for (b = 0; <= B; b++) {
    if (a == 0 || b == 0 || a == b) {
      // case 1, always winning
      N[a, b] = true;
    } else {
      // case 2, winning if there is a losing position reachable
      if (
        there is an 1 <= i <= a, such that N[a-i, b] is false
        OR there is an 1 <= i <= b, such that N[a, b-i] is false
        OR there is an 1 <= i <= min(a, b), such that N[a-i, b-i] is false
      ) {
        N[a, b] = true;
      } else {
        N[a, b] = false;
      }
    } 
  }
}

填充 table 后，如果 N[A, B] 为真，Alice 应该开始，否则让 Bob 开始。

Answer 2

将此作为单独的答案发布，因为它与其他答案截然不同。我也会留下那个答案，因为这种技术对于类似的问题可能不是很有用。

以运行为例，手工各10颗石子，我发现唯一亏损的位置是(1, 2), (3, 5), (4, 7), (6, 10)。有一个整数序列搜索引擎，可以在其中搜索给定序列开头的已知公式，称为 OEIS

所以有序列A072061，与这个匹配。这教会了我们两件事：

这是一个已知问题，该游戏通常被称为 Wythoff's game
所有亏损头寸均由公式 (a(2*k), a(2*k+1)) 给出某个整数 k 和 a(n) = n*(1+(-1)^n)/4+floor((2*n+1-(-1)^n)*(1+sqrt(5))/8)

因此，要确定 Alice 是否应该开始，您可以使用给定的公式计算 (A, B) 是否为亏损头寸。

Nim Game 变化的递归关系

Recurrence relation for variation of Nim Game

algorithm

game-theory

dynamic-programming

data-structures