Необходим предсказуемый генератор случайных чисел

Question

Я разработчик веб-игр, и у меня возникла проблема со случайными числами. Допустим, у игрока есть 20% шанс получить критический удар своим мечом. Это означает, что 1 из 5 попаданий должен быть критическим. Проблема в том, что я получил очень плохие результаты в реальной жизни & mdash; иногда игроки получают 3 крита в 5 попаданиях, иногда ни одного в 15 попаданиях. Сражения довольно короткие (3-10 попаданий), поэтому важно получить хорошее случайное распределение.

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

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

Answer 1

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

Если вы хотите, чтобы 1 из каждых 5 попаданий были критическими, просто выберите число от 1 до 5 и скажите, что это попадание будет критическим.

Answer 2

mt_rand () основана на реализации Mersenne Twister , что означает, что она дает одно из лучших случайных распределений, которые вы можете получить.

Очевидно, что вы хотите совсем не случайность, поэтому вам следует начать с точного указания того, что вы хотите. Вы, вероятно, поймете, что у вас противоречивые ожидания - что результаты должны быть действительно случайными и не предсказуемыми, но в то же время они не должны демонстрировать локальные отклонения от заявленной вероятности - но тогда это становится предсказуемым. Если вы установили максимум 10 не-критов подряд, то вы просто сказали игрокам: «Если у вас было 9 не-критов подряд, следующий будет критическим со 100% уверенностью» - вы можете ну вообще не заморачивайся случайностью.

Answer 3

При таком небольшом количестве тестов вы должны ожидать такие результаты:

Истинная случайность предсказуема только при большом размере набора, так что вполне возможно подбросить монету и получить головы 3 раза подряд, однако после нескольких миллионов бросков вы получите примерно 50-50.

Answer 4

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

Лично я не согласен, что 3 крита подряд это плохо. Также я не согласен, что 15 не критов подряд - это плохо.

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

int base_chance = 20;
int current_chance = base_chance;

int hit = generate_random_number(0, 100) + 1; // anything from 1 to 100
if(hit < current_chance)//Or whatever method you use to check
{
    //crit!
    if(current_chance > base_chance)
        current_chance = base_chance; // reset the chance.
    else
        current_chance *= 0.8; // decrease the crit chance for the NEXT hit.
}
else
{
    //no crit.
    if(current_chance < base_chance)
        current_chance = base_chance; // reset the chance.
    else
        current_chance *= 1.1; // increase the crit chance for the NEXT hit.
    //raise the current_chance
}

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

Просто добавляю 2 цента ...

Answer 5

Несколько лучших ответов - отличные объяснения, поэтому я просто сосредоточусь на алгоритме, который дает вам контроль над вероятностью «плохих полос», в то время как никогда не становится детерминированным. Вот что я думаю тебе следует сделать:

Вместо указания p , параметра распределения Бернулли, которое является вашей вероятностью критического удара, укажите a и b , параметры бета-распределение, «сопряженный априор» распределения Бернулли. Вам необходимо отслеживать A и B , количество критических и некритических попаданий на данный момент.

Теперь, чтобы указать a и b , убедитесь, что a / (a ​​+ b) = p, шанс критического удара. Удобно то, что (a + b) количественно определяет, насколько близко вы хотите, чтобы A / (A + B) было к p в целом.

Вы делаете выборку так:

пусть p(x) будет функцией плотности вероятности бета-распределения. Он доступен во многих местах, но вы можете найти его в GSL как gsl_ran_beta_pdf.

S = A+B+1
p_1 = p((A+1)/S)
p_2 = p(A/S)

Выберите критическое попадание путем выборки из распределения Бернулли с вероятностью p_1 / (p_1 + p_2)

Если вы обнаружите, что у случайных чисел слишком много «плохих полос», увеличьте a и b , но в пределе, как a и b отправляйтесь в бесконечность, у вас будет подход к сумке в случайном порядке, описанный ранее.

Если вы реализуете это, пожалуйста, дайте мне знать, как это происходит!

Answer 6

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

, например

int GetRand(int nSize)
{
    return 1 + (::rand() % nSize);
}
int GetDice()
{
    static int nPrevious=-1;
    while (1) {
        int nValue = GetRand(6);
        // only allow repeat 5% of the time
        if (nValue==nPrevious && GetRand(100)<95)
            continue;
        nPrevious = nValue;
        return nValue;
    }
}

Этот код отклоняет повторные значения в 95% случаев, делая повторения маловероятными, но не невозможными. Статистически это немного некрасиво, но, вероятно, даст желаемые результаты. Конечно, это не помешает распространению типа "5 4 5 4 5". Вы можете стать хитрее и отказаться от второго (скажем) 60% времени, а третьего - от 30%.

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

Answer 7

Вы можете создать список, содержащий числа от 1 до 5, и отсортировать их по случайности. Затем просто просмотрите список, который вы создали. У вас есть гарантия того, что вы наберете каждый номер хотя бы раз ... Когда вы закончите с первыми 5, просто создайте еще 5 номеров ...

Answer 8

Ну, если вы немного разбираетесь в математике, вы можете попробовать Экспоненциальное распределение

Например, если лямбда = 0,5, ожидаемое значение равно 2 (прочитайте эту статью!), Это означает, что вы, скорее всего, будете нажимать / критические / что угодно каждый 2-й ход (например, 50%, а?). Но при таком распределении вероятностей вы будете точно пропускать (или делать что-то противоположное) на 0-м ходу (тот, в котором событие уже произошло и обнуление turn_counter), с вероятностью 40% попасть в следующий ход, около 65% шанс сделать это 2-й (следующий после следующего) ход, около 80%, чтобы попасть 3-й и т. д.

Вся цель этого распределения заключается в том, что если у человека есть 50% -й шанс попадания, и он пропускает 3 раза подряд, он будет уверенно (ну, с вероятностью более 80%, и он увеличивается с каждым следующим ходом). Это приводит к более «справедливым» результатам, сохраняя общую вероятность 50% без изменений.

Если у вас есть шанс 20% крита, у вас есть

• 17% к критическому 1-му ходу
• 32% к критическому второму ходу, если во всех предыдущих не было крит.
• 45% к криту 3-го хода, если крита не было во всех предыдущих.
• 54% к 4-му ходу критического удара, если во всех предыдущих не было крит.
• ...
• 80% к 8-му ходу критического удара, если во всех предыдущих не было крит.

Вероятность 3 крита + 2 не крита в 5 последовательных ходах все еще составляет около 0,2% (против этих 5%). И есть вероятность 14% для 4 последовательных не критов, 5% из 5, 1,5% для 6, 0,3% для 7, 0,07% для 8 последовательных не критов. Бьюсь об заклад, это «более справедливо», чем 41%, 32%, 26%, 21% и 16%.

Надеюсь, тебе до сих пор не скучно до смерти.

Answer 9

Я рекомендую прогрессивную процентную систему, которую использует Blizzard: http://www.shacknews.com/onearticle.x/57886

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

if ( randNumber <= .2 ) {
   //Critical
} else {
   //Normal
}

Все, что вам нужно сделать, это добавить прогрессивное увеличение базового шанса ...

if (randNumber <= .2 + progressiveChance ) {
   progressiveChance = 0;
   //Critical
} else {
   progressiveChance += CHANCE_MODIFIER;
   //Normal hit
}

Если вам нужно, чтобы он был более модным, его легко добавить еще. Вы можете ограничить сумму, которую может получить прогрессивный шанс, чтобы избежать 100% критического шанса или сбросить его при определенных событиях. Вы также можете получить увеличение прогрессивного шанса в меньших количествах при каждом повышении, например, прогрессивный шанс + = (1 - прогрессивный шанс) * МАСШТАБ, где МАСШТАБ <1. </p>

Answer 10

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

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

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

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

Кроме того, вы можете запомнить последние N значений, возвращаемых вашей случайной функцией, и взвесить результат по ним. (простой пример: «для каждого появления нового результата есть 50% -й шанс, что мы должны отбросить значение и получить новое»

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