Как не надо тасовать карты

Как не надо тасовать карты


Частичный перевод статьи
How We Learned to Cheat at Online Poker: A Study in Software Security
by Brad Arkin, Frank Hill, Scott Marks, Matt Schmid and Thomas John Walls

...введение пропущено... Авторы объясняют, что проанализировали программное обеспечение одного онлайн-казино.
Риски программного обеспечения
Тасование виртуальной колоды карт

Первый недостаток, на котором мы сфокусируемся, касается тасования карт. Что означает честное тасование колоды карт? Очевидно, каждая возможная комбинация карт должна иметь равные шансы. Мы назовем каждую возможную комбинацию 52 карт "раздачей".

Для реальной колоды карт есть 52! (примерно 2^226) возможных уникальных раздач. Когда компьютер тасует виртуальную колоду карт, он выбирает одну из этих возможных комбинаций. Есть много алгоритмов, которые могут быть использованы для перемешивания карточной колоды, некоторые из них лучше других (и некоторые просто неверны).

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

Иллюстрация 1: Дефектный алгоритм тасования

procedure TDeck.Shuffle;
var
ctr: Byte;
tmp: Byte;

random_number: Byte;
begin
{ Наполнить колоду картами по порядку }
for ctr := 1 to 52 do
Card[ctr] := ctr;

{ Инициировать генератор случайных чисел при помощи системных часов }
randomize;

{ Случайным образом перетасовать каждую карту }
for ctr := 1 to 52 do begin
random_number := random(51)+1;
tmp := card[random_number];
card[random_number] := card[ctr];
card[ctr] := tmp;
end;

CurrentCard := 1;
JustShuffled := True;
end;

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

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

Проницательные программисты заметят, что приведенный алгоритм содержит ошибку. По идее, он должен перетряхнуть начальную колоду, поменяв каждую карту с какой-нибудь другой картой. В отличие от большинства паскалевских функций, функция Random(n) на самом деле возвращает число от 0 до n-1 вместо числа от 1 до n. Алгоритм выбирает карту для обмена с текущей картой по формуле random(51)+1. Эта формула дает случайное число от 1 до 51. Значит, алгоритм никогда не выбирает переставить текущую карту с 52-й картой. Когда цикл наконец достигает последней карты, 52, эта карта переставляется с любой другой картой, кроме нее самой. Это значит, что тасующий алгоритм никогда не оставит 52-ую карту на 52-ом месте. Очевидное, легко исправляемое, нарушение честного расклада.
Вторая проблема: плохое распределение раздач

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

Чтобы проиллюстрировать проблему на маленьком примере, мы будем тасовать колоду только из трех карт (то есть n=3), используя описанный выше алгоритм.

Иллюстрация 2: Как не надо тасовать карты

Для (i от 1 до n)
Переставить i-ю карту со случайной картой от 1-й до n-й
                  
Иллюстрация 2 показывает дерево всех возможных колод, которые могут быть построены этим тасующим алгоритмом. Если наш генератор случайных чисел хорош, каждый лист этого дерева имеет равные шансы.

Даже на этом маленьком примере можно видеть, что алгоритм не дает раздачи с равной вероятностью. Он будет создавать раздачи 231, 213 и 132 чаще, чем 312, 321, 123. Если вы ставите на первую карту и знаете это распределение, вы можете рассчитывать, что у карты 2 больше вероятность появления, чем у других. Неравные вероятности становятся более заметными с увеличением числа карт в колоде. Когда полная колода из 52 карт тасуется показанным выше алгоритмом (n=52), неравное распределение раздач отклоняет вероятности определенных комбинаций и меняет результаты ставок. Опытные игроки в покер (которые зарабатывают игрой на жизнь) могут получить преимущество от искаженных вероятностей.

От переводчика: вот это меня и зацепило.
Я уже много лет не писал программ карточных игр, но когда этим развлекался, делал именно так. А вот же ж.
Разных колод всего 6; алгоритм дает 27 равновероятных исходов. 27 на 6 не делится. Упс. Колоды 132, 231, 213 получают вероятность 5/27, колоды 123, 312, 321 - вероятность 4/27.
Вероятность получить на первом месте карту 2 - 10/27, карту 1 - 9/27, карту 3 - 8/27. Не то чтобы большая разница, и на 52 картах будет еще меньше, но сам факт - что такой красивый, наивно написанный алгоритм не дает равное распределение - это слегка шокирует.

Иллюстрация 3: Как надо тасовать карты

Для (i от 1 до n-1)
Переставить i-ю карту со случайной картой от i-й до n-й
  
                                             
Иллюстрация 3 дает намного более хороший алгоритм тасования. Ключевая разница между алгоритмами состоит в том, что число возможных карт для обмена убывает с продвижением по колоде. Опять же, мы показываем дерево, иллюстрирующее этот алгоритм на учебной колоде из трех карт. Разница между новым алгоритмом и старым в том, что каждая карта переставляется с картой из диапазона [i, n], а не [1, n]. Это уменьшает число возможных исходов с 3^3 = 27 в плохом алгоритме до 3! = 6. Важное изменение, поскольку число листьев дерева n! в новом алгоритме как раз соответствует числу возможных уникальных раздач.
Заметьте, что каждая возможная раздача генерится одним и только одним способом, и все они имеют равную вероятность появления. Теперь это честно!
Генерация случайных чисел на детерминистской машине

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

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

Чтобы запрограммировать компьютер делать что-то вроде представленного выше алгоритма, генератор псевдо-случайных чисел обычно создает целое число в диапазоне от 0 до N и делит его на N. Получается значение от 0 до 1. Следующий вызов к генератору берет целое из предыдущего вызова и пропускает его через функцию, которая дает новое целое число от 0 до N, и возвращает новое целое, деленное на N. Это значит, что количество уникальных значений, возвращенных любым генератором псевдо-случайных чисел, ограничено количеством целых чисел от 0 до N. В самом обычном генераторе N равно 2^32 (примерно 4 миллиарда), что является наибольшим числом, которое помещается в 32 бита. Другими словами, есть максимум 4 миллиарда возможных значений, производимых генератором такого сорта. На наш взгляд, число 4 миллиарда не так уж и велико.

Число, которое называется "seed" (источник, затравка) передается генератору псевдо-случайных чисел как первое целое для передачи в функцию. Эта затравка используется для начала процесса. Заметьте, что в результатах генератора псевдо-случайных чисел нет ничего непредсказуемого. Каждое значение, возвращаемое генератором, абсолютно жестко определено предыдущим значением (и изначально, затравкой, с которой все началось). Если мы знаем целое число, выданное как одно из значений, мы знаем и все последующие значения, выдаваемые генератором.

Генератор псевдо-случайных чисел, распространяемый с компиляторами Борланда, служит хорошим примером и показан на иллюстрации 4. Если мы знаем, что текущее значение RandSeed равно 12345, то следующее целое будет 1655067934 и будет выбрана карта 20. Это происходит каждый раз (что не должно ни для кого быть сюрпризом, поскольку компьютеры совершенно детерминистичны).
Иллюстрация 4: Реализация Random() от Борланда
long long RandSeed = #### ;

unsigned long Random(long max)
{
long long x ;
double i ;
unsigned long final ;
x = 0xffffffff;
x += 1 ;

RandSeed *= ((long long)134775813);
RandSeed += 1 ;
RandSeed = RandSeed % x ;
i = ((double)RandSeed) / (double)0xffffffff ;
final = (long) (max * i) ;

return (unsigned long)final;
}

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

Алгоритм тасования, использованный в вышеупомянутой программе, всегда начинает с упорядоченной колоды карт и генерит последовательность случайных чисел для перемешивания колоды. Вспомним, что в реальной колоде есть 52! (примерно 2^226) возможных уникальных раскладов. Также вспомним, что затравка 32-битного генератора случайных чисел - 32-битное число, что дает чуть больше 4 миллиардов возможных затравок. Поскольку колода инициализируется и генератор получает новую затравку перед каждой сдачей, только 4 миллиарда возможных раскладов могут получиться из этого алгоритма. Четыре миллиарда возможных раздач - это тревожно меньше, чем 52!.

Хуже того, алгоритм на иллюстрации 1 выбирает затравку для генератора случайных чисел, используя паскалевскую функцию Randomize(). Эта конкретная функция Randomize() выбирает затравку как число миллисекунд, прошедших с полуночи. В сутках есть всего-то жалких 86,400,000 миллисекунд. Поскольку номер миллисекунды используется как стартер для генератора случайных чисел, количество возможных различных колод теперь падает до 86,400,000. Восемьдесят шесть миллионов тревожно меньше, чем четыре миллиарда. Но это еще не все. Все еще хуже.
Ломая систему

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

...пропущено... Авторы рассказывают, что написали программу, которая рассчитывала полный расклад, увидев первые пять карт, за одну секунду. Поскольку казино уже поправило ошибки, фокус больше не пройдет.
Автор: Dilbert.ru на 19:03