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

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

Есть крутые способы тасовать карты, 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(sum($ai = a{i+1}$ for i = 0..(n-1)) / (n-1)) = sum(E($ai = a{i+1}$) for i = 0..(n-1)) / (n-1) — из-за линейности мат. ожидания.
И так как E($ai = a{i+1}$) = 1/(n-1) то это выражение = (n-1) * 1/(n-1) / (n-1) = 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()

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

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

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

Let's block ads! (Why?)