4

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

  • 您只能选择最左边或最右边的卡片。

  • 你的对手总是先选择，并且总是从最左边或最右边的牌中选择最高的牌。如果是平局，它将选择最右边的。考虑到这并不总是最好的选择。

有时不可能赢，但无论如何你必须展示你可以通过与这个对手比赛（或策略，比方说）来增加的最高金额。

例子：

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

3 回答 3

4

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

让我们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]if L>=R，否则取D[N-1]。在这里N = length(D)。

于 2012-01-12T06:17:08.777 回答
3

你应该看看Min-Max Algorithm，可能使用Alpha-Beta pruning

Min-Max 是您的对手总是会为自己选择最佳选择的想法，因此您可以运行每个可能的场景来发现可以让您击败对手的最佳选择。“即，如果我采取行动 x，我的对手将采取行动 y，然后我将采取......”等，一直到游戏结束。因此，您可以确定谁将获胜。

Alpha-Beta 剪枝类似，它着眼于可能的场景，但它确定可能的场景列表是否会产生获胜的结果。如果你知道如果你做了“move x”，那么无论如何你总是会松动，你不需要花更多的时间看“move x then move y”。你可以从“move x”中“剪除”整个选择分支，因为你知道它永远不会有帮助。

于 2012-01-12T06:07:27.333 回答
2

这是最终实际工作的代码。感谢大家的支持。

    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;
            }
        }
    }
于 2012-01-13T05:50:40.787 回答