Физическая колода перемешивается несовершенно, и обычно это сходит с рук. У цифровой такого запаса нет. Её перемешивают несколько строк кода, которые либо дают каждый порядок с равной вероятностью, либо нет, и разница никогда не видна на экране — она проявляется в таблице частот после нескольких миллионов раздач. Есть один стандартный способ сделать это правильно, один известный способ ошибиться, который выглядит тщательнее, и один реальный предел, не связанный ни с тем, ни с другим.
Масштаб задачи
Колоду из 52 карт можно расположить 52! способами: 52 × 51 × 50 и так далее до 1, что даёт примерно 8.07 × 1067. Calling a deck shuffled is a claim about that number: that each of those orderings is exactly as likely as every other. It is a stronger claim than it sounds, and it is what the code must deliver.
Fisher–Yates, за 51 обмен
Правильный алгоритм — Fisher–Yates, и его достаточно коротко изложить в одном предложении. Ведём счётчик i от последней карты до второй. На каждом шаге выбираем позицию j равномерно случайно от 0 до включительно i, меняем местами карты в позициях i и j, переходим к следующему шагу. Для 52 карт это 51 обмен и 51 случайное число, и колода перемешивается за один проход.
Почему это работает, видно из подсчёта. На первом шаге есть 52 варианта выбора j, на втором 51, на третьем 50, и так до 2 на последнем шаге: 52! различных прогонов алгоритма, каждый равновероятен, потому что каждый выбор был равномерным. Порядков тоже ровно 52!, и никакие два прогона не дают один и тот же. Взаимно однозначное соответствие между равновероятными прогонами и возможными порядками — это и есть равномерное перемешивание, так что перемешивание равномерно — не приблизительно, а точно.
Ошибка на единицу, которая его ломает
Соблазнительный вариант выбирает j из всей колоды каждый раз — от 0 до 51, — а не от 0 до i. It looks like it should be better, because every card can move anywhere at every step. It is not uniform, and the counting argument shows why immediately: there are now 5252 равновероятных прогонов вместо 52!, и 5252 не делится на 52!, поэтому порядки никак не могут распределиться поровну.
Три карты делают это достаточно наглядным, чтобы проверить вручную. У сломанной версии 33 = 27 равновероятных прогонов, распределённых по 6 порядкам, что давало бы по 4.5 на каждый. Вместо этого три порядка получают по 5 прогонов, а три — по 4, так что один набор на 25% вероятнее другого. При четырёх картах хуже: 44 = 256 прогонов на 24 порядка, и количество колеблется от 8 до 15, то есть самый вероятный порядок выпадает почти вдвое чаще самого редкого. Смещение не уменьшается с ростом колоды. Просто перестаёт быть тем, что можно заметить.
Где настоящий предел
Правильное перемешивание всё равно не лучше случайных чисел, которые в него поступают, и здесь у браузерной или телефонной игры есть настоящее ограничение. Math.random в движке Chromium, внутри которого работают эти игры, генератор называется xorshift128+ и хранит 128 бит состояния. Это ограничивает число различных последовательностей, которые он может выдать, числом 2128, то есть около 3.4 × 1038. Set that against 8.07 × 1067 порядков, а доля достижимых составляет около 4 × 10-30. Almost every ordering of the deck cannot be produced at all.
Звучит смертельно, но это не так, и именно это различие — полезная часть статьи. Рука в видеопокере никогда не показывает порядок из 52 карт. Она показывает пять карт, а затем до пяти дополнительных. Есть 52 × 51 × 50 × 49 × 48 = 311,875,200 упорядоченных раздач из пяти карт и 2,598,960 различных комбинаций из пяти карт. Размазав 3.4 × 1038 возможных начальных состояний по 311 миллионам раздач, и у каждой раздачи всё ещё порядка 1030 состояний за ней — равномерно с гораздо большей точностью, чем любая игра способна измерить. Слабость Math.random в том, что её будущий выход предсказуем для всякого, кто знает внутреннее состояние, — поэтому она неподходящий инструмент там, где на кону деньги, и вполне подходящий для раздачи пяти карт в тренировочной игре.
Что не переходит от одной раздачи к другой
Из равномерности следуют две детали, и именно там люди ищут подстроенную раздачу.
Первое: ничего не переживает раздачу. Новая колода собирается и перемешивается с нуля перед каждой раздачей, так что предыдущая раздача ничего не добавляет — поэтому подсчёт карт не работает за автоматом, и почему долгая сухая серия не повышает шансов следующей раздачи на выплату.
Второе: не имеет значения, с какого конца колоды берутся карты. Реализация может раздавать пять карт сверху, а карты для добора брать снизу, что звучит так, будто это должно что-то значить. После равномерного перемешивания каждая позиция в колоде имеет одинаковое распределение, так что верх, низ и середина неразличимы, а выбор — удобство для того, кто писал код, а не факт об игре. То же относится и к двойному перемешиванию: равномерное перемешивание уже равномерной колоды остаётся равномерным, так что второй проход ничего не даёт.
Качество перемешивания и честность раздачи — разные вопросы, и легко их перепутать. Игра может запустить классический Fisher–Yates над колодой из 52 карт, а затем изменить одну из пяти карт перед тем, как вывести её на экран, и по самому перемешиванию это никак не будет видно. Равномерно ли перемешивание, можно проверить по нескольким строкам кода. А то, что вы видите на экране, — неизменённый результат перемешивания, — уже другой вопрос, и для игры на фишках без регулятора честный ответ часто будет «нет», в том числе и для игры ниже.
Итог короткий. Fisher–Yates от 0 до i, 51 обмен, каждый порядок равновероятен; вариант со всей колодой смещён, и незаметно — начиная примерно с пяти карт. Генератор не может достичь большинства порядков полной колоды, но для игры на пять карт это несущественно. Ничто из этого не отвечает на вопрос, что происходит между перемешиванием и экраном, — а это единственная часть цифровой раздачи, в которой стоит сомневаться.
Video Poker: Jacks or Better перемешивает ровно так, как описано выше: свежая колода из 52 карт перед каждой раздачей, Fisher–Yates от 0 до i, 51 обмен, предназначено для отработки Math.random. It is also a free-chip practice game rather than a model of a regulated machine, so the paragraph above applies to it: the five dealt cards are not always the shuffle's untouched output. A dead deal is sometimes nudged towards a pair or a four-card flush, more often after a run of losses or when your balance is nearly gone, and a deal that already contains a pair or better is left alone. The draw is untouched — replacement cards come straight off the remaining shuffled deck — so the hold decisions you practise are the real ones even though hands arrive more kindly than the maths would send them. Use it to drill приоритетов удержания а не для оценки того, как часто выпадают раздачи. Здесь четыре автомата, у каждого своя неизменная таблица выплат: Jacks or Better с самого начала, Deuces Wild с уровня 3, Bonus Poker с уровня 8 и Double Bonus с уровня 15, а Triple и Five Play — с уровня 10. Вы начинаете с 1,000 фишек, ставите 5, 10, 20 или 50 за раздачу и раз в день получаете ещё 200; подсказки стратегии подсвечивают рекомендуемое удержание. Работает офлайн; фишки не имеют денежной стоимости.