Необходим предсказуемый генератор случайных чисел - PullRequest
151 голосов
/ 26 мая 2009

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

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

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

Ответы [ 37 ]

223 голосов
/ 26 мая 2009

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

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

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

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

113 голосов
/ 26 мая 2009

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

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

enter image description here enter image description here

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

88 голосов
/ 26 мая 2009

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

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

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

53 голосов
/ 26 мая 2009

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

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

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

39 голосов
/ 26 мая 2009

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

Я написал простую реализацию типа 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% и сохраняет краткосрочные пробежки в хорошем настроении.

35 голосов
/ 26 мая 2009

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

XKCD comic (RFC 1149.5 specifies 4 as the standard IEEE-vetted random number.)

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

С XKCD .

34 голосов
/ 26 мая 2009

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

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

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

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

19 голосов
/ 26 мая 2009

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

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

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

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

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

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

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

8 голосов
/ 26 мая 2009

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

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

8 голосов
/ 26 мая 2009

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...