Карточные дилеры создают уникальную колоду при каждой тасовке, а компьютеры не могут это повторить

Если вы когда-нибудь перемешивали колоду игральных карт, то, скорее всего, создали тем самым уникальную колоду. То есть, вероятно, вы единственный человек, который когда-либо раскладывал карты именно в таком порядке. Хотя это утверждение звучит невероятно, оно прекрасно иллюстрирует, как быстро большие числа могут проникнуть в повседневные ситуации — иногда с серьёзными и неприятными последствиями, как обнаружили разработчики одного онлайн-покера в конце 1990-х годов.

Математику тасовки карт довольно просто объяснить. Чтобы рассчитать, сколько вариантов расстановки может быть у 52 игральных карт, необходимо пройти все возможные варианты тасовки. Логично, что одна из 52 карт кладётся сверху, и как только это определено, для карты под ней остаётся только 51 возможность. Следующая карта имеет только 50 возможных вариантов, и так далее. Таким образом, 52 карты в колоде можно расположить 52 × 51 × 50 × ... × 2 × 1 = 52! различными способами.

Если вы выполните умножение и округлите ответ, то получите число с 67 нулями. Это более чем в квадриллион раз больше количества атомов на Земле.

Из этого становится понятно, что существует очень много различных способов расставить 52 игральные карты. Однако чтобы выяснить, насколько вероятно, что другой человек в мире случайно создаст ту же последовательность карт при тасовании, недостаточно просто поделить 1 на 52! Это число просто покажет, насколько вероятно получить одну конкретную последовательность карт.

Есть ещё один, более тонкий вопрос: насколько вероятно, что два или более человека в мире случайно перетасуют колоду карт одинаково?

Необычайная редкость каждого перемешивания

Этот вопрос напоминает парадокс дней рождения. Он работает по тому же принципу: довольно маловероятно, что у конкретного ученика в классе день рождения попадёт определённую дату — в группе из 30 человек вероятность этого составляет 1 − (364 / 365)³⁰ ≈ 7,9%. Однако вероятность того, что два ученика родились в один и тот же день, составляет более 70%. Причина этого кажущегося несоответствия заключается в том, что люди обычно недооценивают количество возможных пар учеников. Из 30 учеников можно сформировать 435 пар. Если понять это, то вероятность того, что каждая пара учеников родилась в разные дни, уже не покажется такой высокой.

Если вы хотите узнать, насколько вероятно случайным образом перетасовать колоду карт так же, как любой другой человек в мире, есть несколько способов это сделать. Один из них заключается в том, чтобы сначала вычислить вероятность противоположного события, а затем вычесть этот результат из 1. Это означает, что сначала нужно вычислить, насколько вероятно, что все люди в мире создадут совершенно новую комбинацию при перемешивании: у первого человека вероятность этого события равна 1, у второго — (52! – 1) / 52!, у третьего — (52! – 2) / 52! и так далее. Затем нужно вычесть этот результат из 1.

Если в мире проживает восемь миллиардов человек, вероятность того, что несколько человек создадут одинаковую комбинацию карт, можно рассчитать следующим образом:

Проблема в том, что мой калькулятор (или, вернее, онлайн-программа Wolfram|Alpha) не справляется с вычислением этой формулы. Поэтому я вынужден полагаться на очень приблизительную оценку этой вероятности:

Это означает, что вероятность того, что два или более человека в мире создадут одинаковую колоду карт, составляет менее 0,0000..[много нулей]..08 процента — число, которое отличается от 0 только в 47-м знаке после запятой.

Надеюсь, эта иллюстрация убедила всех в том, что вероятность того, что несколько человек в мире случайно создадут одинаковую колоду карт, перетасовывая их, крайне мала. Но вы, вероятно, перетасовывали карты много раз в своей жизни, а не только один раз. Так как же изменится результат, если предположить, что каждый человек перетасовывает примерно 100 колод карт за свою жизнь? Заменив восемь миллиардов в предыдущей оценке на 800 миллиардов, мы обнаруживаем, что вероятность в этом случае составляет менее 8 × 10⁻⁴³ процентов.

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

Кстати, если мы рассмотрим всех людей, которые живут или когда-либо жили на Земле — по некоторым оценкам, около 117 миллиардов человек — каждый из которых перетасовал колоду карт примерно 100 раз (что маловероятно, учитывая, что наш вид не так давно начал использовать игральные карты), то вероятность того, что одна и та же комбинация была создана несколько раз, составляет менее 1,7 × 10⁻⁴⁰ процентов.

Это ясно показывает: действительно крайне маловероятно, что два человека за всю историю человечества когда-либо получали одинаковые колоды карт после тасовки — по крайней мере, если предположить, что они тасовали карты с большой тщательностью. Это иллюстрирует, насколько велико число 52! и как огромно количество возможностей для расстановки 52 карт.

Смотрим и плачем

Значительность числа 52! не только вдохновляет на размышления, но и создаёт ряд серьёзных практических проблем для разработчиков онлайн-игр. В онлайн-покере могут быть задействованы большие суммы денег, поэтому крайне важно, чтобы эти игры были максимально безопасными и честными. Любые недостатки или лазейки могут быть использованы мошенниками или казино против игроков.

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

В конце 1990-х годов платформа разработки ASF Software предоставила нескольким провайдерам онлайн-покера, таким как Planet Poker, алгоритмы тасовки карт. Платформа даже разместила алгоритм на своём веб-сайте в качестве доказательства надёжности программы. И эта публикация привлекла внимание некоторых сотрудников IT-компании Reliable Software Technologies. «Как только мы увидели алгоритм тасовки, мы начали подозревать, что в нём может скрываться проблема. Небольшое расследование доказало, что это предположение было верным», — написали несколько сотрудников в посте на веб-сайте по разработке программного обеспечения.

Алгоритм начинал с упорядоченной колоды карт, а затем шаг за шагом менял местами по две карты. Для этого программа использовала генератор случайных чисел, связанный с системным временем компьютера. Но у этого метода есть несколько ограничений. Во-первых, механизм перестановки был реализован таким образом, что некоторые комбинации карт были предпочтительнее и появлялись чаще, чем другие. Во-вторых, система связывает генерацию чисел с количеством секунд, прошедших с полуночи, сбрасываясь один раз в день, что ещё больше ограничивает возможные случайные значения. Команда Reliable Software Technologies обнаружила, что таким образом можно было сгенерировать только около 86 миллионов комбинаций.

Затем программисты поняли, что, поскольку система привязана к часам для рандомизации перетасовок, расположение карт может быть ещё больше ограничено с учётом хронометража. Простая синхронизация их собственной программы с системными часами сократила возможности до всего лишь 200 000 потенциальных колод, которые мог сгенерировать алгоритм. «После этого шага мы поняли, что владеем системой, поскольку поиск в этом небольшом наборе перетасовок является тривиальным и может быть выполнен на ПК в режиме реального времени», — написали они. Напомним, что это было ещё в 1990-х годах, когда компьютеры были значительно менее мощными, чем сегодня.

Сотрудники Reliable Software Technologies сообщили об этих недостатках разработчикам алгоритма, которые немедленно его переработали. Сегодня многие сайты онлайн-покера используют алгоритм тасования Фишера-Йетса, также называемый тасованием Кнута (Knuth shuffle — звучит как название танца). Он прост в реализации и даёт удовлетворительные результаты.

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