卡牌游戏算法

Question

我被要求用C语言开发一个卡牌游戏，两名玩家可以从一组牌中选择最左边或最右边的牌，例如： 如果列表是：[2,14,12,6,20,10]，玩家可以选择2或10。 最终，得分更高的玩家（由玩家选择的牌的总和）赢得比赛。 是否有一种方法来优化玩家的选择，知道并不总是最佳选择是最大值（例如，在上述情况下选择10会给另一位玩家选择20的机会）。 （听起来像是一个递归函数...）

- Ahmad Aboud

---

例如，看一下Alpha-beta剪枝算法。 - Matej

我相信这个问题可以通过动态规划高效地解决。你只需要为给定子列表创建一个递归表达式，以获得最大的回报。从该表达式中，您将计算一个矩阵，其中条目[i，j]包含从i开始到j结束的子列表的最大结果。(应该是O(n^2)，而不是朴素的穷举搜索，它可能是O(2^n)) - aioobe

Answer 1

我不知道最大化的问题。但是如果（在开始时）有偶数张卡牌，对于第一个玩家来说，有一个简单的算法：

首先，用红色和黑色交替标记卡牌，这样边缘的卡牌就会有不同的颜色。分别计算黑色卡牌和红色卡牌的总和，并选择你喜欢的颜色。假设（例如）黑色卡牌的总和更高，则继续选择黑色卡牌，你的对手将不得不选择红色卡牌-而你将获胜！

- asaelr

Answer 2

在给定的游戏中玩得最好，玩家将获得一些分数。设输入为列表L，并定义F(i,l)和S(i,l)为从第i个元素开始长度为l的列表部分中第一个和第二个玩家的得分。如果（部分）列表的长度为1，则该卡片将由第一个玩家获得。

F(i,1) = L[i]
S(i,1) = 0

如果（部分）列表比第一个玩家想要的更长，他想要最大化选择的卡片和剩下的列表中第二个玩家会得到的内容。

F(i,l) = max( L[i] + S(i+1,l-1), L[i+l-1] + S(i,l-1) )

由于第二个玩家没有选择卡片，他将得到第一个玩家在较短列表中所得到的东西。

S(i,l) = F(i+1,l-1) if L[i] + S(i+1,l-1) >= L[i+l-1] + S(i,l-1), or
         F(i,l-1)   if L[i] + S(i+1,l-1) < L[i+l-1] + S(i,l-1).

实现是通过填充两个n^2数组F和S来完成的。结果是F(1, length(L))。

- Ante

Answer 3

我们在编程课程中做了这个练习，这是我想出来的解决方案（用c++编写，但很容易转换为c）。它使用O(n^2)时间和O(n)空间的动态规划。首先计算每个长度为1的子列表的最佳游戏得分，然后使用它们来计算长度为2的列表的得分，以此类推。最后有两个长度为n-1的列表，我们选择给出更好总体得分的那一个。

int f(const vector<int>& numbers) // return 0 if left is optimal pick, 1 if right 
{
    vector<int> s(numbers);

    for(size_t len = 1; len < numbers.size() - 1; ++len)
        for(size_t i = 0; i < numbers.size() - len; ++i)
            s[i] = max(numbers[i] - s[i + 1], numbers[i + len] - s[i]);

    return numbers.front() - s[1] < numbers.back() - s[0];
}

- Timo

Answer 4

@asaelr 的答案简单易懂，是这个问题的一个非常好的技巧。 然而，这种解决方案只能确保第一个玩家不输，不能确保他比对手赚更多的分数。如果我们想要得到最优解，就必须使用DP。 例如： { 3, 2, 2, 3, 1, 2 }，通过使用这个技巧，我们可以赢得2个点，但是通过使用DP，我们可以赢得3个点。 详细的解释可以在这里找到。真的是一篇很好的文章。 http://articles.leetcode.com/coins-in-line/

- lpcclown