UAPOKER
Зарегистрируйтесь или войдите, чтобы получать билеты на фрироллы Info

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

egorzar
egorzar
Пользователь оффлайн. Последний раз был на сайте 13 лет назад. Оффлайн
На сайте: 14 лет
Сообщения: 21
Как не надо тасовать карты


Частичный перевод статьи
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



Foolosopher
Foolosopher
Пользователь оффлайн. Последний раз был на сайте 1 год назад. Оффлайн
VIP пользовательНаграда: 1-е место в оффлайн приватнике UAPOKERНаграда: Лучший блогер"Серебро" в рейтинге игроков за 2011 г.Победитель турнира для модераторовЛидер квартального рейтинга UAPOKERЗаслуженный медалист. Кликните для просмотра
На сайте: 15 лет
Сообщения: 4591
Любопытно. Заставило задуматься, но пока сложно сказать, правильно это или нет. Надо бы самому прикинуть 3.gif
wwwrt
wwwrt
Пользователь оффлайн. Последний раз был на сайте 3 недели назад. Оффлайн
VIP пользовательНаграда: 1-е место в приватнике на PokerStars
На сайте: 15 лет
Сообщения: 1814
А давайте научим ГСЧ (оператор random) правьно выбирать а то он все не к той карте +1 делает4.gif
(шутю) идею выраженную в данной теме понял - причино-следственная часть ясна!

Да только и менять там особо (в первоначальном алгоритме) ни чего и не надо.
Прикинь вариант что частота повтора алгоритма ну скажем  производная   := Random (5) 11.gif
ВОТ 16.gifИ УСЕ!

Нет конечно и в таком случае можно будет примерно высчитать в какой массив что упадет!17.gif было бы желание17.gif
Acid_Wave
Acid_Wave
Пользователь оффлайн. Последний раз был на сайте 3 года назад. Оффлайн
VIP пользовательНаграда: 1-е место в приватнике на PokerStarsНаграда: Победитель двух приватников на BetfairНаграда: Победитель трех приватников на FullTilt1-е место в приватнике на MuchosPoker
На сайте: 15 лет
Сообщения: 2236
Видимо это было давно и неправда. Советую почитать статью Генератор псевдослучайных чисел из Википедии. Уже давно во всех румах используются одновременно как программные, так и аппаратные ГСЧ. 
IQmonkey
IQmonkey
Пользователь оффлайн. Последний раз был на сайте 13 лет назад. Оффлайн
На сайте: 14 лет
Сообщения: 34
Очень любопытная статья....
DJT299
DJT299
Пользователь оффлайн. Последний раз был на сайте 2 года назад. Оффлайн
На сайте: 14 лет
Сообщения: 632
Вряд ли оно сейчас так, убивают ссылки на борланд и паскаль..
VitalicS
VitalicS
Пользователь оффлайн. Последний раз был на сайте 15 недель назад. Оффлайн
VIP пользовательЗаслуженный медалист. Кликните для просмотра
На сайте: 15 лет
Сообщения: 2268
Статья интересная, но не актуальная!
И есть много моментов с которыми можно поспорить. 1.gif
Klubik
Klubik
Пользователь оффлайн. Последний раз был на сайте 9 лет назад. Оффлайн
На сайте: 14 лет
Сообщения: 80
Очень интересно. Надо тоже что нибудь замутить. Вроде программирование знаю на отлично))))
Кричалка наверх