Объясните про ГСЧ

пока писал пост, ту тему прикрыли. Прошу в этой не поднимать вопросы демонфроста, а ответить на мой вопрос? мне это действительно интересно.

вот мой пост, который опоздал в ту тему:

почему эта тема будет всегда вызывать интерес и дискуссию, понятно.
наверняка среди вас есть программисты. если ГСЧ одинаков у всех (тоесть чист и неподкручен) почему из него делают такую тайну. открывают люди рум. нахрена им возиться с написанием "своего" ГСЧ? Проще купить код, а заморочиться на создание удобного софта, маркетинге, и т.п. Нет же, у всех свой ГСЧ, и у всех он кристально честный.

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

просто не пойму. Есть программа Excel Майрософта, есть маковский офис, но и в том и в том 5+5=10. а тут у каждого своя формула как посчитать 5+5 чтоли?

объясните мне сей феномен, уважаемые регуляры.

А про организации, котролирующие ГСЧ, они государственные?

Алгоритма дающего действительно рандомное рапределние чисел нет в природе.

Все алгоритмы генерации СЧ генерируют так называемые псевдослучайные числа.

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

Разная реализация алгоритмов генерации как раз и обеспечивает величину отклонений от идеальных параметров.

В каком-то алгоритме например отлконение кривой распределения будет смещено влево на 0.005%, а в каком-то на 5*(10в минус 5 степени)%.

Вся эта математика весьма и весьма сложна это во первых.

Во вторых она дорого стоит.

Возьмем к примеру алгоритм реализации ГСЧ от Майкрософт. С его помощью генерируются GUID и что самое главное - закрытые ключи подписей файлов Майкрософта. Дотсуп к ключам подписей в корпорации Майкрософт имеют всего 3 человека насколько я знаю. Майкрософт никогда и никому не продаст свой алгоритм ГСЧ просто потому что есть хоть и ничтожная, но вероятность что в нем выявят изъян, которым могут воспользоваться для взлома ключей-подписей. Именно поэтому он лицензирован и закрыт.

Точно так же с любой организацией, которая занимается разработкой софта.

И так практически везде куда ни ткнись.
Алгоритмы поиска в сбалансированном B-дереве давным давно описаны и формализованы.
Тем не менее реализация и осбенности очень сильно зависят от архитектуры и именно поэтому у Microsoft, Oracle, Sybase, IBM и прочих они свои, закрыты и лицензированы.

Есть программа Excel Майрософта, есть маковский офис, но и в том и в том 5+5=10. а тут у каждого своя формула как посчитать 5+5 чтоли?

Это кстати заблуждение что везде все одинаково.

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

Lezgin @ 10.2.2011
А про организации, котролирующие ГСЧ, они государственные?

Существует три регулятивных органа онлайн покера:

Комиссия по азартным играм Канавейк (тут Full Tilt)
Комиссия острова Олдерни по контролю над азартными играми (тут PartyPoker)
Комиссия по надзору за азартными играми острова Мэн (тут Pokerstars)

Комиссиями островов Олдерни и Мэн руководит государство

вот что я знаю. Они контролируют полностью деятельность румов, а не только ГСЧ

Lezgin, По поводу организаций и ГСЧ. Не знаю, кто их контролирует, но есть некий стандарт ГСЧ и защиты данных, которыму следует подавляющее большинство румов. Соотв. эти румы кто-то контролирует. В том числе и на честность ГСЧ, но частная это компания или гос. - это я хз.

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

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

Для информации http://www.pokerstars.com/ru/poker/rng/

kirill @ 10.2.2011
была кстати история когда один из интеловских процов лажал при перемножении (если не путаю) некоторых очень больших чисел, так нашли, был скандал и интел отзывал процы и попал на бабки.

Это один из первых Пентиумов.
Сумма убытков интела оценивалась в 700 миллионов.

История там по слухам была гараздо смешнее. 2/3 отела проектирования процессоров получили в качестве годовой премии брелки сделанные из отозванных камней. В)

Софтовый ГСЧ априорно не может быть действительно случайным. Есть аппаратные, они дорогие, и те только приближены, но не полностью случайны. Как правило алгоритм там берет за основу какие то действительно случайные колебания окружающей среды, например давления температуры и силы ветра.

Ничего суперсекретного в этом нет, в т.ч. у майкрософта, т.к. математические алгоритмы описаны в науке криптография. Их основная тайна не генерация случайного числа, а закрытый ключ.

Ответить на вопрос по поводу подкрученности ГСЧ не возможно не будучи владельцем крупного рума. Но можно задать ряд вопросов себе и подумать над ответами:

1. Возможно ли это теоретически, в т.ч. технически? Мой ответ, как IT специалист с большим стажем- да, это возможно. Производительность процессоров сейчас так высока, что задачи подобные постоянного пересчета рейтинга скажем миллиона игроков вполне возможны. Особенно на основе современных кластерных технологий. А на основании этого рейтинга можно делать все что угодно. Никто ведь не видит в натуре колоду, скажем когда мы выставляемся АА vs 22. Кто знает сколько в этой виртуальной колоде двоек? 2? Или 10?
2. Есть ли у румов возможности для реализации (равно методологии, технологии, специалисты и бабло бабло бабло)? Однозначно есть и лучшие специалисты и деньги.
3. Если бы я был владельцем рума внедрил бы я что то подобное? Думаю да, мой рум это бассеин в который затекает и вытекает вода, часть я имею в виде рейка, но только пока в бассеине есть вода. И если кто то будет через чур активно эту воду черпать себе в карман, я бы хотел иметь возможность ограничить его. Причем это не хайроллеры, т.к. эти гоняют по сути деньги туда сюда катаясь на горках дисперсии и большинство из них еще и лудоманы, атк что с деньгами далеко не уйдут и в бассеине сильно пусто от них не станет.

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

Что бывает когда алгориты работы ГСЧ предаются огласке:

История с Planet Poker и ASF Software Inc.


Planet Poker - первый в мире покер-рум, который предложил своим пользователям игру на деньги в интернете. Произошло это в январе 1998 года. Немного позже его безопасностью заинтересовались специалисты из "Reliable Software Tehnologies" (ныне "Cigital"). На сайте Planet Poker были открыты исходники их алгоритма ГСЧ (сам алгоритм принадлежал компании "ASF Sowtware Inc."). Этим они хотели показать свою честность и надежность, но исходники только помогли специалистам найти в нем бреши. Вот функция перетасовки карт из опубликованного алгоритма:

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

random_number: Byte;
begin
{ Fill the deck with unique cards }
for ctr := 1 to 52 do
Card[ctr] := ctr;

{ Generate a new seed based on the system clock }
randomize;

{ Randomly rearrange each card }
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 меняются местами с любой случайной картой. Для генерации случайных чисел используются Pascal-функции random, randomize, которые используют системный таймер и алгоритм ГПСЧ для получения случайных чисел.

Первая ошибка алгоритма кроется в функции random(n) - она, в отличие от большинства Pascal-функций, возвращает значение от 0 до n-1. Т.е. "random(51)+1" дает нам число от 1 до 51 - классическая ошибка off-by-one. Получается текущая карта никогда не будет меняться местами с последней 52-й картой, что уже дает отклонение от случайности получаемой колоды.

Также специалисты "Reliable Software Tehnologies" выявили несостоятельность самого алгоритма, даже если исправить ошибку off-by-one. Для демонстрации этого они использовали описанный выше алгоритм:

for (i is 1 to n)
Swap i with random position between 1 and n

Для простоты расчетов использовалась колода из 3-х карт. В результате колоды 231, 213 и 132 встречались чаще чем 312, 321 и 123. Понятно, что для колоды из 52-х карт какие-то варианты перетасовки колоды должны были встречаться чаще чем другие.

Еще одним важным упущением было количество возможных колод в таком ГСЧ. При реальной перетасовке карт возможны 52!= 8,06*1067 вариантов колоды. Pascal-функции генерируют случайные числа на основе системных часов. Основа для расчета случайного числа - количество милисекунд с полуночи. В сутках всего 86 400 000 миллисекунд, таким образом мы имеем всего 86,4 млн возможных вариантов перетасовки колоды, что гораздо меньше реально возможной.

И это не все, найденные недостатки не дают особого преимущества для игроков, но следующая уязвимость позволяла полностью узнать последовательность карт в колоде. Все опять же из-за ГПСЧ, точнее его предсказуемости. Исследователи написали эксплоит, который в точности мог показывать все карты игроков и оставшиеся карты стола после выложенных на стол 3-х карт. Таким образом он основывался на 5-ти известных картах: 2-х игрока и 3-х на столе. Используя аналогичный Pascal алгоритм ГСЧ и подбирая разное количество миллисекунд с отклонением от текущего времени (время генерации карт должно было быть близко к локальному времени), эксплоит находил точное совпадение 5-ти известных карт и выдавал все остальные.

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

Для игроков эта история сложилась удачно - эксплоит был в хороших руках, и специалисты "Reliable Software Tehnologies" сразу сообщили о найденных уязвимостях в "ASF Sowtware Inc." (их услугами кроме "Planet Poker" также пользовались purepoker.com, deltacasino.com) и позже опубликовали свой отчет. Они оценили ущерб, если бы программа попала в плохие руки, в $100 000 в день. Planet poker и вообще онлайн покеру эта история нанесла серьезный ущерб, хотя и не помешала активно развиваться этой отрасли. А "Reliable Software Tehnologies" была переименована в "Cigital" и сейчас является очень авторитетной компанией по аудиту и сертификации программ.

Не знаю, кто их контролирует, но есть некий стандарт ГСЧ и защиты данных

Стандартов много.
Как правило все оспользуют или американский или евросоюзовский стандарт по обеспечению криптографической стойокости алгоритмов шифрования и защиты.

maximusvm @ 10.2.2011
Это кстати заблуждение что везде все одинаково.

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

Что-то я от жизни отстал, похоже :)

"Алгоритм" деления в разных процессорах абсолютно одинаков, там биты двигаются туда-сюда. Синусы процессоры вообще вычислять не обучены (за исключением специализированных).

Про GUID - тоже каша, часть верно, часть совсем не оттуда.

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

Ничего суперсекретного в этом нет, в т.ч. у майкрософта, т.к. математические алгоритмы описаны в науке криптография

Я еще раз повторюсь. Оптимальный алгоритм посика в b-tree известен уже 50 лет как. Тем не менее и у Оракла и у Майкрософта он свой, хоть и базируется на идее эталонного.
Просто их собственные алгоритмы используют особенности архитектуры конкретной системы.

Точно так же и с алгоритмами генерации СЧ.
Они закрыты, просто потому что имея исходный код теоретически можно найти изъян и создать алгоритм, который будет давать более менее достоверное предсказание.

"Алгоритм" деления в разных процессорах абсолютно одинаков, там биты двигаются туда-сюда

ну раздели мне 5 на 13 двигая биты туда сюда.

Chinck @ 10.2.2011
Для информации http://www.pokerstars.com/ru/poker/rng/

на самом деле это ничего не значит, т. к. ГСЧ лишь выдает случайное число от 0 до 1 и когда говорят, что ГСЧ проверен серьезной организацией, то имеют ввиду, что последовательность этих чисел случайна и нету никаких закономерностей.

Вопрос в том, как работает код, вызывающий функцию случайного числа. Можно же написать что-то типа.

БЕРЕМ случайное число
Смотрим, дает ли оно кулер в пользу фиша
Если да, то идем дальше
Если нет, то повторяем сначала.

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

п. с. я в подобные подстройки не верю

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

Сертификация по-нашему :
не помню , то ли в 2005-м , то ли в 2006-м всех владельцев клубов игровых автоматов обязали пройти какую-то новую "усовершенствованную" сертификацию ( помимо той , что делалась производителями аппаратов ) . Порядок в теории такой : снимается игровая плата , тестируется специалистами на каком-то оборудовании на предмет соответствия всех параметров каким-то принятым нормам , если всё ок - тебе выдают красивый сертификат на этот автомат и голографическую наклейку .
Надо так надо . Еду в Волгоград , нахожу этот государственный центр сертификации и стандартизации (вроде так) . Короче - я честно хотел сделать всё как положено . Вот мой разговор с ответственным за это дело человеком :
- Здравствуйте , я такой-то , оттуда-то , у меня столько-то игровых аппаратов , примите пожалуйста заявку на прохождение сертификации . Вот все докуметы ...
- Ты чё парень , пиз....лся , какая заявка , с тебя столько-то (немало) , вот тебе куча наклеек , приклеишь сам .
Надеюсь , что в цивилизованных странах всё не так продажно ..

В общем, как программист плюсую к постам maximusvm и Mad-Revolver

Кстати, пришла в голову простая мысль. Почему румы не сделают механизм контроля честности как в онлайн-казино на рулетке, например?
Я сам об этой теме знаю крайне поверхносто, но как я понимаю там идея в том, что сгенерированную заранее последовательность бросков шарика тебе куда-то выкладывают и ты потом сможешь на нее посмотреть. Ну что тебя не наё..ают кидая шарик в зависимости от твоей ставки.
Имхо, было бы неплохо румам делать что-то аналогично касательно сгенерированной колоды...
Чтобы знать, что там 2 двойки, а не 10 )))

Mad-Revolver @ 10.2.2011
Софтовый ГСЧ априорно не может быть действительно случайным. Есть аппаратные, они дорогие, и те только приближены, но не полностью случайны. Как правило алгоритм там берет за основу какие то действительно случайные колебания окружающей среды, например давления температуры и силы ветра.

Ничего суперсекретного в этом нет, в т.ч. у майкрософта, т.к. математические алгоритмы описаны в науке криптография. Их основная тайна не генерация случайного числа, а закрытый ключ.

Ответить на вопрос по поводу подкрученности ГСЧ не возможно не будучи владельцем крупного рума. Но можно задать ряд вопросов себе и подумать над ответами:

1. Возможно ли это теоретически, в т.ч. технически? Мой ответ, как IT специалист с большим стажем- да, это возможно. Производительность процессоров сейчас так высока, что задачи подобные постоянного пересчета рейтинга скажем миллиона игроков вполне возможны. Особенно на основе современных кластерных технологий. А на основании этого рейтинга можно делать все что угодно. Никто ведь не видит в натуре колоду, скажем когда мы выставляемся АА vs 22. Кто знает сколько в этой виртуальной колоде двоек? 2? Или 10?
2. Есть ли у румов возможности для реализации (равно методологии, технологии, специалисты и бабло бабло бабло)? Однозначно есть и лучшие специалисты и деньги.
3. Если бы я был владельцем рума внедрил бы я что то подобное? Думаю да, мой рум это бассеин в который затекает и вытекает вода, часть я имею в виде рейка, но только пока в бассеине есть вода. И если кто то будет через чур активно эту воду черпать себе в карман, я бы хотел иметь возможность ограничить его. Причем это не хайроллеры, т.к. эти гоняют по сути деньги туда сюда катаясь на горках дисперсии и большинство из них еще и лудоманы, атк что с деньгами далеко не уйдут и в бассеине сильно пусто от них не станет.

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

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

maximusvm @ 10.2.2011
ну раздели мне 5 на 13 двигая биты туда сюда.

Эмм, ты хочешь меня проверить или сомневаешься в моих словах? Если первое - то ради бога, если второе - да тоже пожалуйста, можешь считать и дальше, что в процессоре зашиты таблицы умножения, синусов/косинусов и логарифмов.