В какой-то момент я задался вопросом: какова «финансовая» ценность каждой из карт в «Пьянице»? Так как Шестерка бьет Туза (см. вариант правил под катом), то система ценностей в «Пьянице» циклична, и ответ неочевиден. Например, ценнее ли Семерка Шестерки? Семерка бьет Шестерку — значит да! Но с другой стороны, каждая из них бьет только одну другую карту в игре (Семерка — Шестерку, а Шестерка — Туза) — значит они равны по ценности? Но Туз, побитый Шестеркой, сам по себе гораздо ценнее чем Шестерка, побитая Семеркой — значит Шестерка ценнее?!
Я решил подвести математическую модель под анализ ценности карт в «Пьянице». Результаты получились самые неожиданные.
Для начала, вот правила нашего варианта этой игры:
- В игре участвуют 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).
Комментарии (36)
lexnekr
28.03.2016 13:00+12Как понятно из правил, победа в этой игре зависит исключительно от везения — победитель определяется раздачей карт, так как от игроков вообще ничего не зависит.
Ой ли?
Ведь после каждого сражения победитель забирает карты сражения себе в каком-то порядке. Т.е. происходит уже не случайная сортировка колоды. Вы можете положить их в каком-то порядке сознательно, зная какие карты перед этим пришли "на дно" колоды противника. Не вижу простой стратегии как это можно было бы использовать, но как минимум элемент "случайности" из игры уйдёт ещё до конца 1 прохода колоды (по мере выхода карт из игры "на дно" колод для 2 круга).
Т.е. если не будет ни одного спора в 1 круге, то уже к 18 сражению вы 100% будете знать какая карта будет следующей у вас, а какая у противника. А дальше… Дальше только в зависимости от того следили ли вы за выходящими картами и кто в каком порядке их "на дно" возвращает.
scronheim
28.03.2016 15:38нужно заранее договариваться что бы после окончания карт, новая колода перемешивалась «рандомно»
lexnekr
28.03.2016 16:38У каждого игрока колода будет кончаться в разное время.
Опять же нужно будет считать обе колоды (или откладывать вышедшие из игры, но выигранные карты в сторону), чтобы понимать когда колода закончилась.
Я конечно не претендую на истину в последней инстанции (об игре узнал из статьи, если честно), но мне кажется это усложнит игру, которая судя по названию должна быть максимально простой и доступной при максимальном отказе мозговой активности.
lany
28.03.2016 18:26+3Самая простая стратегия (если противник не пользуется ей же). В каждом сражении участвует чётное количество карт и обычно человек складывает свою выигрышную карту сверху. В результате на чётных позициях оказываются в среднем более сильные карты. Если вы будете убитую шестёрку перекладывать наверх, она с большей вероятностью на следующем круге попадёт на вражеского туза. Опытные игроки делают это совершенно незаметно.
aaamodder
30.03.2016 15:11Кстати, да. Если не фиксировать порядок карт при складывании карт вниз колоды, а дать игрокам самим решать, то игра становится чуть более интелектуальной, и даже можно какие-то стратегии придумывать.
astgtciv
28.03.2016 15:27+1Интересно, мне это не приходило в голову. Но тогда еще нужно как-то следить за тем, в каком порядке карты кладет "на дно" противник.
В любом случае, мой анализ предполагает, что карты кладутся "на дно" в случайном порядке — так мы с сыном играем.
LoadRunner
28.03.2016 15:38Простите, а я прав в предположении, что после деления карт у каждого игрока на руках по 18 карт будет, а поскольку в колоде по четыре карты каждого достоинства, то вероятности будут совсем другие?
astgtciv
28.03.2016 16:41Я так себе и представлял, у каждого игрока по 18 карт — скажем, мы ходим с Шестерки. Против нее случайным образов на сражение выходит одна из оставшихся 35 карт — из-за этого везде вероятности в форме х/35.
LoadRunner
28.03.2016 16:56+2Я себе представляю так (так уж случилось, что я не получил высшего образования и у меня не было тервера):
Поскольку нам не важна масть, то вероятность наличия хотя бы одной шестёрки в нашей колоде — 1\9 (как и любой другой карты).
А как тут посчитать вероятность выпадения этой шестёрки самой первой из 18 карт?
Или правильно всё же считать сразу — выпадение шестёрки первой? Но правильно ли считать вероятность выпадения туза от 35 карт? Ведь до вытаскивания шестёрки у туза был ровно такой же шанс. И, по сути, после вытаскивания шестёрки мы колоду не тасовали, почему шанс должен меняться?
Я понимаю, что лучше бы мне взять и почитать учебник, но мне нравится правило "хочешь узнать правильный ответ — напиши неверный". На ошибках учиться как-то лучше получается.astgtciv
28.03.2016 17:03Все верно, я как раз писал про эту проблему где-то в середине поста. То, как я предлагаю высчитывать вероятности второго и последующих сражений корректно для случая, в котором колода тасуюется после каждого хода. У меня есть лишь надежда, что эти ошибки в вероятности как-то одинаково влияют на все карты, и поэтому результат все равно корректный. Но доказать я тут ничего не могу.
LoadRunner
28.03.2016 22:11Я тут в отрыве от компьютера вспомнил ещё одну вещь, которая зацепила и не отпускает:
Вы ищете вероятность для события "Шестёрка против Туза" ведь? Может тогда правильней считать, каков шанс на выпадение этой комбинации из всех возможных пар, которые на картах получатся?
Тогда из 630 возможных пар, ситуация "Шесть против Туза" возможна в 16 вариантах. А вот спор, когда выпадает ещё одна Шестёрка — всего лишь в 6 вариантах.
knagaev
29.03.2016 18:06Вы под "вероятность наличия хотя бы одной шестёрки в нашей колоде" подразумеваете, что на нашей руке есть от одной до четырёх шестёрок?
При решении задач по теории вероятностей очень важны формулировки :)LoadRunner
29.03.2016 20:49Я подразумеваю, что у нас есть минимум одна шестёрка. Ведь вероятность такого события выше, чем вероятность сразу двух шестёрок в нашей ополовиненной колоде?
Но в контексте данной задачи правильно ли высчитывать вероятность наличия каждой карты в колоде?
Я правильного ответа не знаю, потому и задаю такие вопросы.knagaev
30.03.2016 04:57Я опять не понял что Вы подразумеваете :) исходя из фразы "сразу двух шестерок", кажется, что Вы говорите о случае "ровно одной шестерки на руке", а не "хотя бы одной шестерки". Кстати, вероятность ровно двух шестерок на руке выше, чем ровно одной.
Давайте сформулируем точно что хотим считать :)LoadRunner
30.03.2016 06:33В нашей колоде из 18 карт может оказаться сразу 4 шестёрки, а может не оказаться ни одной. Я о случае, когда в нашей колоде от 1 до 4 шестёрок. Ведь если в нашей колоде есть две шестёрки (например), то одна там точно есть, поэтому и говорю "как минимум одна шестёрка".
rpisarev
28.03.2016 15:46Любопытно, когда в детстве учили играть, я то ли забыл про маневр с 6, то ли это опустили — играл с тех пор по более простым правилам: туз забирал и 6. Игра, на самом деле очень интересная с точки зрения подсчета карт и вырабатывания стратегии. К примеру, случалось, что споров нет и все карты проходили просто оборот и если число карт оставалось кратным (18:18, 24:12, 30:6), то могло произойти "зацикливание". Вероятно, дабы такого не было и вводится правило 6 сильнее туза.
rpisarev
28.03.2016 15:56На счёт случайности я тоже выработал стратегию — ввёл для себя понятие "боссы" и "пешки" — всегда в колоде, после первого оборота у меня было пешка-босс-пешка-босс-пешка...-босс, только если не вклинивался спор. Спор, кстати, тоже шел в порядке: "пешка-спор", т.е. тот, что отыграл, а после него свой "босс-спор". Такой спартанский порядок позволял частенько выигрывать. А когда знакомые начинали понимать фишку, то я вводил хитрость: ведь если в моей колоде было п-б-п-б-...-б, то у другого игрока было б-п-б-п-..-п. И с тузами я делал изменение порядка: п-б-б(туз)-п-п-б-...-б и таким образом удавалось частенько забирать много "боссов" другого игрока. Если не нарывался на туза (и спор, ведь правило о 6 я не знал), то стратегия прекрасно себя окупала.
kimifish
28.03.2016 21:30+1Не очень силён в статистике, поэтому спрошу: верно ли я понял, что можно сдать карты, посчитать у себя и противника тузов и королей и с большой долей вероятности сразу объявить победителя?
RomanPyr
29.03.2016 00:24+2Но это всё равно, что вместо просмотра фильма прочитать спойлер в википедии.
astgtciv
29.03.2016 08:03+1В общем-то да.
Кстати, в качестве проверки, если сложить ценность всех 9 карт — получается 9. Этого и следует ожидать, так как если раздать всю колоду одинаково на двоих (у обоих 18 равных карт), то ожидается что у тебя так и останется 18 карт.
У Туза ценность 4.2, это само по себе уже почти половина от 9. Так что тузы — самое главное, но Короли тоже еще оказывают какое-то влияние.
astgtciv
29.03.2016 07:57+1Я, кстати говоря, забыл написать зачем я стал все это расчитывать — я хотел понять насколько именно нужно радоваться и расстраиваться когда выигрываю или проигрываю ту или иную карту :)
dmagin
29.03.2016 11:54+1Прикольная задачка.
Вот как можно ее решить (и все подобные) в немного другой (более простой) постановке.
Положим, что каждая карта — это игрок. А все сражения между картами — это просто результаты турнира.
Тогда таблица результатов может быть записана проще и нагляднее,- примерно так:
0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
Это матрица смежности графа.
Все, что нам надо — вычислить потенциалы узлов (хм, тут должна быть ссылка куда-то наверное, — может на PageRank) — то есть грубо говоря, найти значимость узлов. Расчет потенциалов сводится к расчету миноров лапласиана от матрицы смежности, — то есть без всяких циклов можно просто посчитать определители (на самом деле — еще проще через обратную матрицу, но это нюансы).
Вектор результатов (ценности карт) получается такой:
6 5040
7 720
8 960
9 1344
10 2016
В 3360
Д 6720
К 20160
Т 35280
Отличается от вашего вектора в 8.4 раза.
То есть действительно ценность 6-ки лежит между валетом и дамой. Не знал ).
Думаю, что можно найти и явные выражения для потенциалов, поскольку матрица смежности проста.astgtciv
29.03.2016 13:56Звучит очень круто! Можно ссылку пожалуйста? Хочется понять, что значат все эти слова — я-то сам с трудом вспомнил про то как матрицы перемножают :)
dmagin
29.03.2016 15:47+1На простые и понятные статьи про лапласианы и их потенциалы я навскидку ссылок не вспомню.
Надо бы написать, конечно, в формате хабра.
Сам про них узнал несколько лет назад, когда разбирался с расчетом рейтингов и самооценок, — поэтому ваша задача и показалась знакомой.
Есть википедия — про матрицу лапласиана. Другое название — матрица Кирхгофа.
Дополнительный минор лапласиана — это когда вы из него удаляете строку и столбец и считаете определитель оставшейся матрицы.
То есть для получения потенциала 6-ки надо удалить из лапласиана от приведенной выше матрицы 1-й столбец и строку.
Можете все посчитать прямо в экселе.
Кстати, еще заметил, что все приведенные выше потенциалы кратны 16, так что можно сократить:
6 315
7 45
8 60
9 84
10 126
В 210
Д 420
К 1260
Т 2205
И еще — разложение приведенных потенциалов на простые множители включает только 2, 3, 5 и 7. Почему — пока неясно, но, повторюсь, что скорее всего можно общую формулу найти для потенциалов матриц приведенного выше типа (диагональных единиц с одним выколом в углу).LoadRunner
29.03.2016 20:52Больше того, 2, 3, 5, 7 — простые числа, причём идущие подряд.
dmagin
30.03.2016 10:08) Ну то, что они простые — это неудивительно, поскольку мы и раскладывали на простые.
А вот то, что множители в разложении не превышают 9 — тоже объяснилось. Поскольку в формулах для вычисления используются факториалы до 9 (см. ниже), то другим простым не откуда взяться.
dmagin
30.03.2016 10:03+1Да, как я и предполагал — нашлось явное выражение для потенциалов (значимости) карт.
Возможно, пояснения требуют отдельной статьи,- тут пока отпишусь для фиксации формул.
Обозначим количество карт разного достоинства через n (для колоды в 36 карт n = 36/4 = 9, для колоды в 52 — n = 13).
Достоинства карт пронумеруем от 1 (самая младшая,- 6-ка для 36, 2-ка для 52) до n (самая старшая — туз) и обозначим через k.
Тогда имеем три формулы для потенциалов достоинств U(k, n):
- Для k = 1: U(1,n) = (n-2)! — это потенциал самых младших карт (шестерок), которые бьют туза, но проигрывают всем остальным.
- Для k = n: U(n,n) = (n-2)!(n-2) — это потенциал самых старших карт, которые бьют всех, но проигрывают шестеркам.
- Для 1 < k < n: U(k,n) = (n-k-1)!(n-1)! / (n-k+1)! — это потенциалы всех остальных карт.
Для колоды из 36 карт получаем приведенные выше цифры:
U(1,9) = (9-2)! = 5040 — шестерка
U(9,9) = (9-2)!(9-2) = 50407 = 35280 — туз
U(6,9) = 2!8! / 4! = 25678 = 3360 — валет
Из формул видно, например, что отношение потенциала условного туза к условной шестерке всегда равно (n-2).
А отношение туза к королю — U(n,n) / U(n-1,n) = 2(n-2) / (n-1).
Ну и т. д.LoadRunner
30.03.2016 10:33Тут где-то потерялись знаки умножения. Похоже, маркдаун-разметка постаралась.
Было бы интересно почитать статью с картинками и пояснениями на пальцах к этим формулам — почему они именно такие.
И сферу применения — где, помимо карт, это принесло бы пользу.
dmagin
30.03.2016 10:50+1Для завершенности картины приведем явные формулы для профита карты — количества ожидаемых приобретений.
Профит — это относительная ценность (потенциал) карты, умноженная на количество карт (n).
Для вычисления относительной ценности надо поделить потенциал карты на сумму потенциалов всех карт.
Сумма потенциалов карт может быть вычислена по формуле:
S(n) = Sum(k){U(k,n)} = (n-2)! (2n-3)
Тогда профит 6-ки равен:
P(1,n) = U(1,n)* n / S(n) = n/(2n — 3)
Для 36-колоды получаем P(1,9) = 9/15 = 3/5 = 0.6. Именно эта цифра приведена в статье.
А профит туза — P(n,n) = U(n,n)* n / S(n) = n(n — 2) / (2n — 3),
Для стандартной колоды — P(9,9) = 97 / 15 = 0.6 7 = 4.2.
Biblusha
Вниз своей колоды можно незаметно положить туза и в нужный момент забирать королей или дам, вытягивая карту не сверху а снизу.
Не всё зависит от удачи ;-)