От редактора: сегодня у нас статья Игоря Бугаенко (BioLogIn) о шаффле колоды и о том, почему все ругаются на МОДОшный шаффлер
В процессе подготовки к нацу я изрядно пострадал "от шаффлера" MTGO, где мои несчастные колоды от души "крючило" и "флудило" (как будто у них было мало проблем без шаффлера =\). Вот я и решил наконец разобраться с тем, насколько шаффлы в реальности отличаются от "настоящего" рандома. Результаты оказались довольно интересны, но оформить это в качестве более-менее связного текста я собрался только сейчас. Надеюсь, что это поможет многим хотя бы частично избавиться от некоторых популярных иллюзий. Однако, поскольку в процессе избавления нам понадобится немного математики, то испытывающие аллергию на цифры и формулы могут пропустить всю середину и обратиться сразу с последнему абзацу.
Итак, начать нам стоит с повторения одной очень тривиальной, но важной вещи:
Случайное распределение - это не равномерное распределение.
Как это ни странно, но многие игроки в Magic the Gathering – игру, завязанную на вероятности - это простой вещи зачастую не понимают, и ругают MTGO-шаффлер на чем свет стоит, получая четвертую подряд землю с топдека. Но давайте разберемся – какова вероятность такого события в рандомизированной колоде?
Пусть у нас есть колода из n карт, среди которых есть k земель и n-k спеллов (а такую колоду очень удобно представлять как последовательность из единичек и нулей). Количество всевозможных вариантов таких последовательностей можно вычислить с помощью хорошо известного всем студентам-математикам биномиального коэффициента, обозначающегося C(n,k). Для 60 карт и 24 земель, например, это всего лишь 36052387482172425 возможных комбинаций. Чтобы оценить вероятность получить, например, пять земель подряд, нам нужно посчитать, сколько из таких последовательностей содержит 5 нулей подряд, и поделить одно число на другое. Довольно просто показать, что количество последовательностей, не содержащих m нулей подряд, можно оценить по (рекуррентной) формуле f(n,k,m)=?{i=1}^m f(n-i,k-i+1,m) (это означает суммирование значений f(n-i,k-i+1,m) по всем значениям i от единицы до m). Подставить в эту формулу разные значения и полюбоваться на большие чиселки можно вот здесь, а для случая 60 карт и 24 земли получаются вот какие числа и вероятности:
Здесь:
Lands – максимальное количество земель в кластере (идущих подряд в колоде земель)
Total – количество различных вариантов рандомизации колоды (комбинаций) без кластеров земель такого размера
Prob – вероятность выпадения комбинации без кластера такого размера
Что же означают все эти циферки? Например, то, что с вероятностью примерно две трети (63%) в рандомизированной колоде из 60 карт и 24 земель где-то есть хотя бы один кластер из четырех земель подряд. А почти в каждой третьей такой колоде (27%) встречаются пять земель подряд. Конечно, за игру вы просматриваете не всю колоду, а в среднем – чуть меньше половины (в случае драфтовой колоды из 40 карт, которая в среднем длится 7-10 ходов), но мы и не изучали вероятности присутствия в колоде нескольких таких кластеров. Похоже, шаффлер в MTGO не такой уж и "подкрученный"? Становится понятно, откуда столько ненависти в его сторону – в реальном мире мы колода рандомизируется куда менее случайными методами, и результат получается куда менее случайным... но куда более равномерным.
Как рандомизирует колоду MTGO? По словам разработчиков, они используют стандартный алгоритм из классической книги Дональда Кнута, который, просто говоря, меняет местами две случайные карты в колоде, и делает это достаточно большое число раз. Доказательство того, что этот алгоритм дает случайные результаты, было дано в середине прошлого века и с тех пор не опровергалось; случайные числа для инициализации алгоритма программисты MTGO честно берут из аппаратных шумов-задержек (/dev/random/), так что оснований подозревать слабую реализацию тоже нет - получается, что MTGO-алгоритм выдает честные "случайные" колоды. Но к шаффлу в реальности этот способ, естественно, применим плохо - пока вы поменяете местами пару сотен "случайных" карт в вашей колоде, отпущенные правилами три минуты давно истекут.
Как же увязать правила DCI (требующие от игроков "достаточно рандомизировать" свои колоды, а на competitive и professional REL - еще и мешать колоды оппонентов) и "несовершенство" доступных живым людям методов шаффла? Для ответа на этот вопрос нам будет полезно рассмотреть еще одно заблуждение (в котором до недавнего времени частично пребывал и автор этого текста). Многие верят, что раскладывание на какое-то (зависящее от размера колоды и количества земель) количество кучек (pile shuffling, table shuffling) помогает в достаточной степени рандомизировать колоду. Хотя вроде бы и очевидно, что любой детерминированный (не случайный) алгоритм шаффла не может сделать из "не рандомизированной" колоды "рандомизированную", но на практике многие об этом забывают. Вспомнить, как работает pile shuffle, можно с помощью всё той же простенькой программки – довольно очевидно, что получить равномерную последовательность таким методом можно, а вот случайной ее назвать сложно – вероятности наличия кластеров земель там совсем не те, что мы рассчитывали несколько абзацев назад. В свое время, кстати, аналогичным "исследованием" занимался и Майк Флорес, но по ссылке, как это обычно бывает у Майка, довольно много лишних букв, так что проследуйте туда на ваш страх и риск... Зато, когда я уже редактировал эту статью перед отправкой, я нашел куда более внятную работу в архиве starcity за 2002 год – даже немного удивительно, как мало изменилось за прошедшие почти 10 лет...
Так вот, наша маленькая программка делает очень простую вещь - заданное число раз раскладывает колоду (в которой изначально все земли лежат вначале\сверху) на заданное число кучек. Легко видеть, что даже "хорошие" количества кучек (например, семь, не кратное ни числу карт, ни числу земель), после нескольких итераций (например, 3) могут приводить к очень приятным для игроков (но совершенно не случайным!) распределениям земель по колоде. Но если вдруг кому-то кажется, что всё это - это руководство к читингу и обучение новым майндтрикам способам стекания колоды, то мне придется еще раз повторить - само по себе раскладывание на кучки в принципе не является способом рандомизации колоды. Если на турнире ваш оппонент несколько раз разложил колоду на кучки, и помимо этого не делал никаких случайных шаффлов ("врезки"\riffle shuffle) - зовите судью и объясняйте ему, что оппонент предоставил не рандомизированную колоду. Вне зависимости от количества кучек и карт в колоде. И наоборот, сами после одного пайл-шаффла (полезного для того, чтобы пересчитать карты и проверить протекторы) обязательно примените более "случайные" методики шаффла.
Одна из самых популярных методик "случайного" шаффла - это riffle shuffle. И оказывается, что несмотря на свою простоту, она довольно эффективно рандомизирует колоду. Математика, которая требуется, чтобы оценить количество таких шаффлов, рандомизирующих колоду, несколько менее тривиальна, чем использовавшаяся выше, и подробно изучена людьми, не имеющими к магии никакого отношения (хотя опять же при редактуре выяснилось, что и имеющие к магии отношению об этом уже писали). Нам же достаточно знать, что это число оценивается как 1.5*log_2(n). То есть для колоды из 40 карт оно чуть больше 8, а для колоды из 60 карт - около 9. А значит, 9 качественных riffle shuffle'ов в целом достаточно для рандомизации колоды.
Подводя итоги: для хорошей рандомизации колоды разложите ее разок на кучки (заодно посчитаете количество карт и проверите состояние протекторов), а затем сделайте десяток riffle shuffle'ов. А дальше всё зависит только от вас ) Удачи вам на турнирах, будьте клевыми и играйте в магию.
Игорь Бугаенко
P.S. Я хотел на закуску развенчать еще один миф и поговорить о "вреде" от 41-ой или 61-ой карты в колоде. Но на этот раз я как следует погуглил и нашел актуальную (апрель 2011) и очень тщательную работу товарища Chingsung Chang. Учитывая количество перелопаченных им данных и построенных им графиков =), мне остается только процитировать его последние абзацы:
Очевидно, что дополнительная карта минимально влияет на вероятности дрова нужной карты, особенно после первых трех-четырех дровов. По факту, этот эффект почти всегда проявляется менее чем в 1% случаев. Но очевидно, что путём добавления дополнительной карты игрок получает недостижимые в стандартных количествах карт соотношения земли\спеллы, то есть может лучше настроить процент маны в колоде. Тут добавление дополнительной карты может дать эффект от 2% до 3% в колоде из 60 карт и от 3% до 5% в колоде из 40 карт. Не используя дополнительную карту, вы ограничиваете себя более длинными "шагами" между доступными вам соотношениями земля\спелл. По факту, вы примерно удваиваете ваши возможности по настройке манабазы. А теперь позвольте спросить вас, из-за чего вы проигрываете чаще - из-за того, что не получили конкретную карту, или из-за того, что (не)получили землю в нужный момент?
_svg.png.c35e3dfdfd71cb34e41c17db8584b939.png)
_svg.thumb.png.21dfa00658016bd06b4e4e154e743a1c.png)
Да, можно.