algorithm - Nim 的另一个游戏变体

Question

给定N个二进制序列

例子: 给定一个序列 101001 表示

玩家 0 只能选择一个元素为 0 的位置，并从该位置移除序列，结果{如果他选择第二个元素则为 1 或如果他选择第四个元素则为 101 或如果他选择第五个元素则为 1010}

玩家 1 只能选择一个有 1 个元素的位置，然后从该位置移除序列结果{如果他选择第一个元素则为 null 或如果他选择第三个元素则为 10 或如果他选择第 6 个元素则为 10100}

现在玩家 0 和玩家 1 轮流减少 N 个序列，每轮他们选择一个序列，选择一个元素并从该位置移除所选序列的末尾，如果玩家不能移动，他输了。

假设双方都发挥最佳，谁会赢？

我试图用 grundy 解决这个问题，但我无法将序列减少到 grundy 数字，因为这两个玩家没有相同的移动选项。谁能给我一个解决这个问题的提示？

顺便说一句，抱歉我的英语不好

Answer 1

这不是尼姆。这是Blue-red Hackenbush的游戏.甚至还有一个 online hackenbush calculator这可以解决这个特定的情况(只需将 B 和 R 更改为 0 和 1)，以及对算法的简短解释:

Until a color change, each segment is worth +1 or -1 (depending on whether it is Blue or Red, respectively). Once a color change occurs, each subsequent segment (regardless of color), is worth half of the previous segment, with a +/- corresponding to the color. Thus, the string BBRB would be worth +1+1-1/2+1/4=7/4.

因此您可以计算每个序列的值。 (假设玩家 0 被分配到正面，即“0”的计算结果为 +1。)如果所有序列中这些值的总和为正，则玩家 0 获胜。如果为负，玩家 1 获胜。如果它是 0，那么谁先走就输。