硬币游戏的最优策略

考虑一行n个值为v1，v2 .......，vn的硬币。我们通过轮流对抗对手进行比赛。在每一回合中，玩家从行中选择第一枚硬币或最后一枚硬币，永久移除它，并接收硬币的价值。如果我们先行动，确定可能赢得的最大可能的金额。硬币游戏的最优策略

我的解决方案

既然我们先走了，我们既可以选择V1和V2，然后我们的对手可以从一开始或从一开始就挑。因此可能出现四个子问题。

（1,1），（1,2），（2,1），（2,2）

其中（1,1）是指，我是从开始挑[即1]并且对手也从开始选择[即1]。（1,2）表示我从开始选择，但对手选择最后一个。

因此，如果M(i,j)是我可以选择的最大值（i，j），则表示（i，j）为递归函数。

M(i,j) = Max{ Max{ M(i+2,j), M(i+1,j-1) } + vi, Max{ M(i+1,j-1), M(i,j-2) } + vj }

说明：当我有i..j元件，那么我可以选择第一个第[i + 1]，并且是，我的对手可以选择或者第一第[i + 2]或最后一个[j-1]，并且我希望在下次挑选时拥有最大数量，因此是外部最大值内的第一项。

第二个与上面类似，即如果我选择最后一个[j-1]，对手选择第一个[i + 1]或者最后一个[j-2]，我下次将其最大化。

现在，我在书里看到了递归作为

M(i,j) = Max{ Min{ Same } + vi, Min{ Same } + vj }

现在，为什么我在这里降到最低。这不等于说我第一次选择最大化，但是我必须选择第二次选择最小化。

我在做什么错？谢谢。

来源

2013-08-01 Kraken

如果要计算，你可以肯定取胜，你必须假设你的对手是试图最大限度地发挥他/她自己的结果，这相当于减少你（因为总和的金额你的收益总是等于v1 + ... + vn）。你的公式计算的是如果你的对手总是从他/她的角度来看错误的话，你会赢得什么。

来源

2013-08-01 08:45:51 Virgile

所以基本上我在计算的是什么是我可以赢得的最大。但我需要找到我能赢的最低最高点。对？ – Kraken

是的，这就是要点。 – Virgile

如果硬币的编号为n是偶数，第一个玩家可以保证自己最大的v1 + v3 + ... + v（n-1）和v2 + v4 + ... + vn。找出哪个最大，然后采取v1或vn。此后，只需将原来分别位于奇数位置或偶数位置的硬币取出。这是可能的，因为无论第二位球员做什么，当第一位球员再次移动时，奇数位置和偶数位置的硬币都会暴露。

这是最好的第一个球员能做的吗？首先玩家可以在任何移动中从“赔率”切换到“平均值”，具体取决于“新赔率”的总和是大于还是小于“新赔率”的总和。第二个球员的策略应该是保持尽可能低的转换动机，即选择最大的硬币（第一个或最后一个位置）。由此产生的位置仍然诱惑第一位玩家转换？是的，我们通过下面的游戏中看到：

1 3 19 6 8 20

第一个球员加上1 + 19 + 8 = 28和3 + 6 + 20 = 29，他可以通过挑选找齐保证至少29的总得分， 20.结果是

1 3 19 6 8

为了减少第一玩家的诱惑从找齐切换到赔率和做甚至比29的总成绩，第二玩家需要8.

1 3 19 6

然而，诱惑依然存在。事实上，赔率位置的总和是1 + 19 = 20，平均值总和只有3 + 6 = 9，所以第一名玩家现在可以通过切换赔率做得更好，并且取1，尽管6更大。

3 19 6

最好第二玩家所能做的是挑选6，第一玩家得到19，第二玩家得到3.总得分：第一玩家20 + 1 + 19 = 40，第二玩家8 + 6 + 3 = 17

看起来第一个玩家总是能以这种方式获得比第二个玩家更多的东西。但是，我们仍然不知道这是否是第一位球员的最佳策略。

在另一方面，如果硬币的数目n是奇数，第一玩家和上述分析第二玩家的角色基本上相反。

现在问题变成了，上面列出的贪婪策略是否真的是最优？我们可以通过检查二元决策树来检查特定情况，其中第一个玩家取第一个或最后一个硬币，然后第二个玩家取第一个或最后一个剩下的硬币等等。树中会有2^n树叶;可以计算每个叶子的得分，然后从叶子到根的工作，每个较高节点的值可以计算为两个孩子的最大值或两个孩子的最小值，具体取决于它们是谁。

而是明确构建树，可以隐含递归函数调用，这将节省所需的总内存，但不会节省时间建成。

如果有人分析这样的比赛，并与我的不同的优化策略来了，我很希望看到它。

来源

2015-04-27 05:21:42

http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

本页面给出了问题的一个非常明确的解释，也是解决方案。它的结论是：

 
F(i, j) represents the maximum value the user can collect from 
     i'th coin to j'th coin. 

    F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1)), 
        Vj + min(F(i+1, j-1), F(i, j-2))) 
Base Cases 
    F(i, j) = Vi   If j == i 
    F(i, j) = max(Vi, Vj) If j == i+1

来源

2016-06-18 03:50:54 WZL

的“最小化”那里，因为每个人都希望尽量减少硬币的对手的总价值发生。所以，你应该假设你的组件已经采取哪些最小化后的总价值，当轮到你来选择下一个硬币的策略。 – WZL

硬币游戏的最优策略

回答

相关问题