Лучший выбор карт в карточной игре в 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)

• Let 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;
            }
        }
    }