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

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


    В статье разберемся с ситуацией.



    Способ тасовки


    Есть крутые способы тасовать карты, 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 итераций. Это значит, что для нормальной перетасовки понадобится почти две минуты.


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


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

    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 68

      +2
      Вопрос решается раскладыванием карт на несколько стопок, после чего складыванием их вместе и тасовкой. Несколько итераций можно секунд за 30 сделать.
        +5
        Вопрос решается недорогой машинкой с AliExpress :)
          0
          ShuffleMachine если на то пошло. IoT убъет их, хотя изначально — статистика!
            +3
            недорогя шаффл машинка с алиэкспресс не перетасует карты хорошо ( проверено ).
            Только профф модели от 500$ и выше
              +2
              Среднестатистически мы имеем ShuffleMachine за 500$ и выше, фактически мы имеем пару маргиналов у которых режим «Shuffle» отключается после опохмелья. Так себе тоже механизм. Но у этих механизмов random не псевдослучаен!
                +1

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

                  0
                  Врут. Без вмешательства в прошивку шафлмашины сие невозможно.
                  Они все проходят сертификацию ( что то типа RNG Certification )
                    +1
                    Кстати, просветите неграмотного человека…

                    Как я понимаю, современные шаффл-машины тоже электронные с ГПСЧ. А что служит в них источником энтропии?
                      0
                      В основном оптические шумы. Читал что есть решения где радиоактивный элемент внутри чипа.
                      Мы в свое время такие покупали www.idquantique.com/random-number-generation/products/quantis-random-number-generator чтобы сертификацию пройти
                      «Uses quantum optics process to create true quantum randomness»
                        0
                        Ну, если с источником радиации, то, думаю, сертификацию СЭС будет получить сложнее.
                          0
                          Я думаю что если используется альфа распад, то нет необходимости.
                          Но это мое имхо. Я не изучал вопрос.
            +18

            Эта статья могла бы быть просто великолепна если бы вы использовали математику из этой публикации https://arxiv.org/pdf/math/0501401.pdf. Jonasson в ней доказал что чтобы хорошо перетасовать колоду способом из статьи нужно минимум N^2 log N (для колоды из N карт) повторений, что чуть-чуть далеко от 64.


            Кстати, эта же работа ссылается на другую работу в которой был найден самый эффективный способ тасовки — 7 итераций river shuffle.

              0

              Спасибо за ссылку. Лютый матан, конечно, аж зависть берёт. Поискал river – не нашлось, зато на первой странице упоминается riffle со ссылкой на [1], там итераций до идеальной перетасовки 1.5log2n. Может, это оно?

                0

                Riffle конечно же, автокоррекция подвела. Оценка количества итераций которую вы привели это почти она. Bayer ее уточнил по тому как люди тасуют карты и оценка чуть-чуть понизилась до тех самых 7.

                  0
                  Но есть, как говорится, нюансы…

                  Если идеально (т.е. так, чтобы карты перемещались строго через одну) выполнить riffle shuffle над преферансной колодой (32 листа), то она вернется в исходное состояние :)
                    0

                    Да, и это реальная проблема для тасовачных машин. Оказалось что сложно сделать машину которая будет делить колоду на две части в недетерминированном месте и тасовать ее неровно (когда каждая карта слева ложиться на каждую справа). То есть повторять «ошибки» людей, которые, в общем, и делают riffle эффективным.

              –12

              идеально перетасовать может смартфон или комп, напишите прогу (если такой нет): домашний комп будет сервером, гости по wi-fi подключаются и играют в карты

                +14
                А потом резиновые женщины и безалкогольное пиво? А как же ощущения?
                  +1

                  Карты с какой-нибудь "умной бумагой", на которой сервер отображает нужные карты при каждой раздаче.
                  Ощущения в порядке :)

                    0

                    А потом соревнования по взлому карт

                      +2
                      — У меня козырный туз — У меня тоже!
                  –10
                  домашний комп будет сервером, гости по wi-fi подключаются

                  Люблю старую школу… новому поколению с его облачными блокчейнами на лямбдах такого и в голову, уверен, не придет никогда)
                    +2
                    Подобными комментариями, «состаривающими» такой подход, вы делаете только хуже.
                      +9
                      Когда ноют про новые поколения – как-то забывают, кто именно эти поколения растил и воспитывал…
                    +2

                    Есть хороший выпуск намберфила по этой же теме
                    https://youtu.be/AxJubaijQbI

                      +1
                      Зашел в комментарии посмотреть, упомянул ли кто это видео. Именно после него я не поленился освоить riffle shuffle — это оказало несложно — и теперь тасую карты гораздо лучше.
                      +1
                      Знакомое вроде видео на картинке. Я так и не понял тогда, чувак с него прав в своих возмущениях или нет?
                        +1
                        Где-то обсуждали, что это вообще не проигравшийся игрок, как часто на описаниях к нему пишут, а контролер от владельца казино, который пришел причины крупного выигрыша расследовать
                        +4
                        Что такое случайная раскладка карт?

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

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

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

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


                        Кажется очевидным, что хорошая случайная тасовка колоды из n карт — та, после которой получившаяся последовательность карт является случайной величиной с равномерным распределением на множестве из n! всех возможных перестановок карт. Почему вам первым в голову пришло именно то, что написано, я не понимаю.
                          +1
                          Тоже хотел написать именно это определение — равномерность на множестве всех перестановок. Но, справедливости ради, этот критерий технически трудно проверять (n! — это довольно много), поэтому часто используются критерии-проекции: проверить распределение отдельных карт, пар карт и т.д., в общем случае это какая-нибудь функция небольшой мощности от перестановки.
                            0
                            Если задать такое определение, то для перехода из некоторой расстановки понадобится в любую другую с одинаковой вероятностью около 20!-26! снятий (даже называть страшно), river shuffle скорее всего только в 100 раз меньше.
                              0
                              Наверное, это говорит о неэффективности используемых алгоритмов шафла карточной колоды. Ведь обычная случайная перестановка работает за линейное число операций, как уже упомянули ниже.
                            –1

                            Если кто не видел сюда про 52!

                              –1
                              > Плохая ситуация — когда после перетасовки в каком-то месте после карты с номером i идет карта с номером i+1

                              Нормальная ситуация для нормального рандома.
                              Тасовка, в которой никакие пары карт никогда не сохраняют свои позиции — плохая ситуация.
                              ____

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

                              Если положить колоду на стол и брать по одной карте, которую класть в случайное место в колоде в руках(которая изначально пуста), то после 52 таких итераций мы получим перетасованную колоду, равномерность которой зависит только от равномерности нашего «генератора случайного места».
                                +3
                                можно еще рассыпать по столу, а потом собрать
                                +6
                                Мы с друзьями никогда столько не тасуем карты. А это значит, что у нас на игру очень сильно влияет расклад прошлой партии.

                                На Гамблере давно выяснено, что сгенерированная ГПСЧ «хорошо перетасованная колода» неестественна. При игре в преферанс она выдает более равномерные расклады рук, чем это случается в реальной игре.

                                Игроки, много играющие живую, готовы к такому отклонению от случайности и интуитивно его эксплуатируют.
                                Поэтому игра на Гамблере кажется им неправдоподобной.

                                Проводили эксперименты. В реальной игре подсчитывали число одномастных прикупов (т.е. таких, в которых обе карты одной масти). Так вот, частота таких прикупов оказывалась в 1,5-2 раза выше, чем при идеальной тасовке.
                                  +2
                                  Выходит, хороший ГПСЧ для максимального удовольствия от карточных игр должен намеренно допускать «неслучайность», и отвечать ряду статистических критериев, которые соответствуют ручной тасовке.
                                    +1
                                    Беда в том, что сформулировать эту «неслучайность» еще гораздо сложнее, чем идеальную случайность.

                                    Т.е. если неудачно подобрать ее статистические характеристики, то число недовольных игроков только возрастет. А если подобрать другие характеристики, то к ним примкнут еще и новые.

                                    А так администрация может честно ответить: Да, мы знаем, что раздачи немного не соответствуют реальным. Зато они чисто случайные и все, поэтому, в равных условиях.
                                    0
                                    Я встречал разные подходы при игре в реальный преферанс — кто-то говорит, что надо тщательно мешать колоду (любители распасовок очевидно) и вторая крайность — вообще не мешать колоду, максимум две итерации
                                      0
                                      С этой т.зрения автору статьи не мешало бы дать критерии оптимальной колоды. В Преферансе таким способом фактически не допускаются именно случайные расклады. Иначе, играть становится не интересно.
                                      0

                                      Для многих игр, особенно не имеющих "карт на руке" ("Каркассон"), или малое их количество, при большом количестве вариаций ("Зельеварение", хоть с допами, хоть без), и имеющих явное деление карт на early-, mid- и endgame, актуально не просто равномерно перемешать, а еще так, чтобы не шли косяками в начале партии топовые карты.

                                        0
                                        Сначала я отделяю от колоды часть, потом долю этой части закидываю на другую сторону, а после докладываю оставшуюся долю
                                        Обычно при тасовке используем следующий «алгоритм».
                                        Первым движением берется часть карт из середины колоды. Потом доля этой части закидывается на верх колоды.Следующим движением колода, которая лежала на 4 пальцах руки наклоняется в сторону большого пальца и и часть взятых карт закидывается снизу колоды. И так далее, получается каждый раз часть взятых из колоды карт закидывается поочередно в вниз и верх колоды.
                                        Конечно riffle shuffle круче, но мы так не умеем ))
                                          0
                                          Перемешать что-то так, чтоб система заведомо начала демонстрировать хаотическое поведение можно с помощью, в частности,"преобразования пекаря".
                                          Несмотря на свою простоту, преобразование пекаря очень хорошо моделирует поведение многих реальных физических систем и иллюстрирует механизм возникновения случайности в процессах, течение которых полностью предопределено.
                                          Журнал «Квант» №4. 1989 г.

                                          На первый взгляд, есть ощущение, что тот способ, которым большинство тасует карты — и есть его разновидность:)
                                            0
                                            С другой стороны есть же шуточное правило преферанса — «дважды сдвинутая колода считается перетасованной». В отработанной колоде чаще всего идут три карты одной масти подряд. Раздачи идет по две. И после небольшого тасования вероятность игры, а не паса, повышается, а долговременное равномерное распределение по игрокам не должно от этого сильно страдать. Игра же идеально рандомной колодой скорее всего превратится в нудную череду распасов. Но увы, матаном свое ХО я подкрепить не могу.
                                              0
                                              Все верно. При хорошо перетасованной колоде несколько повышается вероятность ухода в распасы. При небрежно перетасованной — выше вероятность игры на взятки и/или удачного прикупа.

                                              Это тоже замечено. В том числе при игре вживую.

                                              Поэтому сетует на нереальность онлайновых сдач, в основном, те, кто не очень любит/умеет играть распасовки.
                                              0
                                              а карты из новой, невскрытой пачки как-то перетасованы?
                                              Пачки одинаково хорошо перетасованы между собой?
                                                0
                                                В новой пачке карты как правило упорядочены. Я посмотрел изрядное количество видео с карточными фокусами; в тех фокусах, которые начинались с распечатки новой колоды и подчеркивалось, что они упорядочены стандартным образом, использовался такой порядок. Начинается с туза масти пик, потом от двойки до десятки, валет, дама, король, потом такой же порядок с мастью бубен, потом трефы в обратном порядке от короля до туза и такой же обратный порядок от короля до туза червей. То есть начинается и заканчивается тузами, а в середине колоды два короля («kissing kings»). Рекламные карты и джокеры отдельно в самом начале.
                                                  0
                                                  Нет. В новой колоде карты идут подряд от младших к старшим
                                                    0

                                                    Нет, лежат в порядке 23456… КА с каким-то порядком мастей. Так удобнее фасовать.

                                                    0

                                                    Riffle shuffle это просто! Я прямо рекомендую освоить, меньше дня на освоение. Ну и нормальной колодой играть удобнее конечно.

                                                      0
                                                      Индийская тасовка (hindu shuffle), пожалуй, быстрее делается.
                                                        0
                                                        Но ведь она ничем принципиально не отличается от тасовки из второй гифки статьи. Только хват другой.
                                                          0
                                                          да, но у меня получается ее быстрее делать и меньше карт перекидывать за раз.
                                                          0
                                                          Я иногда так тасую карты. Даже не знал, что это «именной» способ тасовки.
                                                          –2
                                                          Совет от человека, до недавнего времени работавшего в игровой индустрии. Идеальная тасовка — это та, когда вы карты вообще в руки не берете, либо берете но играете, без каких либо ставок.
                                                            +1
                                                            То есть если дома в дурака на интерес играете, по вашей логике можно карты вообще не тасовать, тасовка уже идеальная.
                                                            0
                                                            Способ далеко не лучший. Когда мы берём колоду, мы её делим примерно в соотношении 50/50, потом половину от первой колоды мы так же делим и соединяем со второй пока первая колода не будет содержать 1-3 карты. Потом повторяем. Из-за того, что остаются подпоследовательности исходной колоды, то «корреляция» с исходной колодой будет всегда существовать. Самый надёжный способ это разбросать карты по столу, перемешать и собрать в колоду, тогда все пары исходной колоды будут разорваны, а те же самые пары в новой колоде будут более случайны.
                                                            Почему бы не рассмотреть этот вопрос с точки зрения энтропии?
                                                              0
                                                              В случае игры в дурака одному придет та, которой били, а другому — та, которую били, и это будет совсем не случайно.
                                                              А меня бабушка приучила сдавать всегда по две карты. Видимо как раз для того чтобы не было такого попадания. Я редко, но сталкивался с людьми, которые тоже сдавали парами.

                                                              Компьютеры убили карты, раньше без карт и недели не проходило, а теперь хорошо если раз в год пуля.
                                                                0
                                                                Компьютеры убили карты, раньше без карт и недели не проходило, а теперь хорошо если раз в год пуля.

                                                                В студенческие годы вечера не проходило, чтобы не расписать одну-две пульки :) Кроме, разве что, сессии.
                                                                  0
                                                                  В преф именно так и сдаётся, именно, чтобы избежать случайного расклада. Полностью случайных раскладов в префе быть не должно, должны быть перекосы в мастях, иначе играть будет не интересно/долго.
                                                                  0
                                                                  картонные карты так не получится шафлить

                                                                  получилось

                                                                    0

                                                                    Карточные игры далеко не ограничиваются французской/испанской колодой.


                                                                    Это тоже карточная игра

                                                                    image


                                                                    А еще карты рачительные хозяева пакуют в специальные кармашки или даже ламинируют. Что вовсе не облегчает процесс.

                                                                      +1
                                                                      Не более, чем терминологическая путаница. Всё это называют одним термином «карточные игры». Хотя одни из них «игры с использованием игральных карт», а другие — «игры с использованием карточек».
                                                                        –2

                                                                        Если уж буквоедствовать, то правильно.


                                                                        Посмотрите, на корневой коммент ветки, видите цитату из поста?
                                                                        Логично предположить, что она относится к телу поста, не правда ли?
                                                                        А если нажать CTRL+F и ввести процитированное в появившееся окошечко, то вы найдете соответствующее вхождение, и анимированную картинку рядом с ним.
                                                                        Обратите внимание на характерные толщину и структуру карт: это явно карты на картоне, по поводу которых не может быть споров, точно ли это сверхтонкий картон или, таки, сверхплотная бумага.


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


                                                                        Я всего лишь показал уже другие, но все еще картонные, карты. А вы пытаетесь меня убедить, что 150 и 3000 мкм — это


                                                                        Не более, чем терминологическая путаница

                                                                        Не надо так.

                                                                          0
                                                                          В таком случае, чтобы не было терминологической путаницы, давайте обусловимся различать собственно «карточные игры», «коллекционные карточные игры», «настольные стратегические карточные игры» и другие.

                                                                          Если в некоторых ККИ перетасовать колоду из 70-100 карточек еще можно, то из 300+ уже затруднительно.

                                                                          Что уж говорить о НСКИ… перетасовать десятки тайтлов толстого картона просто нереально. Остается их только «перемешивать».

                                                                          А теперь, внимание! Смотрим на заголовок статьи и видим там слово «тасовка». Из чего следует вывод, что автор имел в виду игры классической «французской» колодой (52 листа + джокеры). Или «русской» (36 листов) или «пикетной» (она же «преферансная» — 32 листа). Или ККИ с относительно небольшим набором карт. Но никак не игры типа «Каркассон» с его толстыми тайтлами.

                                                                          Лично я ничего не имею против ККИ и НСКИ. Но лучше в некоторых случаях тасовать, а в других, всё же, — перемешивать.
                                                                            –1

                                                                            Именно! Рад, что мы поняли друг друга.


                                                                            Впрочем, того, что автор ветки решил придраться, даже не посмотрев, к чему именно, это никак не отменяет.

                                                                              0
                                                                              Давайте же простим его, ибо я тоже не сразу понял, что Вы имеете в виду.

                                                                              Это колоды для кардистри или для казино делают многослойными с пластиковым покрытием и углеволоконными вставками. А у нас Ленинградская картонная фабрика выпускала простые картонные карты с лаковым покрытием. Зато очень качественные и с художественным оформлением. «Времена года» были первой колодой в моей коллекции (так что я тоже в некотором роде фанат ККИ :) ). Пока ее не закрыли. А жаль. Никакие колоды от Пьятника не идут в сравнение с ней или с другими колодами.
                                                                                0

                                                                                Каджит не в обиде ) Он отлично помнит, что иногда ход его мыслей слишком заковырист, а косноязычие слишком велико.

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое