Перемешивание

Итак, как же вы реализуете перемешивание колоды карт?

Я задумался над этим, когда прочёл о мучениях Майка Поупа с алгоритмами перемешивания карт. Вот цитата из блога Майка Поупа:

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

Мне этот подход показался странным, но в отличие от Майка у меня программистский бэкграунд. Я обратился к своему старому другу - циклу. Предположим, что у нас есть массив из 52 элементов, представляющих 52 карты в колоде.

Здесь и далее код на C#. Внизу статьи есть небольшая справка по используемым функциям.

var rand = new Random();
for (int i = cards.Length - 1; i > 0; i--)
{
  int n = rand.Next(i + 1);
  int temp = cards[i];
  cards[i] = cards[n];
  cards[n] = temp;
}

Мы проходим по колоде, меняя местами каждую карту с другой картой, выбранной случайным образом. Это выглядит довольно бесхитростно, хотя хотелось бы, чтобы в C# была команда Swap() - она бы упростила код. Это довольно похоже на перемешивание Кнута-Фишера-Йетса, что совершенно не означает, что я очень умный, а скорее говорит о том, что перемешивание - это достаточно простая задача.

Выглядит корректно, вроде бы всё правильно. Однако, с этим кодом есть две проблемы. Видите их?

Первая проблема

Вот здесь:

new Random();

Компьютеры - плохие генераторы случайных чисел. Любое перемешивание, неважно какой алгоритм, будет настолько хорошим, насколько хорош ваш генератор случайных чисел.
Поэтому, если вы пишете, например онлайн-казино, вы должны быть очень осторожны со словом "Random" в своём коде. Если вы будете неосторожны, у вас будут проблемы:

В алгоритме перемешивания колоды карт есть ошибка. По иронии, код был выложен в открытый доступ на www.planetpoker.com/ppfaq.htm с тем чтобы показать заинтересованным игрокам, насколько честно идёт игра (соответствующий вопрос уже удалили). В коде есть вызов randomize() для генерации случайной колоды карт. Реализация, написанная на Delphi 4, берет число миллисекунд от полуночи для старта генератора случайных чисел. Это означает, что вывод генератора случайных чисел предсказуем. Предсказуемый "генератор случайных чисел" - это серьезная проблема безопасности.

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

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

Вторая проблема

Вторая проблема этого кода в том, что он слишком сложный. Эрик Липперт объясняет почему:

Стандартный способ реализовать этот алгоритм - это сделать отображение каждой карты на множество вещественных чисел из отрезка 0.0 до 1.0. А затем отсортировать список исходя из порядка вещественных чисел. Получим сложность O(n log n) и отсутствие предвзятости.

Оказывается, самый просто способ реализовать перемешивание - это сортировка. Это не обязательно самый быстрый способ, если сравнить с O(n) KFY-алгоритма. Мы отсортируем колоду по случайному числу - в данном случае GUID.

var cards = Enumerable.Range(0, 51);
var shuffledcards = cards.OrderBy(a => Guid.NewGuid());

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

Опасность Наивного Алгоритма

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

for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

Это неплохое, простое решение для задачи перемешивания:

1. Пройти по всем картам в колоде

2. Поменять местами текущую карту с любой, случайно выбранной картой

На первый взгляд это выглядит как отлично подходящий способ перемешивания. Он простой, он прямолинейный, и вывод смотрится корректно. Именно так определяется наивный алгоритм:

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

Пример наивного алгоритма - это сортировка пузырьком, она занимает всего пару строк и прост в понимании, но имеет сложность О(n²). Более "умный" алгоритм - это быстрая сортировка, который, хотя и намного более сложный чем сортировка пузырьком, имеет сложность О(n log n) в среднем.

Однако с наивным алгоритмом перемешивания есть одна более глубокая проблема, которую заметят не все программисты. А вы заметили? Чёрт, мне объяснили эту задачу, и я всё равно не заметил проблемы.

Давайте посмотрим, что произойдет, когда мы запустим наивный алгоритм перемешивания на колоде из трёх карт 600,000 раз. В этой колоде 3! или 6 возможных перестановок. Если перемешивание работает корректно, мы должны увидеть, что каждая комбинация представлена 100,000 раз (т.е. все перестановки должны быть равномерно распределены).

Как можно заметить, перестановки 231, 213, 132 встречаются чаще других, а остальные перестановки, соответственно, реже. Т.е. распределение, генерируемое наивным алгоритмом, неравномерное. Это означает, что наивный алгоритм перемешивания имеет предвзятость и принципиально "сломан". Кроме того, предвзятость сразу не видна; необходимо запустить алгоритм несколько тысяч раз, чтобы увидеть доказательную статистику, что не всё так гладко. В этом коварство ошибки.

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

Давайте взглянем на корректный алгоритм перемешивания Кнута-Фишера-Йетса (KFY):

for (int i = cards.Length - 1; i > 0; i--)
{
  int n = rand.Next(i + 1);
  Swap(ref cards[i], ref cards[n]);
}

Видите разницу? Я с первого раза не заметил. Давайте сравним обмен местами для колоды из трёх карт:

Наивный алгоритм выдаёт 3³ (27) возможных комбинаций. Что странно, т.к. математика говорит нам, что возможно только 3! или 6 комбинаций для колоды из трёх карт. В KFY-алгоритме мы выполняем обмен третьей позиции с одной из трёх карт, затем выполняем обмен со второй позиции с оставшимися двумя картами.

KFY-алгоритм порождает ровно 3 * 2 = 6 комбинаций, как видно на картинке выше. Исходя из опыта перемешивания обычных карт может показаться, что чем дольше перемешивать, тем более случайным будет распределение карт в колоде. Однако в случае с наивным перемешиванием - чем больше мы тасуем карты тем хуже. Давайте сравним все возможные перестановки для двух алгоритмов:

Легко можно заметить, что среди 27 результатов наивного алгоритма некоторые комбинации колоды появляются чаще других. С точки зрения простой математики, 27 не делится нацело на 6.

Достаточно теории, давайте посмотрим на другие результаты. Как насчет колоды из 4 карт, перемешанной 600,000 раз?

600,000 делится на 24, и в результате получается 25,000; это практически ровно то, что выдаёт KFY-алгоритм. Результаты наивного алгоритма разбросаны по всей шкале.

Ситуация становится только хуже для большего размера колоды. Вот сравнение для колоды из 6 карт.

С колодой из 6 карт разница между алгоритмами ещё больше. Математика ещё раз добавляет наглядности:

6! = 720

6⁶ = 46,656

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

Я знаю, математика в этом примере может показаться вам простейшей, но для меня этот результат был неожиданным. Мне было трудно понять, почему наивный алгоритм перемешивания, хотя лишь немного отличается от KFY-алгоритма, выдаёт на практике такой неправильный результат. Это минимальная разница в коде, но значительная разница в результатах. Понять, почему это так, мне помогло отслеживание результатов и сбор их в статистику.

Вместо послесловия

Наивные реализации часто выбираются вперед сложных. Простота рассматривается как добродетель. Лучше взять что-то простое, медленное, но понятное, чем сложное, быстрое и непонятное. По крайней мере так кажется. Иногда, однако, как мы видели в нашем примере с перемешиванием, простота наивной реализации может ввести в заблуждение. Код может быть одновременно простым и неправильным. Мне кажется основной урок лежит в тестировании. Не важно насколько прост ваш код, ничто не заменит тестирования, чтобы убедиться, что код делает именно то, что вы думаете.

Короткая справка по C#

var rand = new Random() - вызов, который создаёт класс, который предоставляет генератор псевдослучайных чисел.

rand.Next(length) - метод класса Random, который возвращает случайное целое число >= нуля, которое меньше указанного максимального значения.

Swap(ref T first, ref T second) - статический метод, который обменивает местами значения переданных ему переменных.

ref - передача аргумента метода по ссылке.

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

Enumerable.Range(Int32, Int32) - генерирует последовательность целых чисел в заданном диапазоне.

<Enumerable>.OrderBy(a => Guid.NewGuid()) - вызов OrderBy сортирует элементы последовательности в порядке возрастания ключа. Вызов Guid.NewGuid() - статический метод, инициализирует новый экземпляр структуры Guid.

GUID - Globally Unique Identifier - это 128-битная метка, используемая для того чтобы присваивать уникальные идентификаторы объектам.

Данная статья является переводом двух постов из блога Джефа Эттвуда - первого и второго.