В последнее время я много играю со своим 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).
Автор: astgtciv
