Потребность в предсказуемом случайном генераторе

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

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

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

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

Я написал простую сумку в случайном порядке, как в Ruby, и сделал некоторые тесты. Реализация сделала это:

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

Он считается несправедливым на основе граничных вероятностей. Например, для вероятности 20% вы можете установить 10% в качестве нижней границы и 40% в качестве верхней границы.

Используя эти границы, я обнаружил, что при прогонах 10 ударов, 14,2% случаев, когда истинная псевдослучайная реализация давала результаты, которые были вне этих границ . Примерно в 11% случаев, 0 критических ударов были забиты в 10 попытках. 3,3% времени, 5 или более критических ударов были высажены из 10. Естественно, используя этот алгоритм (с минимальным количеством рулонов 5), гораздо меньшее количество (0,03%) пробелов «Fairish» было за пределами границ , Даже если приведенная ниже реализация не подходит (возможно, более умные вещи можно сделать, конечно), стоит отметить, что часто пользователи могут почувствовать, что это несправедливо с реальным псевдослучайным решением.

Вот мясо моего FairishBag написанного на Ruby. Вся реализация и быстрое моделирование методом Монте-Карло доступны здесь (gist) .

 def fire! hit = if @rolls >= @min_rolls && observed_probability > @unfair_high false elsif @rolls >= @min_rolls && observed_probability < @unfair_low true else rand <= @probability end @hits += 1 if hit @rolls += 1 return hit end def observed_probability @hits.to_f / @rolls end 

Обновление. Использование этого метода увеличивает общую вероятность получения критического попадания, примерно до 22%, используя границы выше. Вы можете компенсировать это, установив свою «реальную» вероятность немного ниже. Вероятность 17,5% с помощью волшебной модификации дает наблюдаемую долгосрочную вероятность около 20% и сохраняет справедливость в краткосрочной перспективе.

Это означает, что 1 из 5 хитов должен быть критическим. Проблема в том, что у меня очень плохие результаты в реальной жизни – иногда игроки получают 3 крита в 5 хитов, иногда ни один из 15 хитов.

Вам нужна сумка для тасования . Это решает проблему случайного случайности, которая слишком случайна для игр.

Алгоритм примерно такой: вы поставили 1 критический и 4 некритических попадания в сумку. Затем вы производите свой заказ в сумке и выбираете их по одному. Когда сумка пуста, вы снова заполняете ее теми же значениями и производите ее. Таким образом, вы получите в среднем 1 критический удар за 5 ударов и не более 2 критических и 8 некритических ударов подряд. Увеличьте количество предметов в сумке для большей случайности.

Вот пример реализации (в Java) и ее тестовых примеров, которые я написал некоторое время назад.

У вас есть непонимание того, что означает случайное.

Какие из них более случайны?

введите описание изображения здесь введите описание изображения здесь

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

Учитывая поведение, о котором вы просите, я думаю, что вы производите неправильную переменную.

Вместо того, чтобы рандомизировать, будет ли этот удар критическим, попробуйте рандомизировать количество оборотов до следующего критического попадания. Например, просто выберите число между 2 и 9 каждый раз, когда игрок получает критический момент, а затем дайте им следующий критический после того, как прошло много раундов. Вы также можете использовать методы кубиков, чтобы приблизиться к нормальному распределению – например, вы получите следующий критический момент в 2D4 оборотах.

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

Сначала определите «правильное» распределение. Случайные числа, ну, случайные – результаты, которые вы видите, полностью согласуются с (псевдо) случайностью.

Расширяясь на этом, я предполагаю, что вам нужно какое-то чувство «справедливости», поэтому пользователь не может пройти 100 оборотов без успеха. Если это так, я буду отслеживать количество сбоев с момента последнего успеха и взвешивать сгенерированный результат. Предположим, вы хотите, чтобы 1 из 5 рулонов «преуспел». Таким образом, вы произвольно генерируете число от 1 до 5, и если оно 5, отлично.

Если нет, запишите сбой и в следующий раз сгенерируйте число от 1 до 5, но добавьте слово «floor» (numFailures / 2). Так что на этот раз, опять же, у них есть шанс 1 на 5. Если они терпят неудачу, в следующий раз выигрышный интервал составляет 4 и 5; шансы на успех в 2-5. С этими вариантами, после 8 неудач, они наверняка преуспеют.

Как насчет замены mt_rand () на что-то вроде этого?

XKCD comic (RFC 1149.5 указывает 4 как стандартное случайное число, прошедшее IEEE).

(RFC 1149.5 определяет 4 как стандартное случайное число, прошедшее проверку IEEE.)

Из XKCD .

Надеюсь, эта статья поможет вам: http://web.archive.org/web/20090103063439/http://www.gamedev.net:80/reference/design/features/randomness/

Этот метод генерации «случайных чисел» распространен в играх rpg / mmorpg.

Проблема, которую он решает, – это (выдержка):

Паук лезвия у вас в горле. Он бьет, и вы пропустите. Он снова бьет, и вы снова пропустите. И снова и снова, пока вам не удастся попасть. Ты мертв, и над твоим трупом раздался двухтонный арахнид. Невозможно? Нет. Невероятно? Да. Но, учитывая достаточно игроков и учитывая достаточно времени, невероятное становится почти уверенным. Дело не в том, что лезвие паука было трудным, это была просто невезение. Как расстраивает. Этого достаточно, чтобы заставить игрока хотеть бросить курить.

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

Для хорошего подробного и обширного анализа этого домена см. Мудрость программирования AI Game 2 . Вся книга стоит прочитать для любого разработчика игр, идея «казалось бы случайных чисел» обрабатывается в главе:

Отфильтрованная случайность для решений ИИ и игровой логики :

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

Вы также можете найти другую главу:

Статистика случайных чисел

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

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

Возможно, что вы хотите, это порог милосердия … помните последние 10 рулонов, и если они не получили критического удара, дайте им халяву. Разгладьте стропы и стрелы случайности.

Вашим лучшим решением может быть тестирование игр с несколькими различными неслучайными схемами и выбрать тот, который сделает игроков счастливыми.

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

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

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

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

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

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

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

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

Лично я не согласен, что 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 цента ...

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

Вместо указания 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) 

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

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

Если вы это сделаете, сообщите мне, как это происходит!

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

например

 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%.

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вам нужно, чтобы это было более причудливо, это довольно легко добавить в большее количество. Вы можете ограничить количество, которое progressiveChance может получить, чтобы избежать 100% -ной критической вероятности или сбросить его на определенные события. Вы также можете увеличить progressiveChance в меньших количествах, каждый из которых будет повышаться с помощью чего-то вроде progressiveChance + = (1 - progressiveChance) * SCALE, где SCALE <1.

Ну, если вы немного учитесь математике, вы, вероятно, можете попробовать Exponential distribution

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

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

Принимая 20% -ный шанс крита, у вас есть

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

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

Надеюсь, тебе все равно не надоедает до смерти.

Что делать с критической зависимостью от последних N атак. Одна простая схема – это какая-то цепочка марков: http://en.wikipedia.org/wiki/Markov_chain, но код очень прост в любом случае.

 IF turns_since_last_critical < M THEN critial = false turns_since_last_critical++; ELSE critial = IsCritical(chance); IF Critial THEN turns_since_last_critica = 0; ELSE turns_since_last_critica++; END IF; END IF; 

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

OP,

В значительной степени, если вы хотите, чтобы это было честно, это не будет случайным.

Проблема вашей игры – это фактическая длина матча. Чем дольше матч, тем меньше вероятность того, что вы увидите (криты будут составлять 20%), и это приблизится к вашим намеченным значениям.

У вас есть два варианта: предварительно вычислить атаки на основе предыдущих бросков. Который вы получите один крит каждые 5 атак (на основе ваших 20%), но вы можете сделать заказ случайным.

listOfFollowingAttacks = {Хит, Хит, Хит, Мисс, Крит};

Это шаблон, который вы хотите. So make it choose randomly from that list, until its empty, them re-create it.

That’s a pattern I created for my game, it works quite well, for what I want it to do.

your second option, would be, increase the chance to crit, you are probably going to see a more even number in the end of all attacks(presuming that your matches ends rather quickly). The less % chance, the more RNG’d you get.

You are looking at a linear distribution, when you probably want a normal distribution.

If you remember back in your youth playing D&D, you were asked to roll multiple n-sided die, then sum the results.

For instance, rolling 4 x 6-sided die is different than rolling 1 x 24-sided dice.

City of Heroes actually has a mechanic called the “streakbreaker” that solves exactly this problem. The way it works is that after a string of misses of a length related to the lowest to-hit probability in the string, the next attack is guaranteed to be a hit. For example if you miss an attack with over 90% to hit chance then your next attack will auto hit, but if your hit chance is lower like 60% then you’ll need to have several consecutive misses to trigger the “streakbreaker” (I don’t know the exact numbers)

alt text

this one is really predictable… but you can never be sure.

How about weighting the value?

For example, if you have a 20% chance to critical hit, generate a number between 1 and 5 with one number representing a critical hit, or a number between 1 and 100 with 20 numbers being a critical hit.

But as long as you are working with random or pseudorandom numbers, there’s no way to potentially avoid the results you are currently seeing. It’s the nature of randomness.

Reaction on: “The problem is I got very bad real life results — sometimes players get 3 crits in 5 hits, sometimes none in 15 hits.”

You have a chance of somewhere between 3 and 4 % of getting nothing in 15 hits…

I would propose the following “randomly delayed putback die”:

  • Maintain two arrays, one ( in-array ) initially filled with the values from 0 to n-1, the other ( out-array ) empty
  • When a result is requested:
    • return a random value from all defined values in in-array
    • move this value from in-array to out-array
    • move one random (over all elements, including the undefined!) element from out-array back into in-array

This has the property that it will “react” more slowly the bigger n is. For example, if you want a 20% chance, setting n to 5 and hitting on a 0 is “less random” than setting n to 10 and hitting on a 0 or 1, and making it 0 to 199 out of 1000 will be almost indistinguishable from true randomness over a small sample. You will have to adjust n to your sample size.

Pre-calculate a random critical hit for each player.

 // OBJECT //... // OnAttack() //... c_h = c_h -1; if ( c_h == 0 ) { // Yes, critical hit! c_h = random(5) + 1 // for the next time // ... } 

I think perhaps you are using the wrong random distribution function. You probably don’t want an even distribution over the numbers. Try a normal distribution instead so that the critical hits become more uncommon than the ‘regular’ hits.

I work with Java so I’m not sure where you can find something for C++ that gives you random numbers with a normal distribution but there has to be something out there.

  • Сбой при выдаче результата arc4random () в Int
  • Последовательно создайте один и тот же случайный массив numpy
  • Случайный взвешенный выбор
  • Генерировать N случайных и уникальных чисел в пределах диапазона
  • Генерация перетасованного диапазона с использованием PRNG, а не перетасовка
  • Понимание «случайности»
  • Создание случайных чисел в массиве
  • канонический способ рандомизации NSArray в Objective C
  • Случайные / шумовые функции для GLSL
  • Каков наилучший способ вернуть случайную строку в текстовый файл с помощью C?
  • Зачем использовать class C # System.Random вообще, а не System.Security.Cryptography.RandomNumberGenerator?
  • Давайте будем гением компьютера.