algorithm - 2人游戏的最优策略

Question

• 2 位玩家 A 和 B 正在玩一个涉及数字n的游戏
• 玩家 A 迈出第一步，双方轮流下棋。
• 在每次移动中，玩家取数 n，选择一个数 i 使得 2^i < n 并将 n 替换为 < em>k = n - 2^i 当且仅当 k 的二进制表示中 1 的个数大于或等于 n 的二进制表示中 1 的个数
• 当没有玩家可以移动时游戏结束，即不存在这样的 i

例如:

n = 13 = b1101

只有 i=1 可能

k = n - 2^i = 11 = b1011

同样，只有 i = 2 可能

k = n - 2^i = 7 = b111

由于玩家A不能再移动，玩家B获胜

我推断，在任何一步，我们只能选择一个i，使得n的二进制表示中相应位置有一个0。

例如: 如果n=1010010，那么i只能是{0,2,3,5}。

但我不能再进一步了。minimax 算法并没有完全打动我。如果有任何帮助，我将不胜感激。提前致谢

Answer 1

假设n不是太大，我们可以用动态规划来解决这个问题。 定义一个数组 A[1:n]，其中 A[i] 表示玩家 i 是否会在输入 i 上获胜。 让我们使用解释:

   A[i] = 1, if A wins on input i,
   A[i] = 0, if A loses on input i.

现在 A 可以自底向上计算如下:

A[1] = 0, A[2] = 1.
For j=3:n { 
      Assign A[j] = 1 if there exists a number i such that (A[j-2^i] = 0) AND 
                              (number of 1's in i >=  number of 1's in j)
      Otherwise  Assign A[j] = 0 
}