C#中卡牌游戏中最佳卡牌选择

Question

问题在于在游戏的每个时刻选择最佳选项，遵循以下规则：

• 您只能选择最左边或最右边的卡片。
• 您的对手将始终先行动，并且始终选择最左边或最右边的卡片中最高的一张。如果出现平局，则会选择最右边的卡片。请注意，这并不总是最佳选择。

有时无法获胜，但您必须仍然展示您可以通过针对该对手（或策略）进行比赛而添加的最高金额。

例子：

Cards:    1 2 4 2 8 4 3
Opponent: 3 4 2 2 = 11
Me:       1 8 4 = 13

在第二轮中，我选择了1而不是4，因此稍后就可以选择8。这就是为什么选择最高牌并不总是最佳选择的原因。

我一直在尝试使用递归来实现这个解决方案，但我不确定这是否是最佳选择。有没有关于如何设计该算法的想法？

[编辑] 感谢@PengOne的慷慨帮助。这是我正在尝试实现的代码，但不幸的是它给我报错。我应该怎么修复它？随着我的进展，我会进行编辑。

static int cardGameValue(List<int> D, int myScore, int opponentScore)
{
    if (D.Count == 0) return myScore;
    else
    {
        if (D[0] <= D[D.Count - 1])
        {
            opponentScore += D[D.Count - 1];
            D.RemoveAt(D.Count - 1);
        }
        else
        {
            opponentScore += D[0];
            D.RemoveAt(0);
        }

        int left = cardGameValue(
                new List<int>(D.GetRange(1, D.Count - 1)),
                myScore + D[0],
                opponentScore);

        int right = cardGameValue(
                new List<int>(D.Take(D.Count - 2)),
                myScore + D[D.Count - 1],
                opponentScore);

        if (left >= right)
        { return left; }
        else
        { return right; }
    }
}

- Jean Carlos Suárez Marranzini

---

游戏怎么赢？你告诉了我们规则，但没有说明目标。 - PengOne

这是一项学校/大学任务吗？ - lahsrah

对手：3 4 2 2 他首先选择了3（因为他总是选择最高的），然后我选了1，他选了4，我选了8，然后他选了2，接着我选了4，他选了2。 - Jean Carlos Suárez Marranzini

任何玩家只能选择最左边或最右边的卡牌。 - Jean Carlos Suárez Marranzini

我一直在试图覆盖我选择的任何可能结果。但总是出现一些问题。我的代码太长且硬编码，实际上无法显示。 - Jean Carlos Suárez Marranzini

Answer 1

从最简单的情况使用递归构建解决方案。

让 D 成为卡牌数组。让 A 成为你的卡牌总数，B 成为对手的卡牌总数。将 S = A-B 设置为游戏价值。如果 S>0，则你赢了；如果 S<0，则你输了；如果 S==0，则平局。

最简单的方法是一次性进行两个操作，先是你的操作，然后是对手的确定性操作。有两种基本情况需要考虑：

- 如果 length(D) == 0，则返回 S。游戏已经结束。 - 如果 length(D) == 1，则返回 S + D[0]。你选择剩下的牌，游戏结束。

对于递归情况，当 length(D) > 1 时，评估以下两种可能性：

- 如果你选择左卡牌，然后对手做出他的确定性举动，则 L 是游戏结果，即：L = D[0] - max(D[1],D[N-1]) + cardGameValue(newD) - 如果你选择右卡牌，然后对手做出他的确定性举动，则 R 是游戏结果，即：R = D[N-1] - max(D[0],D[N-2]) + cardGameValue(newD) 选择相应数字的操作，如果 L>=R，则取 D[0]，否则取 D[N-1]。这里 N = length(D)。

- PengOne

---

感谢您的帮助。我已经尽力了，实际上根据解释发布了我正在尝试制作的算法。它还有什么问题吗？ - Jean Carlos Suárez Marranzini

我仍在更新代码，希望每次都能让它变得更好。 - Jean Carlos Suárez Marranzini

Answer 2

你应该查看 极小化极大算法，可能需要使用Alpha-Beta剪枝。

极小化极大算法认为你的对手总是会选择最好的选择，因此你可以运行每种可能的情况来发现能够打败对手的最佳选择。例如，“如果我采取行动x，我的对手将采取行动y，然后我会采取...”等等，一直到游戏结束。因此，你可以确定谁将获胜。

Alpha-Beta剪枝类似于极小化极大算法，它查看可能的情况，但它确定了一系列可能的情况是否会产生获胜的结果。如果你知道如果你采取“行动x”，那么无论如何你都会输，你就不需要再花时间去看“行动x然后行动y”了。你可以从“行动x”开始“剪枝”整个选择分支，因为你知道它永远不会有帮助。

- jb.

---

由于状态空间很小，他甚至不需要修剪。 - Amir Afghani

@AmirAfghani，你很可能是完全正确的，但如果我不提一下，我就对他不公了。 - jb.

当你被迫在某个时刻使用启发式方法，因为完整的前瞻成本太高时，极小化算法才真正有意义。如果起始列表有60个数字，那么对于这个游戏来说可能是正确的。 - Rafe

当你被迫在某个时刻使用启发式算法，因为完整的前瞻成本太高时，极小化算法才真正有意义。如果起始列表有60个数字，那么对于这个游戏来说，这可能是正确的。 - Rafe

我认为极小化极大算法更有意义，不仅仅是有意义。他可以通过极小化极大算法进行全面搜索并得到最佳答案。 - Amir Afghani

我同意，极小化算法将让他查看所有选择并找出答案。如果搜索空间较小，则速度会更快。 - jb.

Answer 3

这是最终起作用的代码。感谢大家的支持。

    static int cardGameValue(List<int> D, int myScore, int opponentScore)
    {
        if (D.Count == 0) return myScore;
        else if (D.Count == 1)
        {
            opponentScore += D[0];
            return myScore;
        }
        else
        {
            if (D[0] <= D[D.Count - 1])
            {
                opponentScore += D[D.Count - 1];
                D.RemoveAt(D.Count - 1);
            }
            else
            {
                opponentScore += D[0];
                D.RemoveAt(0);
            }

            int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore);

            int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore);

            if (left >= right)
            {
                return left;
            }
            else
            {
                return right;
            }
        }
    }

- Jean Carlos Suárez Marranzini

---

我认为你想让 opponentScore 成为一个引用参数。否则，当你更新它的值时，你并没有保存结果。 - jb.