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 = 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)

选择较大数字对应的玩法，即如果D[0]则取L>=R，否则取D[N-1]。这里N = length(D)。