c# - 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成为游戏的值(value)。如果 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) .