[Из песочницы] О ценности карт в игре «Пьяница»28.03.2016 12:48

В последнее время я много играю со своим 5-летним сыном в карточную игру «Пьяница». И он, и я радуемся, когда побеждаем, и огорчаемся, когда проигрываем.

В какой-то момент я задался вопросом: какова «финансовая» ценность каждой из карт в «Пьянице»? Так как Шестерка бьет Туза (см. вариант правил под катом), то система ценностей в «Пьянице» циклична, и ответ неочевиден. Например, ценнее ли Семерка Шестерки? Семерка бьет Шестерку — значит да! Но с другой стороны, каждая из них бьет только одну другую карту в игре (Семерка — Шестерку, а Шестерка — Туза) — значит они равны по ценности? Но Туз, побитый Шестеркой, сам по себе гораздо ценнее чем Шестерка, побитая Семеркой — значит Шестерка ценнее?!

Я решил подвести математическую модель под анализ ценности карт в «Пьянице». Результаты получились самые неожиданные.
Для начала, вот правила нашего варианта этой игры:

  • В игре участвуют 2 игрока.
  • 36 карт (от шестерок до тузов) раздаются поровну.
  • Каждый игрок снимает верхнюю карту своей колоды и кладет ее лицом вверх — происходит «сражение». Победивший в сражении игрок кладет все карты сражения под низ своей колоды.
  • Победитель в сражении определяется по обычному старшинству карт (сверху вниз): Туз, Король, Дама, Валет, Десятка, Девятка, Восьмерка, Семерка, Шестерка. Есть только одно очень важное исключение: Шестерка побеждает Туза.
  • Если в сражении участвуют одинаковые карты (например, две десятки), то происходит «спор»: поверх «спорящих» карт лицом вниз кладутся еще по карте (они являются пассивными заложниками спора), и потом лицом вверх еще две карты которые вступают в сражение. Победитель забирает себе все карты спора.


Как понятно из правил, победа в этой игре зависит исключительно от везения — победитель определяется раздачей карт, так как от игроков вообще ничего не зависит.

Итак, как мы можем определить «ценность» карты в «Пьянице»? Я решил определить ценность карты через ожидаемое количество карт которые эта карта принесет если игра будет продолжаться бесконечно долго.

Начнем с простой задачи: определения ожидаемого количества карт только для Шестерки и только одного сражения. В колоде 36 карт, значит, если мы ходим Шестеркой, она вступает в сражение с другой (случайно выбранной) картой из оставшихся 35ти. Что может произойти? С вероятностью в 4/35 выпадет Туз, и тогда мы получим и Шестерку, и Туза. С вероятностью в 3/35 выпадет еще одна Шестерка, и произойдет спор —, а так как мы предполагаем абсолютно случайный расклад, то мы с равной вероятностью либо выиграем, либо проиграем его, а значит, что в среднем ожидается, что наша Шестерка останется у нас. Во всех остальных случаях мы теряем шестерку. Итого, ожидаемое кол-во карт для Шестерки после одного сражения: 7/35 Шестерки + 4/35 Туза.

Теперь, заполним матрицу для ожидаемых кол-в всех карт для одного сражения (ряд Шестерки — это ожидаемое кол-во карт получаемое после одного сражения с участием нашей Шестерки).

Шестерка Семерка Восьмерка Девятка Десятка Валет Дама Король Туз
Шестерка 7/35 0 0 0 0 0 0 0 4/35
Семерка 4/35 7/35 0 0 0 0 0 0 0
Восьмерка 4/35 4/35 11/35 0 0 0 0 0 0
Девятка 4/35 4/35 4/35 15/35 0 0 0 0 0
Десятка 4/35 4/35 4/35 4/35 19/35 0 0 0 0
Валет 4/35 4/35 4/35 4/35 4/35 23/35 0 0 0
Дама 4/35 4/35 4/35 4/35 4/35 4/35 27/35 0 0
Король 4/35 4/35 4/35 4/35 4/35 4/35 4/35 31/35 0
Туз 0 4/35 4/35 4/35 4/35 4/35 4/35 4/35 31/35


Очевидно, что недостаточно учесть одно сражение, чтобы определить ценность карты. Например, у Шестерки есть шанс выиграть Туза, который сыграет в какой-то момент в будущем и, в свою очередь, имеет шанс выиграть другие карты. Как получить подобную матрицу, но с ожидаемыми кол-вами карт через два сражения? Ответ оказывается до изумления простым — надо просто умножить эту матрицу на саму себя! (Основы матричного умножения: чтобы получить элемент (X, Y) результата умножения, надо скалярно умножить ряд Х первой матрицы на колонку Y второй, то есть попарно перемножить соответствующие элементы этих двух векторов и результаты сложить).

Например, вероятность начать с Шестерки и через 2 сражения держать на руках Шестерку — (7/35)^2, так как Туз, потенциально выигранный в первом сражении никак не увеличивать шансов получить Шестерку во втором. Однако, тот же Туз увеличивает шансы получить каждую из остальных карт во втором сражении —, но ожидаемые кол-ва карт для Туза во втором сражении умножаются на вероятность получить Туза в первом сражении (4/35). И т.д.

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

Итак, совсем немного руби кода: 

require 'matrix'
# Матрица ожидаемых кол-в для одного сражения
m1 = Matrix[
     [7.0/35, 0, 0, 0, 0, 0, 0, 0, 4.0/35],
     [4.0/35, 7.0/35, 0, 0, 0, 0, 0, 0, 0],
     [4.0/35, 4.0/35, 11.0/35, 0, 0, 0, 0, 0, 0],
     [4.0/35, 4.0/35, 4.0/35, 15.0/35, 0, 0, 0, 0, 0],
     [4.0/35, 4.0/35, 4.0/35, 4.0/35, 19.0/35, 0, 0, 0, 0],
     [4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 23.0/35, 0, 0, 0],
     [4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 27.0/35, 0, 0],
     [4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 31.0/35, 0],
     [0, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 4.0/35, 31.0/35]
]
# Матрица ожидаемых кол-в после 1000 сражений (m1 в степени 1000)
m1000 = m1 ** 1000
# (значения округлены) => Matrix[[0.0667, 0.0667, 0.0667, 0.0667, 0.0667, 0.0667, 0.0667, 0.0667, 0.0667], [0.0095, 0.0095, 0.0095, 0.0095, 0.0095, 0.0095, 0.0095, 0.0095, 0.0095], [0.0127, 0.0127, 0.0127, 0.0127, 0.0127, 0.0127, 0.0127, 0.0127, 0.0127], [0.0178, 0.0178, 0.0178, 0.0178, 0.0178, 0.0178, 0.0178, 0.0178, 0.0178], [0.0267, 0.0267, 0.0267, 0.0267, 0.0267, 0.0267, 0.0267, 0.0267, 0.0267], [0.0444, 0.0444, 0.0444, 0.0444, 0.0444, 0.0444, 0.0444, 0.0444, 0.0444], [0.0889, 0.0889, 0.0889, 0.0889, 0.0889, 0.0889, 0.0889, 0.0889, 0.0889], [0.2667, 0.2667, 0.2667, 0.2667, 0.2667, 0.2667, 0.2667, 0.2667, 0.2667], [0.4667, 0.4667, 0.4667, 0.4667, 0.4667, 0.4667, 0.4667, 0.4667, 0.4667]]


Обратите внимание, как через некоторое кол-во сражений все ожидаемые кол-ва карт для одной карты становятся одинаковыми — так как (из-за циркулярной системы ценностей) в конце концов мы можем выиграть все карты, то ожидаемые кол-ва для всех карт сходятся к одному числу. Теперь осталось совсем немного — складываем все числа в каждом ряду чтобы узнать «ценность» каждой из карт (т.е., ожидаемое число карт после 1000 сражений): 

m1000.row_vectors.map {|row| row.reduce(&:+).round(3)}
# [0.6, 0.086, 0.114, 0.16, 0.24, 0.4, 0.8, 2.4, 4.2]


Для наглядности:

Шестерка Семерка Восьмерка Девятка Десятка Валет Дама Король Туз
Ценность 0.6 0.086 0.114 0.16 0.24 0.4 0.8 2.4 4.2


Неожиданные выводы:

  • Ценность Шестерки лежит между Валетом и Дамой!
  • Только у Короля и Туза ожидаемое конечное кол-во карт превышает 1 (то есть, ожидается позитивный ROI).

© Habrahabr.ru