为2人游戏的最佳策略

2玩家一个& B被打涉及多个游戏ň
玩家A使第一招&双方球员发挥交替。
在各移动玩家需要的数量n，选择一个数量我使得2^I <Ñ和替换Ñ与K = N - 2^I当且仅当在1的个数的ķ二进制表示大于或等于1的数量在ñ
游戏的二进制表示结束时没有玩家可以使一动，即不存在这样的我

n = 13 = b1101

唯一可能的I = 1

k = n - 2^i = 11 = b1011

同样，只有可能的I = 2

k = n - 2^i = 7 = b111

由于玩家A不能作出任何更多的动作，播放器B赢

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

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

，但我不能移动任何further.A极大极小算法的心不是正好撞击我，我将不胜感激任何help.Thanks提前

来源

2012-09-24 Leopard

看起来像一个“净息差”的游戏给我。你可以将规则编辑成项目列表吗？ – wildplasser

http://math.stackexchange.com可能会做得更好 – Eric

感谢您的编辑。它更可读。空白也有帮助。（但我似乎还没有把握住它;-) – wildplasser

假设n是不是太大了，我们可以使用动态编程来解决这个问题。定义一个数组A [1：n]，其中A [i]表示玩家是否会赢得输入i。让我们用解释：

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

现在可以计算自下而上如下：

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 
}

来源

2012-09-25 00:07:02 krjampani

如果n变得太大，例如10^9的顺序，那么自顶向下的方法将工作而不是DP方法。 – Leopard

如果n在二进制表示中有多个1，则记忆化的自顶向下方法可能比DP快得多。否则，我猜测DP会更快。运行一些测试看看哪个更好，会很有趣。 – krjampani

为2人游戏的最佳策略

回答

相关问题