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

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

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

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

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

Пример:

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

c# recursion algorithm playing-cards
person Jean Carlos Suárez Marranzini    schedule 12.01.2012    source источник
comment
Как выигрывается игра? Вы рассказали нам правила, но не цель.   -  person PengOne    schedule 12.01.2012
comment
1 2 4 2 8 4 3 Оппонент: 3 4 2 2. Как он это сделал?   -  person Amir Afghani    schedule 12.01.2012
comment
это задание школы/универа?   -  person lahsrah    schedule 12.01.2012
comment
Игра выиграна, если вы наберете больше очков, чем ваш противник, добавив выбранные вами карты.   -  person Jean Carlos Suárez Marranzini    schedule 12.01.2012
comment
Противник: 3 4 2 2 Сначала он выбрал 3 (он всегда выбирает самый высокий), потом я взял 1, он взял 4, я взял 8, потом он взял 2, потом я взял 4, он взял 2.   -  person Jean Carlos Suárez Marranzini    schedule 12.01.2012
comment
Любой игрок может выбрать только крайнюю левую или крайнюю правую карту.   -  person Jean Carlos Suárez Marranzini    schedule 12.01.2012
comment
Я пытался охватить любую доступную возможность исхода по моему выбору. Но всегда что-то не так. Мой код слишком длинный и жестко запрограммирован, чтобы его можно было показать.   -  person Jean Carlos Suárez Marranzini    schedule 12.01.2012

Ответы (3)


arrow_upward
4
arrow_downward

Постройте решение из простейших случаев, используя рекурсию.

Пусть 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).

person PengOne    schedule 12.01.2012
comment
Спасибо за помощь. Я сделал все возможное и фактически опубликовал алгоритм, который я пытаюсь сделать на основе объяснения. Что в нем еще не так? - person Jean Carlos Suárez Marranzini; 13.01.2012
comment
Я все еще предоставляю обновления кода, надеясь с каждым разом становиться лучше. - person Jean Carlos Suárez Marranzini; 13.01.2012

arrow_upward
3
arrow_downward

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

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

Сокращение альфа-бета похоже на то, что оно рассматривает возможные сценарии, но определяет, приведет ли список возможных сценариев к выигрышному результату. Если вы знаете, что если вы сделаете «ход x», то вы всегда будете проигрывать, несмотря ни на что, вам не нужно тратить больше времени на поиск «хода x, затем хода y». Вы можете «обрезать» всю ветвь выбора из «переместить x», потому что вы знаете, что это никогда не поможет.

person jb.    schedule 12.01.2012
comment
При таком маленьком пространстве состояния его даже не нужно подрезать. - person Amir Afghani; 12.01.2012
comment
@AmirАфгани, скорее всего, вы совершенно правы, но я бы не отдал ему должного, если бы не упомянул об этом. - person jb.; 12.01.2012
comment
Минимакс действительно имеет смысл только тогда, когда вы вынуждены использовать эвристику в какой-то момент, потому что полный просмотр вперед слишком дорог. Это может быть верно для этой игры, если в стартовом списке, скажем, шестьдесят номеров. - person Rafe; 12.01.2012
comment
Минимакс действительно имеет смысл только тогда, когда вы вынуждены использовать эвристику в какой-то момент, потому что полный просмотр вперед слишком дорог. Это может быть верно для этой игры, если в стартовом списке, скажем, шестьдесят номеров. - person Rafe; 12.01.2012
comment
Я бы сказал, что минимакс более осмысленный, не только осмысленный. Он может выполнить исчерпывающий поиск с помощью минимакса и получить наилучший ответ. - person Amir Afghani; 12.01.2012
comment
Согласен, минимакс позволит ему просмотреть все варианты и найти ответ. Если пространство поиска маленькое, это будет быстрее. - person jb.; 13.01.2012

arrow_upward
2
arrow_downward

Это код, который действительно работал в конце. Спасибо всем за вашу поддержку.

    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;
            }
        }
    }
person Jean Carlos Suárez Marranzini    schedule 13.01.2012
comment
Я полагаю, вы хотите, чтобы opponentScore был параметром ref. В противном случае, когда вы обновляете его значение, вы не сохраняете результат. - person jb.; 14.01.2012