Что не так с "корейским рандомом"?

[MasterToma]

!!WARNING!! Статья содержит минимальное количество МАТАНа и может провоцировать рак для неподготовленых !!WARNING!!

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

Случайные числа - это не тривиальная задача, и без доступа к внешнейму источнику энтропии (состояние процессора, например) очень тяжело получить реальное рандомное число. Однако, даже используя современные механизмы, довольно трудно получать сотни случайных чисел в секунду (ММО). Нужно очень ловко обходить известные проблемы. Проблем очень много (соль для каждого потока, обновление в 1 герц, получение дробных числел, получение их в диапазоне от 1 до 100 и тд тд). ПТС наступил на грабли в

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

(презентация от Лаввэя - главного инженера MSVC по c++). Всего 3 строчки кода

                    //где-то при старте каждого нового потока
                    srand(time(NULL));
                   
                    // получение случайного числа в диапазоне 0.0 - 99.99
                    double dice = std::rand() % 100;
                    if (dice <= dropData->GetChance())
                    {
                    //....

NCsoft, guys

 

[Andragor]

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

 

[Низ]

MasterToma, Огромное спасибо вам за ваш труд. Я мало что понимаю из написанного вами. Но очень интересно читать то, что вы пишите для общего развития. Пускай я и не в теме, но мне хотелось бы еще сильнее углубится в проблему случайны чисел.
Если я правильно понял, то в идеале случайные числа должны давать примерно такой результат:
делаем цикл с вызовом случайного числа от (1-100) 100 раз, в идеале мы должны получить все числа от 1 -100. Если у нас идет переборка в сторону определенных чисел - то рандом плохой?

 

[Zubastic]

Чет пост какой-то короткий. Впрочем суть в презентации дается нормальная

 

[Низ]

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

 

[Zubastic]

. Если у нас идет переборка в сторону определенных чисел - то рандом плохой?

Вся соль в презентации, на которую была дана ссылка.

 

[Низ]

Zubastic, Я не кодер, но кажется уловил смысл кода: а суть в том, что все шансы записаны в бд, откуда и присваиваются. И тут рофл - что корейцы говорят, мол все случайно, а на самом деле все шансы записаны.

 

[MasterToma]

1. вся суть в презентации. Там показано, как нельзя использовать псевдо-генератор случаных чисел
2. NCSoft сделал все возможные ошибки, описанные в презентации (первые 10 слайдов)
3. Настоящие рандомные числа возможны, для этого ОС дает доступ к жезелу для случайной соли из реального мира
4. Низ, не совсем так - просто "случайные" числа у NCSoft генерируются очень неверно из-за глупых ошибок в коде. Например, никогда не выпадет 5

 

[Низ]

MasterToma, спасибо за разжевывание. Преклоняюсь перед вами как перед специалистом. Извините, если написал где глупость.

 

[MasterToma]

Низ, Да никакой глупости нет, эти проблемы встречаются в каждом коде, в конце концов дядька из Microsoft не выдержал и 6 лет назад разжевал, как в трех строчках можно сделать 10 ошибок и не получить равномерного распределения случайных чисел. В L2J часть этих проблем исчезла, потому что они не используют дробные числа в дропе.

 

[WangYi]

Вообще при расчете рандома от 0 до 100, наиболее часто должно выпадать число в районе 40-60, а по краям по идее наименьшая вероятность. Если я еще не пропил теорию вероятностей, конечно))

 

[MasterToma]

Вообще при расчете рандома от 0 до 100, наиболее часто должно выпадать число в районе 40-60, а по краям по идее наименьшая вероятность. Если я еще не пропил теорию вероятностей, конечно))

Это при нормальном распределении Гаусса. Относится к статистикам хорошо - например, больше всего на Земле людей в возрасте от 30 до 50.

При равномерном - это как бросок кубика. Если кубик на 6 граней, то шанс каждой грани это 1/6 и точка. Если 100 - то шанс 1/100 у КАЖДОЙ грани.

 

[Низ]

MasterToma, после ваших сообщений захотелось глубже вникнуть в теорию случайных чисел. Очень интересно.

 

[KanuToIIIKa]

Это многое обьясняет, спасибо!
P.S. На деле думал поможет как-то точиться на офе или там выбивать шмотки или еще что где участвует рандом, а на практике легче дождаться бага инновы и надюпать себе предметов\опыта (если вы понимаете о чем я) хД

 

[Mex-Vision]

Помню как мы переписывали систему дропа в некстах, более приблеженную к ПТС делали, то есть не высчитывали фактический шанс предмета, а крутили группу n количество раз. К примеру есть группа с предметами, ее шанс дропа с рейтами х1 равен 100%, это значит что группа барабан прокрутится 1 раз. Сумма шансов всех предметов в группе равна 100% это приравнивается к 1000000. Затем, визуально представьте линию с миллионом сечений, и каждый предмет занимает определенное количество этих сечений, то есть если у первого предмета шанс 50%, значит на шкале от 1 до 500000 это его числа, и когда функция рандомного числа от 1 до 1000000 выдает число от 1 до 500000, то мы дропаем именно этот предмет. Не знаю насколько это правильный подход, но нам он показался логичней чем был. В таком случае каждый предмет изначально имеет в себе диапазон чисел которые одно из которых нужно для его дропа. Мы эмулировали различное количество попыток, и результат был очень очевидным, то есть если предмет падает с шансом 30%, то с миллиона прокрутов, положительных результатов было в в районе 300000, что соответствует действительности. Такой якобы рандом, стал более прогноз тельным. Но я всё ещё не уверен, если данная функция работает для абсолютно всех дропов на сервере, то по факту, с онлайном в 1 игрок она работать будет как надо, но если таких игроков 10, я думаю они будут влиять на шансы друг друга. Мб я и не прав, просто мысли в слух, очень интересная тема.

 

[Rozhek]

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


Тут я тоже не понимаю, от чего ужасаться.
Ну получили не полностью рандомное число, 99-67=33. 32767 / 33 - Это примерно 0.1% погрешности от «случайного» числа.
Если распределение вероятности не ожидаемое, скорее всего проблема в формуле проверки шанса, а не этой погрешности ))
Например
If(dice<3)
return 1;
Else if(dice<15)
Return 2;
Else if(dice<50)
return 3;
Else return 0;
Думал, что будет шанс 3, 15 и 50. А получил 3, 12, 35.
Ещё можно погрешность в 0.5% добавить за счёт удаления дробной части. Почему 0.5? 0.01-0.99 это 1% от 100. Допустим целыми dice получили 50. Если dice=50.5, то ничего не поменялось. Если dice=49.50, То попали в нашу 0.5% погрешность. Но это уже зависит от условий выборки, можно наверное и 1% погрешности получить.

 

[Низ]

Rozhek, нууу тут уже от части философия. Поскольку допуская, что случайные числа - случайны, мы можем списать на порог погрешности. Если мы для себя принимаем, что в цикле из 100 запросов от 0-100, мы хотим увидеть все цифры от 0-100, то любые отклонения от этого - можно и снести к "не случайному". Поэтому Тома поднял, очень сложную и интересную тему. Думаю тут каждый согласится, что в программировании важно: достижение поставленной задачи и простота решения. Какая задача изначальна была у Корейцев? Задать определенную выборку шансов и если они совершили погрешность даже на 0.1 % - это уже ошибочное решение задачи.

 

[sergebaz]

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

 

[Spoken]

до ГФ

В PTS GF на ряду с std::rand используется также std::mt19937_64.

std::mt19937_64 вызывается(из проверенного мной) всюду в формулах скиллдвига и прочих механиках. А общее соотношение вызовов такое: 241 вызов std::mt19937_64 против 79 вызовов std::rand.

Касаемо сида при создании тредов:
Для std::rand сидом выступает либо

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

, либо

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

А std::mt19937_64 сидится с помощью

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

std::mt19937_64 почти всегда используется для получения double числа в диапазоне от 0.0 до 1.0
Для этого есть 2 функции преобразования, отличающиеся только возможностью возврата значения 1.0:

const double DOUBLE_UNIT_EXCLUSIVE = 0x3CA0000000000000d;
const double DOUBLE_UNIT_INCLUSIVE = 0x3CA0000000000001d;
const double DOUBLE_SIGN_CHANGE = 0x43F0000000000000d;

double GetDouble_UnitExclusive()
{
  signed __int64 l = MersenneTwister64::NextLong() >> 11;
  if (l < 0)
    return ((double)l + DOUBLE_SIGN_CHANGE) * DOUBLE_UNIT_EXCLUSIVE;

  return (double)l * DOUBLE_UNIT_EXCLUSIVE;
}

double GetDouble_UnitInclusive()
{
  signed __int64 l = MersenneTwister64::NextLong() >> 11;
  if (l < 0)
    return ((double)l + DOUBLE_SIGN_CHANGE) * DOUBLE_UNIT_INCLUSIVE;

  return (double)l * DOUBLE_UNIT_INCLUSIVE;
}

Затем значение, как правило, масштабируется и сравнивается с шансом.
Вот так были решены эти проблемы в GF.

P.S. Если кому-то интересно, в интернете есть готовая реализация std::mt19937_64 на Java:

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

 

[MasterToma]

@Spoken, возможно, что ГФ часть исправили, если верить вашим заявлениям, я смотрел ее поверхностно. В своих фиксах для С1 я тоже переписал rand() на std::mt19937, инициализируя std::random_device.
Rozhek , тут немного глубже, чем просто модуло. И, судя по заявлениям @Spoken, в ГФ все таки начали исправлять. Потому что видно было, особенно при дропе и НПЦ спавне, что царь рандом не настоящий.