Хабрахабр

Еще потасовать или хватит?

Пока я тасую карты, передо мной всегда возникает вопрос: "Уже хватит?" Вопрос серьезный — лишнее время тратить не хочется, а играть на заряженной колоде тоже не в кайф.
В статье разберемся с ситуацией.
Почти в каждой карточной игре после партии нужно перетасовать карты.

По моим наблюдениям люди тасуют карты именно так или близко к этому. Есть крутые способы тасовать карты, riffle shuffle, например.

Я так не умею, да и картонные карты так не получится шафлить, поэтому я тасую простым способом, выглядит примерно так:

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

Первое что пришло мне в голову — хорошая раскладка та, на i-м месте может равновероятно оказаться любая карта.

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

Представить это можно так: если смотришь верхнюю карту колоды, то не можешь предположить какая карта будет следующей. Другой подход к определению хорошей раскладки — на i+1-м месте лежит карта независимая от карты на i-м месте.

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

Занумеруем все карты по порядку. Мы взяли колоду, оставшуюся после предыдущей игры. Поэтому будем измерять долю карт, которые лежат по порядку после перетасовки. Плохая ситуация — когда после перетасовки в каком-то месте после карты с номером i идет карта с номером i+1.

def next_stat(a): c_next = 0 c_total = 0 for i in range(len(a)-1): c_total += 1 c_next += a[i] == (a[i+1]-1) return c_next * 1.0 / c_total

Их доля будет в среднем 1/(n-1), где n — количество карт в колоде. Понятно, что даже в хорошо потасованной колоде некоторые карты случайно лягут по порядку.

Пруф

ожидания.
И так как E($ai = a{i+1}$) = 1/(n-1) то это выражение = (n-1) * 1/(n-1) / (n-1) = 1/(n-1) E(sum($ai = a$ for i = 0..(n-1)) / (n-1)) = sum(E($ai = a{i+1}$) for i = 0..(n-1)) / (n-1) — из-за линейности мат.

Посчитаем вероятность подряд идущих карт для колоды из 52 карт в зависимости от количества итераций перемешивания.

Из графика видно, что даже после сотни итераций вероятность подряд идущих карт примерно в два раза выше, чем идеальная вероятность.

Код для построения графика

import random def two_split_shuffle(a): s1 = random.randint(1,len(a)-1) s2 = random.randint(1,len(a)-1) s_min = min(s1, s2) s_max = max(s1, s2) p1 = a[:s_min] p2 = a[s_min:s_max] p3 = a[s_max:] return p3 + p2 + p1 def shuffle_n(a, f, n): for _ in range(n): a = f(a) return a def next_stat(a): c_next = 0 c_total = 0 for i in range(len(a)-1): c_total += 1 c_next += a[i] == (a[i+1]-1) return c_next * 1.0 / c_total def expected(f, n = 100): s = 0 for _ in range(n): s += f() return s / n def get_expected_next_stat(shuf, n, cards): return expected(lambda: next_stat(shuffle_n(range(cards), shuf, n))) cards = 52
x = range(100)
y = map(lambda i: get_expected_next_stat(two_split_shuffle, i, cards), x) import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize=(12,8))
plt.plot(x, y, label = u'Вероятность подряд идущих карт для разделения на 3')
plt.plot(x, [1./(cards-1)] * len(x), label = u'Оптимальная вероятность')
plt.grid()
plt.legend()

Я за 30 секунд делаю примерно 16-17 итераций. В целом, можно считать, что 60 итераций — оптимальное количество, меньше точно плохо. Это значит, что для нормальной перетасовки понадобится почти две минуты.

А это значит, что у нас на игру очень сильно влияет расклад прошлой партии. Мы с друзьями никогда столько не тасуем карты.

Будьте аккуратны)

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть