Немного о методах шаффла.

[zuko3d]

Если вам не очень хочется вникать в рассуждения - снизу есть "сухие" результаты

 

Думаю, всем знакомо это ощущение: раздаёшь себе 10-15 земель, проигрываешь игру и получаешь ценный совет от товарищей: "Надо бы тебе лучше шаффлиться!" Я решил проверить, какие методы шаффла и как влияют на итоговое распределение карт. Заранее предупрежу, что опираюсь я здесь только на статистику и только на честные методы. Так что не забывайте, что всё это работает лишь на длинной дистанции, а не в рамках одной отдельно взятой партии.

 

Методы оценки

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

Первым делом хотелось использовать энтропию (p(i) - вероятность некой карты оказаться на позиции i после шаффла). Для каждой карты в изначальной деке я считал энтропию, брал минимум по всем и смотрел, что же выходит. А выходило скучно - почти всегда энропия была выше 80%, даже для "заведомо плохих" методов (наприме - подснятие). Поэтому такую метрику я отбросил.

Далее я стал считать "разрушенные связи" (способом оценивают качество шаффла в покере, например). Суть метода в том, что мы смотрим, сколько пар карт являются соседями как до шаффла, так и после него. Для идеального случая это число должно было быть равно 1. Метрика интересная, но её как-то мало, да и не совсем ясно, чем она поможет "в жизни".

Поэтому (по совету друга) я подошёл ближе к проблеме распределения земель и сделал так: берём деку из 24 земель на 60 карт, шаффлим задуманным методом. После этого берём 5-10 подряд идущих карт, считаем соотношение земель к размеру выборки. Смотрим разницу между тем, что получилось на практике и тем, что должно быть "в идеале". Делаем, например, 1000 таких выборок, находим дискретное распределение этих ошибок. Находим его мат. ожидание. Вот эту-то величину мы и будем использовать в качестве основного "мерила качества". Чем она меньше - тем лучше.

 

Как вычислять эту оценку?

Я написал небольшую программу, которая всё это моделирует. Существует мнение, что "случайности не случайны" (с). А если быть точным - то у компьютерных генераторов случайных чисел ограничен "запас случайности". Для того генератора, которым я пользовался, этот запас равен 2^32, т.е. 4 миллиарда разных значений. Вполне сносно, чтобы проверить какие-то теории. Сами числа распределены равномерно. Да, можно было бы использовать random.org или некие спец. методы - но здесь это было бы лишним.

 

Простые методы шаффла

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

 

Cut

Он же - подснятие. Все пары карт кроме одной (той, по которой идёт подснятие) остаются лежать рядом до и после такого "шаффла". Тем не менее, энтропия у такого метода максимальная (если выбирать место для "среза" случайным образом), т.е. после подснятия заранее выбранная вами карта может оказаться на любом месте в колоде, причём везде - с одинаковой вероятностью.

Допустим, дека постакана (после декчека, ну или в начале турнира). Распределение "отклонений от идеала" будет вот таким:

Мат. ожидание ошибки - 42%.

Поясню: если мы будем выбирать, например, X подряд идущих карт, то с вероятностю 38% мы будем иметь ошибку, равную 0.42. То есть если в идеале мы хотим получить соотношение земли/карты 0.4, то здесь это соотношение будет либо 0, либо 0.84 с вероятностью 38%. Т.е. больше чем в трети случаев мы будем видеть либо набор только из земель, либо почти полностью из не-земель. Очевидно, плохой метод шаффла - но мне он нравится в качестве "плохого примера" для объяснения.

 

Riffle Shuffle

При идеальном исполнении колода сначала делится на две части по 30 карт (напомню - мы рассматриваем случай деки 24 земель на 60 карт) и карты будут лежать по очереди "одна из левой части, одна из правой". Идеальное исполнение нам не нужно (да и сложно это), так что предположим, что иногда карты могут "слипаться" и уходить по две подряд из одной половинки.

Опять же - предположим, что наша дека постакана. Тогда мат. ожидание ошибки будет равно 40%. Это тоже очень много, и об этом будет подробно рассказано ниже.

 

Riffle-Cut

Берём в левую руку колоду, правой "отщепляем" от неё часть и "вставляем" её в левую часть. Это некая смесь двух предыдущих методов. Очень часто используется ввиду своей простоты исполнения. У метода есть два важных параметра: как много карт отщеплять и насколько большое пересечение делать между отщеплённой частью и частью из левой руки. На эти вопросы я отвечу позже, когда буду более подробно рассматривать полноценный шаффл, а не разовое действие.

Если нам принесли деку после декчека и мы сделаем один рифл-кат, то распреледение ошибки будет вот таким:

(обе части колоды отличаются по размеру на 10-15%, доля пересечения варьируется от "почти нисколько" до "полное пересечение")

Мат. ожидание ошибки у такого метода равно 24%.

 

Pile Shuffle

Разложить по кучкам свои карты - дело полезное. Существуют некоторые мифы по этому поводу. Понятное дело, что сам по себе этот метод имеет нулевую энтропию (иными словами: положение каждой карты в колоде после разложения по кучкам известно абсолютно точно). Тем не менее - этот метод полезен чтобы перед началом игры удостовериться в правильном количестве карт в деке. Лично меня и моих знакомых спасало не раз.

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

 

Нормальные методы шаффла

Сразу скажу, что все перечисленные ниже методы обладают (почти) максимальной энтропией. А вот если вы вдруг используете для шаффла метод с очень низкой энтропией, да ещё и умышленно - это читинг.

 

Рифл-кат несколько раз

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

Допустим, мы делаем не особо аккуратный кат (в левой руке будет от трети до двух третей деки), и потом не особо аккуратное соединение частей (пересечение может быть как полным, так и всего по одной карте). Процесс этот будем повторять 5 раз (рисунок слева, мат. ожидание 13%) и 15 раз (рисунок справа, мат. ожидание те же 13%).

 

Теперь будем выполнять кат более аккуратно (делить на почти одинаковые половинки) и соединять будем так, чтобы пересекалось как можно сильнее. Для 5 раз (слева) мат. ожидание ошибки стало 14%, а для 15 (справа) осталось 13%.

 

Общая тенденция такая: чем больше раз вы делаете рифл-кат, тем меньше разброс ошибки (при том, что в среднем она остаётся такой же). Но нужно понимать, в какой момент остановиться. В один момент распределение ошибок начинает очень сильно напоминать нормальное (на левых графиках распределение немного вытянулось вправо, а вот на правых графиках всё симметрично). Обычно - после 10-15 рифл-катов распределение становилось именно таким, так что делать больше 15 рифлов не советую - это просто трата вашего времени. При этом "аккуратность" исполнения рифл-катов влияет слабо. Нет смысла стараться делить на две почти одинаковые половинки.

Отдельно замечу, что после 2х рифл-катов энтропия будет лишь ~70% от максимума, а вот после 3х - уже почти максимум (больше, чем 99%). Так что если вы, например, пожертвовали фечку - вам достаточно сделать рифл-кат всего 3 раза. И не нужно больше (энтропия и так почти максимальна) - экономьте время. В форматах с тоннами фечек это важно.

 

Разложить по кучкам, а потом рифл-кат несколько раз

Я не буду здесь описывать все сочетания из параметров такого шаффла (это было ну очень скучно читать) - приведу только один пример. Если кому-то захочется больше - пишите, мне не сложно потом накидать ещё табличек.

Итак: раскладываем на 6 кучек, потом делаем 15+ рифл-катов (мат. ожидание 13%):

Я взял этот пример потому, что (насколько мне известно) это самый популярный метод шаффла среди игроков. Хороший рифл(не рафйл-кат, а именно рифл) делать умеют далеко не все, потому и не делают.

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

При изменении количества кучек (кто-то раскладывает на 7, кто-то на 8 и т.п.) распределение почти не изменяется.

 

Несколько раз Riffle Shuffle

Вот здесь вас ожидает неожиданное открытие. Дело в том, что несмотря на то, что метод обладает такой же высокой энтропией - между собой карты не так хорошо меняют порядок, как в других случаях. Поначалу кажется, что уже после первого рифла все постаканные карты будут разъеденены. Что может пойти не так?.. Но вот после второго некоторые из карт возвращаются на своё место. А если проводить все рифлы идеально, то после нескольких таких идеальных рифлов дека вообще примет своё изначальное состояние. Т.е. все постаканные земли опять будут постаканы. А если говорить в числах, то даже после 30 (неидеальных) рифлов мат. ожидание ошибки будет 19%. И лишь после 50ти рифлов оно станет равно 13%.

В итоге имеем, что этот метод:

• Портит карты
  
• Не даёт нормального распределения карт по деке
  

Здесь наверняка будет резонный вопрос: "А почему его тогда в покере применяют?" Ответ простой: в покере важна энтропия, скорость исполнения метода (хороший крупье сможет за десять секунд исполнить рифлов пять) и разрушение связей (карты, лежавшие рядом, не должны лежать рядом после шаффла). И Riffle Shuffle идеально подходит под эти критерии. А то, что какие-то стаки однотипных карт не будут разбиты после 10ти рифлов - в покере никого не интересует, ибо там нет однотипных карт (можно, конечно, говорить про масти - но это уже отдельная тема).

 

Результат

Подведу итог (напомню, что везде использовалась дека в 24 земли на 60 карт):

• Раскладывать на кучки имеет смысл только в целях подсчёта карт. Распределение земель по деке от этого не улучшается (если вы, конечно, помимо этого ещё используете другой метод шаффла).
  
• После взрыва фечки достаточно сделать всего 3 рифл-ката чтобы дека была достаточно рандомизирована. Аналогично - достаточно сделать всего 3 рифл-ката с декой оппонента перед началом игры дабы (частично) обезопасить себя от читеров.
  
• Рифл-кат уже после пяти раз даёт неплохое распределение земель по деке. Делать его больше 15 раз - трата времени.
  
• Чистый рифл (не рифл-кат) плохо распределяет земли по деке. Нужно больше пятидесяти заходов для того, чтобы добиться результата, аналогичного десяти рифл-катам.
  

 

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

 

UPD: поправил графики, прошлый сервер с картинками умер.

Изменено 7 июня 2017 пользователем zuko3d

[dmitry medvedev]

Спасибо, познавательно. Есть еще такое раскладывание на n кучек, где карты (обычно начиная с n+1'й) выкладываются не по порядку, а рандомно. Этим способом, например, Карстен пользуется, тоже можно попробовать как-то промоделировать. Там скорее всего существует некоторый перекос в сторону более удобных вариантов, но пусть будет хотя бы идеальный случай, где для каждой карты вероятности попадания в любую кучку одинаковы. Кучки в конце, соответственно, тоже складываются в случайном порядке.

 

Ну и riffle — он все-таки рифл

Изменено 31 июля 2016 пользователем dmitry medvedev

[Dzaar]

Мой внутренний математик получил невероятное наслаждение от статистики и таблиц. Большой плюс.

[Texen]

Получил подтверждение, что разложить на 8 кучек для подсчёта карт и 3-5 раз порифлить - отличный план! Всегда так делал.

[Nailus_wylde]

Всегда подозревал, что идеальный рифл*N скорее вреден, чем полезен. Сам перед партией всегда ровно один раз раскладываю по кучкам, потом делаю 5-7 намеренно неидеальных риффлов. В отличие от рифл-ката обычный рифл разлепляет карты, что полезно. За статью жирный плюс!

PS когда уже в правилах черным по белому запретят пайл-шаффл больше одного раза за партию?! Отдельные уникумы к муллигану до 5 минут 5-7 от таймера съедают...

Изменено 31 июля 2016 пользователем Nailus_wylde

[zuko3d]

Ну и riffle — он все-таки рифл

Да, точно. Не знаю, почему я так привык говорить. Поправлю в статье чуть позже.

 

PS когда уже в правилах черным по белому запретят пайл-шаффл больше одного раза за партию?! Отдельные уникумы к муллигану до 5 минут 5-7 от таймера съедают...

Есть подозрение, что никогда. Потому что при попытках формализовать этот процесс возникают сложности. Да и есть пока ещё проблемы посерьёзнее, на всё рук не хватит.

 

В отличие от рифл-ката обычный рифл разлепляет карты, что полезно.

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

[konalt]

Всегда подозревал, что идеальный рифл*N скорее вреден, чем полезен. Сам перед партией всегда ровно один раз раскладываю по кучкам, потом делаю 5-7 намеренно неидеальных риффлов. В отличие от рифл-ката обычный рифл разлепляет карты, что полезно. За статью жирный плюс!

PS когда уже в правилах черным по белому запретят пайл-шаффл больше одного раза за партию?! Отдельные уникумы к муллигану до 5 минут 5-7 от таймера съедают...

 

Предигровые процедуры должны занимать не более трёх минут, если оппонент шафлится впритык по времени, то стоит позвать судью на любом упп)

[NortUS]

Предигровые процедуры должны занимать не более трёх минут, если оппонент шафлится впритык по времени, то стоит позвать судью на любом упп)

Один из самых великих мифов среди игроков. Про три минуты ни в одном документе не написано.

[sccblazer]

Поэтому (по совету друга) я подошёл ближе к проблеме распределения земель и сделал так: берём деку из 24 земель на 60 карт, шаффлим задуманным методом. После этого берём 5-10 подряд идущих карт, считаем соотношение земель к размеру выборки. Смотрим разницу между тем, что получилось на практике и тем, что должно быть "в идеале". Делаем, например, 1000 таких выборок, находим дискретное распределение этих ошибок. Находим его мат. ожидание. Вот эту-то величину мы и будем использовать в качестве основного "мерила качества". Чем она меньше - тем лучше.

 

Я правильно понимаю, что mana weaving а-ля "2 спела - 1 земля" покажет идеальный шаффл по такому тесту?

Или я что-то не понял, тогда прошу добавить формул, чтобы было яснее.

[zuko3d]

Я правильно понимаю, что mana weaving а-ля "2 спела - 1 земля" покажет идеальный шаффл по такому тесту?

Или я что-то не понял, тогда прошу добавить формул, чтобы было яснее.

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

 

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

 

Какие формулы стоит добавить? Что нужно подробнее объяснить или просто пояснить?

[EpicWinner]

Всё бы ничего, да глаза вытекли от первого же "райфл" и читать не смог. Если что, даже гугл-переводчик умеет в произношение слов.

[Revognah]

Большое спасибо за статью.

Польза.

[sccblazer]

zuko3d Но про энтропию написано:

Для каждой карты в изначальной деке я считал энтропию, брал минимум по всем и смотрел, что же выходит. А выходило скучно - почти всегда энропия была выше 80%, даже для "заведомо плохих" методов (наприме - подснятие). Поэтому такую метрику я отбросил.

Так отбросил или не отбросил?

[ShadowJackJC]

А если раскладывание по кучкам делать рандомным образом, а не по порядку - это добавляет эффективности?

Ну и интересно было бы увидеть подсчеты для ЕДХ колод, взять 35 земель и 64 не земли. Просто в ЕДХ в силу толщины колоды проблема шаффла и земель даже более интересна.

[zuko3d]

zuko3d Но про энтропию написано: .....

 

Так отбросил или не отбросил?

 

Я её считал (её вычисление не занимало много времени), но не опирался на неё при оценке "хороших" и "плохих" методов.

[sccblazer]

Немного некропостинга - наткнулся на статью - http://www.dartmouth.edu/~chance/teaching_aids/Mann.pdf

Вот тут действительно научный подход, любителям математики рекомендую читать полностью.

Для остальных:

TL;DR - В статье в итоге для размешивания 52-карточной колоды рекомендуют делать 12 рифлов, также приведена общая формула зависимости от количества карт в колоде. Итого:

 

для 40 карт - 11 рифлов

для 60 карт - 12 рифлов

для 99 карт (привет ЕДХ) - 13-14 рифлов

[zuko3d]

Немного некропостинга - наткнулся на статью - http://www.dartmouth.edu/~chance/teaching_aids/Mann.pdf

Вот тут действительно научный подход, любителям математики рекомендую читать полностью.

Спасибо, статья хорошая и интересная.

 

По поводу "других результатов": там используется другой способ оценки. Нельзя сказать, что она (оценка) "более строгая" или "более качественная". Она просто другая. И она подразумевает, что все карты - разные по своей роли. Если бы мы считали количество возрастающих последовательностей (я бы именно так перевёл "rising sequences") с учётом "одинаковости" карт (т.е. пользовались бы отношением частичного порядка, а не строгого, как в статье), то и результаты были бы другие. Если найду время - попробую посчитать, вдруг что-то интересное получится.

Изменено 11 августа 2016 пользователем zuko3d

[Mordodrukow]

Мне тема показалась наиболее "профильной", поэтому задам вопрос здесь.

 

В ЕДХ, как известно, 99 карт в колоде. Я человек не очень ловкий, поэтому для шаффла беру половину деки, делаю несколько рифлов, потом делаю то же самое со второй половиной. Потом делю их снова пополам, меняю местами верхние половинки из кучки номер 1 и номер 2. Снова делаю рифлы.

 

Вопрос такой: это вообще легально или на турнире могут по рукам дать за это?

[Garyou]

Мне тема показалась наиболее "профильной", поэтому задам вопрос здесь.

 

В ЕДХ, как известно, 99 карт в колоде. Я человек не очень ловкий, поэтому для шаффла беру половину деки, делаю несколько рифлов, потом делаю то же самое со второй половиной. Потом делю их снова пополам, меняю местами верхние половинки из кучки номер 1 и номер 2. Снова делаю рифлы.

 

Вопрос такой: это вообще легально или на турнире могут по рукам дать за это?

Как вариант еще - брать половину дечки, делить ее пополам, риффлить, брать половину второй половины дечки, риффлить с 3/4 колоды, брать от 3/4 половину, риффлить её с оставшейся 1/4. Короче - играться что с чем риффлишь. Никогда не было даже косых взглядов. Многие так и мешают. Да и риффл, емнип, является достаточно рандомизирующим способом, особенно если повторить его 2-3 раза до каждой смены половинок. Так что, ИМХО, всё в порядке.

[Vsdg]

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

[Ralgha]

Очень круто, спасибо!!! (ушел тестить)

[Gallexy]

картинки поломались.

[VARIV]

Много раз по разному тестил шафл. Но лучше раскладывания 2-3 раз на по 7 нет ничего.

При остальных шафлах были участки в деке где 3-4-5-6-7 земель лежало подряд что не есть хорошо. плохо что визарда запретили этот метод...

[Texen]

Много раз по разному тестил шафл. Но лучше раскладывания 2-3 раз на по 7 нет ничего.

При остальных шафлах были участки в деке где 3-4-5-6-7 земель лежало подряд что не есть хорошо. плохо что визарда запретили этот метод...

Группы по несклько земель в целом вписываются в понятие рандомизации, если нет чёткого паттерна.

[sccblazer]

Задача шафла не сделать "хорошо", а сделать случайно. А в этом случае подряд идущие земли или не земли неизбежны.