Анализируя модифицированную версию карточной игры «Война»

Простая игра, в которую обычно играют дети, в игру «Война» играют два человека, используя стандартную колоду из 52 игральных карт. Сначала колода перемешивается, и все карты раздаются двум игрокам, так что у каждой по 26 случайных карт в случайном порядке. Предположим, что игрокам разрешено проверять (но не менять) обе колоды, чтобы каждый игрок знал карты и порядки карт в обеих колодах. Обычно это замечание делается на практике, но оно ничего не меняет в том, как проходит игра, и помогает сохранить эту версию вопроса полностью детерминированной.

Затем игроки открывают самые лучшие карты из соответствующих колод. Игрок, который открывает большую карту (согласно обычному порядку: 2, 3, 4, 5, 6, 7, 8, 9, 10, Джек, Королева, Король, Туз), выигрывает раунд, ставя свою первую карту ( старшая карта) внизу его колоды, а затем - карта его оппонента (младшая карта) внизу колоды (как правило, порядок этого не применяется, но чтобы сохранить первую версию этого вопроса детерминированной, например, приказ будет применяться).

В случае ничьей каждый игрок раскрывает четыре дополнительные карты сверху своих колод. Если четвертая карта, показанная одним игроком, выше, чем четвертая карта, показанная другим игроком, игрок с более высокой четвертой картой выигрывает все карты, сыгранные во время тай-брейка, и в этом случае карты победителя сначала помещаются внизу поля. колода победителя (в порядке «первым пришел - первым вышел»; другими словами, более старые карты помещаются внизу первыми), за которыми следуют карты проигравших (в том же порядке).

В случае последующих связей процесс повторяется до тех пор, пока не будет определен победитель. Если у одного из игроков закончились карты и он не может разорвать ничью, игрок, у которого все еще есть карты, объявляется победителем. Если у обоих игроков заканчиваются карты для игры одновременно, игра объявляется ничейной.

Раунды разыгрываются до тех пор, пока у одного из игроков не закончатся карты (т.е. в его колоде больше нет карт), после чего игрок, у которого еще есть карты, объявляется победителем.

Поскольку игра была описана до сих пор, ни умение, ни удача не участвуют в определении результата. Поскольку существует конечное число перестановок из 52 карт, существует ограниченное количество способов, которыми могут быть изначально разыграны колоды, и из этого следует, что (поскольку единственная информация о состоянии в игре - это текущее состояние колод обеих игроков. ) исход каждой игровой конфигурации может быть определен априори. Конечно, это возможно, чтобы выиграть игру в войну, и по той же причине, чтобы проиграть ее. Мы также оставляем открытой возможность того, что игра в войну может привести к ничьей или бесконечному циклу; для полностью детерминированной версии, описанной выше, это может иметь место или не иметь место.

Несколько вариантов игры, которые пытаются сделать ее более интересной (и нет, не все включают превращение ее в пьющую игру). Один из способов сделать игру более интересной - позволить игрокам объявлять автоматические «козыри» в определенных раундах. В каждом раунде любой игрок (или оба игрока) может объявить «козырем». Если один из игроков объявляет «козырь», этот игрок выигрывает раунд независимо от того, какие карты играют. Если оба игрока объявляют «козырь», то раунд считается ничейным, и игра продолжается соответственно.

Можно представить себе множество правил, ограничивающих способность игроков козырять (неограниченные козыри всегда приводят к игре в «Tie», поскольку игроки бьют козыри каждый ход). Я предлагаю две версии (чуть выше моей головы; вероятно, более интересные версии в этих направлениях) войны, основанные на этой идее, но использующие разные механизмы ограничения козырей:

1. Frequency-War: игроки могут победить, только если они не выиграли в предыдущих раундах.$k$
2. Война мести: игроки могут победить, только если они не выиграли раунд в предыдущих раундах.$k$

Теперь о вопросах, которые относятся к каждой из версий, описанных выше:

1. Существует ли такая стратегия, что для некоторого набора возможных начальных конфигураций игры игрок, использующий ее, всегда выигрывает (стратегия с сильным выигрышем)? Если так, то какова эта стратегия? Если нет, то почему нет?
2. Существует ли такая стратегия, что для некоторого набора возможных начальных конфигураций игры игрок, использующий ее, всегда может выиграть или форсировать ничью (выигрышная стратегия)? Если так, то какова эта стратегия? Если нет, то почему нет?
3. $S$$S'$

Чтобы было ясно, я думаю о «стратегии» как о фиксированном алгоритме, который определяет, в каких раундах игрок, использующий стратегию, должен превзойти. Например, алгоритм «бить, когда можешь» - это стратегия, а алгоритм (эвристический алгоритм). Другой способ, о котором я спрашиваю, заключается в следующем:

Есть ли хорошие (или доказуемо оптимальные) эвристики для игры в эти игры?

$k$$k=0$

Если я правильно понимаю, вся информация об игре доступна обоим игрокам. Таким образом, начальная конфигурация и все возможные ходы известны обоим игрокам (в основном потому, что оба игрока могут посмотреть карты другого игрока). Это делает игру идеальной информацией с нулевой суммой. Таким образом, существует идеальная стратегия, доступная обоим игрокам, которая достигла бы лучшего результата в каждой игре для этого игрока. Это было доказано в 1912 году немецким математиком Эрнстом Цермело.

Я не знаю, что такое стратегия, но можно представить, как построить для нее большое игровое дерево и заставить компьютер найти стратегию для меня, используя алгоритм min-max .

Дерево для каждой игры будет иметь в качестве корня руки двух игроков. Ветви на дереве соответствуют ходам игроков. В простейшем случае они состоят из простой установки необходимых карт. В более сложных случаях можно сделать «козырный» ход. Внутренние узлы дерева записывают текущую конфигурацию карточек вместе с любой информацией о состоянии относительно «козырей». Листья дерева соответствуют позициям в конце игры, которые будут отмечены, скажем, +1 для победы Игроку 1, 0 для ничьей и -1 для победы Игроку 2. Игнорируйте циклические игры на данный момент.

Теперь алгоритм min-max будет работать следующим образом (с точки зрения игрока 1). Предположим, что он смотрит на узел, где игрок 1 делает ход, и что узлы ниже помечены +1, 0 или -1 ( выплата) наряду с выбором, который игрок должен сделать, чтобы получить заданный результат. Игрок 1 просто выбирает узел с наибольшей выплатой, записывает эту выплату и выбор, необходимый для ее получения. Для узла, в котором игрок 2 делает ход, выбирается узел с минимальным выигрышем, и этот выбор записывается. Это отражает то, что Игрок 2 стремится выиграть с наименьшим количеством очков. Это распространяется на дерево. Выборы, записанные в каждом узле, соответствуют лучшей стратегии, которую может сделать игрок. Окончательный выигрыш определяет, кто победит. В конечном счете, это функция с точки зрения выигрыша, хотя точный выбор ходов может отличаться.

Потенциально циклические конфигурации могут быть включены в игровое дерево, просто добавляя петли, которые возвращаются к уже увиденной конфигурации (при вычислениях сверху). Для таких узлов вы берете наибольшую фиксированную точку, если это узел, где играет Игрок 1, и наименьшую фиксированную точку, когда Игрок 2 играет.

Обратите внимание, что если вы не сделали предположение, что оба игрока могут исследовать обе колоды, этот подход не будет применяться. Тогда игра будет включать случайность, а выбранная стратегия будет зависеть от конкретной игры.

Существует ли сильная или слабая выигрышная стратегия для одного из игроков, зависит от результата алгоритма min-max, примененного ко всем деревьям. Но их наверняка много ... Вычислить дерево для одного, вероятно, довольно просто, поскольку в игре не так много вариантов.