点博弈和动态规划

Question

我正在尝试用动态编程解决点游戏的变体。

常规的点游戏是用一排点来玩的。每个玩家在各自的线端获得一或两个点，没有留下任何点的人获胜。

在此版本的游戏中，每个点都有不同的值。每个玩家轮流轮流并在线的两端各取一个点。我想提出一种使用动态编程来找到第一个玩家保证获胜的最大金额的方法。

我在理解这个问题时遇到了问题，并试图为解决方案编写一个重现。任何帮助表示赞赏，谢谢！

Answer 1

看看这个网站：http://people.csail.mit.edu/ bdean/6.046/dp/，特别是问题 10：

游戏的最佳策略。考虑一排 n 个硬币，其值为 v(1) ... v(n)，其中 n 是偶数。我们通过轮流与对手进行游戏。在每个回合中，玩家选择该行中的第一个或最后一个硬币，将其从该行中永久删除，并获得硬币的价值。确定如果我们先行动，我们绝对可以赢得的最大可能金额。

如果我正确阅读您的帖子，这正是您想要的。解决方案非常简单，并且在我看来解释得很好。