Может кому будет интересно - статья о рандоме, написанная "русским"(понятным) языком.

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

[ Перевод: © Дмитрий Попков ]

Внизу Научного Центра Онтарио в Торонто (Канада) расположено большое круговое устройство, сделанное из тонких прутов стали. Любознательные наблюдатели могут взять бильярдные шары, находящиеся там для этой цели, и пустить их свободно по устройству. Шары со свистом летят по направляющим, с лязгом рикошетят от штырей, захватываются центробежной силой и поднимаются к потолку. В некоторых местах шары выбирают одну направляющую или другую совершенно случайно. Как получается, что эта не силовая конструкция, созданная по жесткому образцу, выдает непредсказуемые результаты?

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

Похоже на какую-то занудную чушь?

Случайные числа нужны для придания вашим программам эффекта неожиданности без вовлечения core dump. Это настоящий полигон для захватывающих дух экспериментов.

Случайно, но не по-настоящему случайно

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

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

Стандартная в Linux С-библиотека (stdlib.h) содержит две встроенные функции для случайных чисел. Первая, rand(), возвращает случайную последовательность между 0 и RAND_MAX. Если мы наберем

  printf( " rand() is %d\n", rand() );
  printf( " rand() is %d\n", rand() );
  printf( " rand() is %d\n", rand() );

rand() вернет подобные значения

  rand() is 1750354891
  rand() is 2140807809
  rand() is 1844326400

Каждое обращение вернет новое, случайно выбранное положительное целое число (типа integer).

Другая стандартная библиотечная функция random() вернет положительное длинное целое число (типа long integer).  В Linux и целочисленные, и длинные целые числа имеют одинаковый размер. random() обладает и некоторыми другими свойствами, которые обсудим далее.

Существуют также и другие, уже устаревшие, функции для получения случайных чисел.

  * drand()/erand() возвращает случайное двойное между 0..1.
  * lrand()/nrand() возвращает случайное длинное между 0 and 2^31.
  * mrand()/jrand() возвращает последовательность случайной длины.

Они обеспечивают обратную совместимость с другими клонами UNIX.

rand() и random(), конечно, совершенно бесполезны сами по себе и редко вызываются непосредственно. Не так часто мы ищем числа между 0 и действительно большим числом: числа должны принадлежать, в соответствии с поставленной проблемой, заданному диапазону. Чтобы приручить rand(), его значения должны быть промасштабированы в приемлемом диапазоне, например между 0 и заданным максимумом. Неплохо работает модульный оператор (%): когда число поделено, остаток между 0 и 1 меньше оригинала. Добавление 1 к модулю дает искомый диапазон.

  int rnd( int max ) {
    return (rand() % max) + 1;
  }

Здесь одна линейная функция вернет числа между 1 и заданым максимумом. rnd(10) вернет числа между 1 и 10, rnd(50) вернет числа между 1 и 50.  Реальные события могут моделироваться выбором соответствующих значений для получения определенных результатов. Бросок монеты - это rnd(2)==1 для решки и rnd(2)==2 для орла  Бросок игрального кубика - rnd(6)+rnd(6)

В различных Linux руководствах по rand() рекомендуется брать "верхние биты" (т.е. использовать деление вместо модуля), потому что это имеет тенденцию быть более случайным. Однако функция rnd(), упомянутая выше, генерирует числа со степенью случайности, приемлемой для большинства приложений.

Следующая тестовая программа генерирует 100 чисел между 1 и 10, считая, как часто каждое число появляется в последовательности. Если бы числа были совершенно равноправны, каждое из них появилось бы по 10 раз.

  int graph[11];
  int i;

  for (i=1; i<=10; i++)
      graph[i] = 0;
  for (i=1; i<=100; i++)
      graph[ rnd(10) ]++;
  printf( "for rnd(), graph[1..10] is " );
  for (i=1; i<=10; i++)
      printf( "%d " , graph[i] );
  printf( "\n" );

Запустив эту подпрограмму, мы получим следующее:

  for rnd(), graph[1..10] is 7 12 9 8 14 9 16 5 11 9

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

unsigned int seed = 0;

int fast_rnd( int max ) {
  unsigned int offset = 12923;
  unsigned int multiplier = 4079;

  seed = seed * multiplier + offset;
  return (int)(seed % max) + 1;
}

Эта функция жертвует точностью ради скорости: она производит случайную последовательность не так математически верно, как rnd(), но использует только несколько небольших вычислений. В идеале, смещение и множитель должны быть такими простыми числами, чтобы минимальное количество чисел имело преимущество над остальными.

Замена rnd на fast_rnd() в тестовых функциях все еще дает разумное приближение к rand()

  for fast_rnd(), graph[1..10] is 11 4 4 1 8 8 5 7 6 5

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

  seed = room_number;
  num_enemy = fast_rnd( 5 );
  for ( enemy=1; enemy<=num_enemy; enemy++ ) {
      enemy_type[enemy] = fast_rnd( 6 );
      enemy_horizontal[enemy] = fast_rnd( 1024 );
      enemy_vertical[enemy] = fast_rnd( 768 );
  }

Seed для rand() в Linux устанавливается посредством srand(). Например,

  srand( 4 );

установит rand() seed в 4.

Существуют два способа управлять последовательностью в другой функции Linux - random(). Первый - srandom(), подобен srand(), устанавливает seed для random().

Второй способ актуален, если вы нуждаетесь в большей точности: Linux обеспечивает две функции, чтобы управлять быстродействием и точностью random().  С помощью initstate() вы можете задать random() и начальное число, и буфер для хранения промежуточных результатов. Буфер может быть размером 8, 32, 64, 128 или 256.  Больший буфер даст более случайные числа, но потребует больше времени для расчетов.

  char state[256];                 /* 256 байт буфер */
  unsigned int seed = 1;         /* устанавливаем seed в 1 */

  initstate( seed, state, 256 );
  printf( "using a 256 byte state, we get %d\n", random() );
  printf( "using a 256 byte state, we get %d\n", random() );
  initstate( seed, state, 256 );
  printf( "resetting the state, we get %d\n", random() );

получаем

  using a 256 byte state, we get 510644794
  using a 256 byte state, we get 625058908
  resetting the state, we get 510644794

Вы можете переключать состояние random() посредством setstate() совместно srandom() для установки seed в определенное значение.
setstate() всегда возвращает указатель на предыдущее состояние.

  oldstate = setstate( newstate );

Если вы не изменяете seed при запуске программы, ваши случайные числа будут всегда те же самые. Для создания изменяющейся случайной последовательности seed должно быть установлено в некоторое значение, взятое вне программы. Хороший прием - использование значения, возвращаемого функцией time(), использующей time.h.

  srand( time( NULL ) );

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

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

Так каков же лучший метод перетасовки списка? Разрезание печатных листов? Сомневаюсь. Обмен случайных элементов несколько тысяч раз? Эффективно, но медленно и не гарантирует, что все элементы будут иметь шанс на перемещение. Лучше будет взять каждый элемент списка и поменять его местами с каким-нибудь другим. Например, предположим, что мы имеем список из 52 игральных карт с номерами от 0 до 51.  Для перетасовки карт сделаем следующее:

  int deck[ 52 ];
  int newpos;
  int savecard;
  int i;

  for ( i=0; i<52; i++ )
      deck[i] = i;
  printf( "Deck was " );
  for ( i=0; i<52; i++ )
      printf( "%d ", deck[i] );
  printf( "\n" );
  for ( i=0; i<52; i++ ) {
      newpos = rnd(52)-1;
      savecard = deck[i];
      deck[i] = deck[newpos];
      deck[newpos] = savecard;
  }
  printf( "Расклад таков: " );
  for ( i=0; i<52; i++ )
      printf( "%d ", deck[i] );
  printf( "\n" );

В результате получим расклад до и после:

Было 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
Стало 35 48 34 13 6 11 49 41 1 32 23 3 16 43 42 18 28 26 25 15 7 27 5 29 44 2 47 38 39 50 31 17 8 14 22 36 12 30 33 10 45 21 46 19 24 9 51 20 4 37 0 40

Различные типы случайностей
Люди, знакомые со статистикой, знают, что многие реальные жизненные события не подчиняются закону равномерного распределения. Первый капитальный ремонт автомобиля, например, может потребоваться между 5 и 9 годом после приобретения, но это чаще случается на 7-й год. Любой год в этом диапазоне вероятен, но наибольшую вероятность имеет середина диапазона.

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

int normal_rnd( int max ) {
  return (rnd( max ) + rnd( max ) + rnd( max ) + rnd( max ) +
         rnd( max ) + rnd( max ) + rnd( max ) + rnd( max ) ) / 8;

}

Используя normal_rnd() в тестовой функции, мы получаем значения, которые распределены в средней точке между 1 и max:

  for normal_rnd(), graph[1..10] is 0 0 4 26 37 23 10 0 0 0

Нормальные случайные числа могут быть использованы, чтобы сделать игру более правдоподобной, делая поведение врагов более устойчивым.

Для чисел, искаженных к концу диапазона, мы можем создать low_rnd() с приоритетом около 1.

  int low_rnd( int max ) {
    int candidate;

    candidate = rnd( max );
    if ( rnd( 2 ) == 1 )
       return candidate;
    else if ( max > 1 )
       return low_rnd( max / 2 );
    else
       return 1;
  }

В каждой рекурсии low_rnd() делит диапазон пополам.   Вычитая наименьшее случайное число из наибольшего в диапазоне, мы можем записать соответствующие значения high_rnd(), где приоритет отдается числам, расположенным около max:

  int high_rnd( int max ) {
    return max - low_rnd( max ) + 1;
  }

Искажения легко обнаруживаются с помощью тестовой программы:

  для low_rnd(), graph[1..10] is 36 15 11 8 9 3 4 3 3 8
  для high_rnd(), graph[1..10] is 4 5 8 5 4 10 6 10 14 34

Случайные условные операторы
Случайные ветви в логике могут быть получены с помощью функции odds()

  int odds( int percent ) {
       if ( percent <= 0 )
          return 0;
       else if ( percent > 100 )
          return 1;
       else if ( rnd( 100 ) <= percent )
          return 1;
       return 0;
  }

Эта функция возвращает значение "Истина" в течение указанного процент от заданного времени, тем самым облегчая объединение с условными операторами типа if.

  if ( odds( 50 ) )
    printf( "Пещера не обрушилась!\n" )
else
   printf( "О, черт - не повезло! Вы погребены заживо в груде камней.\n" );

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

Copyright (C) 2001, Ken O. Burtch.
Copying license http://www.linuxgazette.com/copying.html
Published in Issue 63 of Linux Gazette, Mid-February (EXTRA) 2001
[Источник: Русская версия "Linux Gazette"]

Так вот, продолжим, пост взят со всем известного RF-cheats:

Исследование алгоритма заточки предметов

Итак, благодаря одному из участников форума(а конкретнее Airsimer, за что ему большое спасибо) мне в руки попались исходники сервера RF Online Giga3. Скажу сразу - версия старая, серверов на ее основе сейчас практически нет и современная ситуация может сильно отличаться от описанной. Тем более, исходники неполные и в рабочий сервер скомпилировать их мне не удалось.

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

Хочу сразу разочаровать любителей рецептов типа "убить флема в новолуние, забрать лут и выкинуть перед Героем помахав рукой - 100% точка!" - таких алгоритмов в исходниках мне обнаружить не удалось. Конечно, тут могут возразить - "а как же точатся на +7, я сам видел!". Точатся. Но не обычным способом, а с помощью одного финта, о котором я расскажу ниже.

Итак, главный вывод, который я вынес из просмотра исходников - Корейский Рандом существует!
Именно так - основная функция, с помощью которой оценивается успешная заточка и последствия неуспешной - стандартная функция С rand(). Вообще по стандарту эта функция возвращает случайное число типа float в промежутке от 0 до 1. Единственное, что влияет на ее значение - так называемое начальное значение, задаваемое функцией srand(). Так вот, начальное значение этой функции является текущее время, вернее, его преобразованное числовое значение

PHP код:
srand((unsigned)time(NULL));
Но это знание ничего нам не дает, кроме того, что рецепты типа "точись в полночь!" не так уж и необоснованы.

Идем дальше.

За заточку предмета отвечает функция pc_UpgradeItem, находящаяся в файле player.cpp. Рассмотрим ее подробнее.

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

Дальше начинается самое интересное.

1. Устанавливается рейт на основании использованных камней. Рейты каждого камня берутся из базы и суммируются. Рейт без камня - 0,125.
PHP код:
for(int i = 0; i < upgrade_jewel_num; i++)
{
if(!pJewelFld[i])
   fRate += 0.125;
else
   fRate += pJewelFld[i];
}
2. Далее вычисляется рейт вещи в зависимости от ее уровня

PHP код:
BYTE GetItemUpgedLv(DWORD dwLvBit)
{
    BYTE byLv = 0;
    for(int g = 0; g < MAX_ITEM_LV; g++)
    {
        BYTE byTemp = (BYTE)((dwLvBit>>(g*4))&0x0000000F);
        if(byTemp == __NO_TALIK)
            break;
        byLv++;
    }
    return byLv;
}
конструкция не совсем ясна, но насколько я понял, вычисляемый левел - количество УЖЕ вставленных таликов - каждый бит переменной dwLvBit соответствует вставленному талику. Левелов всего 7, что вполне естественно. Похоже, от типа вставленных таликов зависимости нет.
Небольшое дополнение - рейт вещи вычисляется на основании вставленных таликов + учитывается вставляемый талик. Т.е. при расчете вещь считается уже проталеной, поэтому далее в конструкциях switch - case есть число 7.

3. Вычисляется общий, базовый рейт
PHP код:
dwTotalRate = s_dwItemUpgSucRate[byLv]*fRate/upgrade_jewel_num)*1000;
значение s_dwItemUpgSucRate зависит от левела и является массивом
s_dwItemUpgSucRate[] = {100, 75, 50, 25, 10, 5, 1};

4. Берется рандом.

PHP код:
DWORD dwR1 = rand();
DWORD dwRand = (dwR1<<16)+rand();
5. Первая проверка - талик вставится или сгорит

dwTotalRate <= dwRand%100000

сравнивается базовый рейт и рандом.

6. если первая проверка прошла(базовый рейт меньше либо равен рандому) идет проверка - сгорят ли уже вставленные талики
PHP код:
switch(byLv)
            {
            case 5:
                if(125 > ::rand()%1000)
                    bTalikBreak = true;
                break;
            case 6:
                if(250 > ::rand()%1000)
                    bTalikBreak = true;
                break;
            case 7:
                if(500 > ::rand()%1000)
                    bTalikBreak = true;
                break;
            }
это зависит от рейта вещи, т.е. уже вставленных таликов и.... заново вычиляемого рандома.

7. Если талики не сгорают, то вычисляется поломка вещи

PHP код:
bool bItemBreak = false;
switch(byLv)
{
    case 5:
        if(125 > ::rand()%1000)
        bItemBreak = true;
        break;
    case 6:
        if(250 > ::rand()%1000)
        bItemBreak = true;
        break;
    case 7:
        if(500 > ::rand()%1000)
        bItemBreak = true;
            break;
Опять же, зависит от рейта вещи и заново вычисляемого рандома.

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

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

Да, насчет точки +7. В исходнике имеется следующая конструкция:

if(m_bCheat_100SuccMake)
dwTotalRate = 0xFFFFFFFF;

эта переменная при установке ее в значение true дает 100% шанс создания и модификации предмета.
переменная является параметром чара и устанавливается владельцем базы. возможно (ТОЧНО, и это уже давно известно - примечание меня   ), GM имеют такой флаг и без проблем делают пухи +7. Обычным методом заточить на +7 очень маловероятно.

(с)Saaleb