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; }
    }
}

Answer 1

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

令 D 为卡片数组。令 A 为您的牌总数，B 为对手的牌总数。将 S = AB 设置为游戏的值。如果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 = 长度(D)。

Answer 2

您应该查看最小-最大算法，可能使用Alpha-Beta 剪枝

最小-最大是指你的对手总是会为自己选择最好的选择，因此你可以运行每一个可能的选择场景来发现最佳选择将会导致你击败对手。 “即，假设我采取 x 步，我的对手将采取 y 步，然后我将采取......”等等，一直到游戏结束。因此，您可以决定谁会获胜。

Alpha-Beta 剪枝与此类似，它着眼于可能的场景，但它确定一系列可能的场景是否会产生获胜的结果。如果你知道如果你“移动x”那么无论如何你都会失败，你就不需要花更多的时间看“移动x然后移动y”。您可以从“移动 x”中“修剪”整个选择分支，因为您知道它永远不会有帮助。

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;
            }
        }
    }