Question

问题在于按照这些规则在游戏的每一时刻选择最佳选择:

你们只能拿到最左边或最右心。
你们的反对者将首先从左边或最右心中选择最高卡。如果它有tie,它就将取胜。考虑到这一点并不总是最佳选择。

有时是无法赢得胜利的,但是,你必须显示,通过打击这种反对者,你能够增加最大的距离(或说是战略)。

例:

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

在此,我选择了第二次,而不是4次,因此,我可以在8次发言。因此,选择最高卡并不总是最佳的。

I ve been trying to implement this solution using recursion but I m not sure it s the best option. Any ideas on how to design this algorithm?

[EDIT] Thanks to @PengOne for it s generous help. This is the code im trying to implement, but unfortunately it s giving me errors. What should I fix in it? I m editing this as I progress.

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为卡片阵列。 ∗∗∗∗∗ B 是你的反对者总卡。 <代码>S = A-B为游戏价值。如果<代码>S>0,如果失去<代码>S<0和,请打上<>。 S=0。

The easiest is to make two moves at once, your move followed by the opponent s determined move. There are two base cases to consider:

如果length(D) = 0, 返回S。游戏已经结束。
If length(D) == 1, return S + D[0]. You choose the remaining card, and the game ends.

在<代码>length(D) > 1时,对两种可能性进行评估。

Let L be the result of the game if you choose the left card followed by the opponent doing his deterministic move, i.e.

L = D[0] - max(D[...],D[N-1]+kaGameValue(newD)
Let R be the result of the game if you choose the right card followed by the opponent doing his deterministic move, i.e.

R = D[N-1] - max(D[0],D[N-2]) + cardGameValue(newD)

Choose the play corresponding to the larger number, i.e. take D[0] if L>=R, otherwise take D[N-1]. Here N = length(D).

Answer 2

请参看Min-Max Algorithm , 可能的话,可在上查阅。甲型六氯环己烷

Min-Max认为,你的反对者将永远选择自己的最佳选择,因此,你可以选择每一种可能的设想,以找到最佳选择,从而导致你对你们的反对。 “因此,鉴于我举动x,我的反对者将采取行动,然后,我就要走......”等一切办法结束游戏。因此,你可以决定谁将获胜。

阿尔法-贝塔管道类似,它审视了可能的情景,但它确定,一个可能的情景清单是否将产生一个获胜的结果。如果你知道,如果你做“移动X”的话,那么你将永远不会松散,那么你就不需要花更多的时间来研究“移动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;
            }
        }
    }

友情链接