Лучший выбор карт в карточной игре в C#

Question

Задача состоит в том, чтобы в любой момент игры выбрать лучший вариант, следуя этим правилам:

• Вы можете выбрать только самую левую или самую правую карту.

• Ваш оппонент ВСЕГДА выбирает первым и ВСЕГДА выбирает старшую карту из крайней левой или правой карты. Если это галстук, он выберет самый правый. Примите во внимание, что это не всегда лучший выбор.

Иногда невозможно выиграть, но в любом случае вы должны показать максимальное количество очков, которое вы можете добавить, играя против этого оппонента (или, скажем, стратегии).

Пример:

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

Здесь я выбрал 1 вместо 4 на втором ходу, чтобы потом выбрать 8 позже. Поэтому выбор старшей карты не всегда лучший.

Я пытался реализовать это решение с помощью рекурсии, но я не уверен, что это лучший вариант. Любые идеи о том, как разработать этот алгоритм?

[EDIT] Спасибо @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),

Answer 2

Вы должны взглянуть на алгоритм Min-Max, возможно с альфа-бета-обрезкой

Мин-Макс - это идея, что ваш противник всегда будет выбирать для себя лучший выбор, поэтому вы можете запустить каждый возможный сценарий, чтобы найти лучший выбор, который приведет к тому, что вы опередите своего противника. "т. е. если я сделаю ход x, мой оппонент сделает ход y, затем я возьму…" и т. д. вплоть до конца игры. Таким образом, вы можете определить, кто победит.

Альфа-бета-обрезка похожа на то, что она рассматривает возможные сценарии, но она определяет, будет ли список возможных сценариев когда-либо давать выигрышный результат. Если вы знаете, что если вы сделаете "движение 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;
            }
        }
    }