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

Question

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

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

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

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

Пример:

родовое слово

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

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

[РЕДАКТИРОВАТЬ] Спасибо @PengOne за щедрую помощь. Это код, который я пытаюсь реализовать, но, к сожалению, он дает мне ошибки. Что в ней исправить? Я редактирую это по мере продвижения.

родовое слово

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. Здесь создается кодовый код.

Answer 2

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

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

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

Answer 3

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

родовое слово