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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Что из этого более случайное?

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

Answer 3

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

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

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

Answer 4

Сначала определите «правильное» распределение. Случайные числа, ну, в общем, случайные - результаты, которые вы видите, полностью соответствуют (псевдо) случайности.

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

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

Answer 5

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

Я написал простую реализацию типа Shuffle Bag в Ruby и провел некоторое тестирование. Реализация сделала это:

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

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

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

Вот мясо моего 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% и сохраняет краткосрочные пробежки в хорошем настроении.

Answer 6

Как насчет замены mt_rand () на что-то подобное?

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

С XKCD .

Answer 7

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

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

Проблема, которую он решает, заключается в следующем (извлечение):

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

Answer 8

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

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

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

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

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

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

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

Answer 9

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

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

Answer 10

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

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