Если вам не очень хочется вникать в рассуждения - снизу есть "сухие" результаты
Думаю, всем знакомо это ощущение: раздаёшь себе 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: поправил графики, прошлый сервер с картинками умер.
