[Перевод] Генератор случайных чисел, застрявший на одном значении
Моё исследование посвящено мини-игре Green Toad House в New Super Mario Bros (NSMB). В этой мини-игре используется случайность, поэтому в процессе я изучил генератор случайных чисел (RNG) NSMB.
Чтобы пост не был слишком длинным, будем считать, что вы знаете, что такое RNG, а также о концепции порождающих значений (seed). Если нет, то вот хорошие ресурсы для изучения: pannenkoek2012 в YouTube (SM64), Retro Game Mechanics Explained в YouTube (SMW), Википедия.
Исследуем функцию
Для начала рассмотрим ручную декомпиляцию генератора случайных чисел NSMB, который я назвал rand_nsmb:
uint32_t rand_nsmb(uint32_t *state) {
uint64_t value = (uint64_t)(*state) * 1664525 + 1013904223;
return *state = value + (value >> 32);
}Функция RNG, следующий результат которой вычисляется как предыдущий результат, умноженный на константу, плюс другая константа, называется линейным конгруэнтным генератором (LCG). Показанная выше функция почти полностью совпадает с LCG. Единственное, что её отличает — это + (value >> 32) в конце.
Когда вы находите неизвестный код со странными большими константами, то можете многое узнать о нём, загуглив их. Если поискать 1664525 и 1013904223, то можно обнаружить, что они очень часто используются совместно в функциях LCG1, а изначально были опубликованы в книге Numerical Recipes. В книге функция LCG на основе этих двух чисел названа «ranqd1» («random quick-and-dirty generator 1»). В дальнейшем я буду использовать это название для такого LCG.
Для сравнения приведу реализацию ranqd1 (не скопированную из книги), соответствующую форматированию из примера rand_nsmb выше:
uint32_t ranqd1(uint32_t *state) {
uint64_t value = (uint64_t)(*state) * 1664525 + 1013904223;
return *state = value;
}С учётом этого, можно с уверенностью заявить, что в рамках этого анализа значения распределены равномерно.
Примечание о порождающих значениях
Насколько я понимаю, процедура выбора порождающего значения (seed) RNG в игре NSMB при её запуске надёжна. Она собирает энтропию из различных источников, в том числе и текущее время загрузки игры, текущий номер растровой строки, состояние GPU, нажатые кнопки и так далее. Затем она вычисляет хэш SHA-1 всего этого и выполняет XOR, преобразуя значение в 32-битное целое число.
С учётом этого, можно с уверенностью заявить, что в рамках этого анализа значения распределены равномерно.
Если не считать отсутствующего + (value >> 32), функция идентична rand_nsmb.
ranqd1 обладает очень приятным свойством: перед повторением значений он циклично обходит каждое 32-битное целое число2 (совершает «полный цикл»), и в общем случае (согласно Numerical Recipes) «не хуже любого другого 32-битного линейного конгруэнтного генератора».
То есть функция RNG игры — это просто ranqd1 (качественный LCG), но с одним небольшоим дополнением. Nintendo прибавляет биты, которые в противном случае были бы обрезаны при косвенном преобразовании типа в uint32_t во время возврата. Поначалу кажется, что это должно быть хорошим решением — мы не теряем эту достаточно случайную информацию, а используем её повторно!
Но здесь есть проблема: генерация случайных чисел — одна из тех областей, в которых вообще не стоит экспериментировать с проверенными формулами, если вы не уверены точно в том, что вы делаете. И как мы вскоре увидим, это изменение принесло больше проблем, чем преимуществ.
Циклы
Выше я говорил, что до повторения значений ranqd1 циклично обходит каждое 32-битное целое значение. Из-за внесённого в NSMB изменения это свойство сохраняется не всегда, поэтому я решил провести тщательный анализ цикла rand_nsmb.
Я написал на C программу, которая итеративно обходит каждое 32-битное число и подставляет их в rand_nsmb, а затем следующее число по получившемуся следу значений RNG, пока она не доберётся до дубликата. Для решения такой задачи хорошо подходит динамическое программирование; моя программа записала информацию о каждом seed (в каком цикле он оказывается и сколько шагов ему потребовалось, чтобы достичь его) в огромный файл с таблицей данных на 20 ГБ. Даже несмотря на то, что файл сохранялся на внутренний SSD моего ноутбука, для выполнения программы потребовалось примерно две недели. Закончив с этим, я мог быстро ответить на множество вопросов, линейно прочитав файл вывода с помощью (что заняло примерно полчаса3) и вычислив интересовавшую меня статистику.
И вот, что я выяснил.
Для начала давайте рассмотрим средний случай. При случайном начальном rand_nsmb в среднем повторит свой вывод спустя 1820529 вызовов. Хоть это и далеко от 4294967296 вызовов, необходимых для повторения числа функции ranqd1, для подобной видеоигры этого всё равно вполне достаточно.
Интереснее было исследовать наихудшие случаи. Насколько маленький цикл вы получите, если перед запуском игры вам перебежит дорогу чёрная кошка с пустыми вёдрами? Вот отсортированный по длине список всех 1653 циклов rand_nsmb и круговая диаграмма с количеством соответствующих состояний:
Количество seed, приводящих к различным длинам цикла
1 цикл длиной 1708724
1 цикл длиной 354835
1 цикл длиной 155834
1 цикл длиной 146318
1 цикл длиной 127646
1 цикл длиной 81673
1 цикл длиной 48534
1 цикл длиной 26128
1 цикл длиной 1371
1630 циклов длиной 8
12 циклов длиной 4
1 цикл длиной 2
1 цикл длиной 1
Примерно ¾ всех состояний попадают в наибольший цикл длиной 1,7 миллиона состояний. За ним следует множество уменьшающихся циклов, занимающих аналогично уменьшающиеся секторы круговой диаграммы. Не знаю, почему так много циклов длиной 8, но это не важно.
Взгляните на конец списка. Там есть двенадцать циклов длиной в 4 состояния, один в 2 состояния и один… в одно состояние.
Эта функция RNG имеет фиксированную точку.
Вот она: 1144735523. Вы можете проверить это самостоятельно при помощи интерактивного виджета rand_nsmb из оригинала статьи — rand_nsmb(1144735523) возвращает 11447355234.
Генератор случайных чисел, способный бесконечно выдавать одно и то же число, мягко говоря, неидеален.
Фиксированная точка
Влияние на геймплей
Каково будет играть в NSMB, когда её функция RNG застрянет на единственном числе?
Чтобы получить вероятность в 90% попадания в фиксированную точку rand_nsmbo, вам придётся запустить игру 1,9 миллиарда раз, но чуть быстрее этого можно достичь при помощи хакинга. Для этого можно воспользоваться патчем кода NSMBe.
Я полностью прошёл игру таким образом. Вот некоторые из найденных мной странностей:
Тайлы не рандомизированы (верхняя анимация). Этот баг влияет на большинство уровней, но особенно очевиден в начале 1–2.
Некоторые звуковые эффекты не рандомизированы. При двойном прыжке и прыжке от стены всегда воспроизводятся одни и те же звуки, а не выбираются случайно из нескольких.
Решение в Green Toad House всегда одинаково. И оно по случайности5 всегда совпадает с порядком, в котором Toadsworth помещает карты в блоки.
Пузыри из труб исходят из одной точки (вторая анимация). Обычно они исходят из разных точек вдоль края трубы.
Некоторые враги с непредсказуемыми паттернами атак становятся предсказуемыми. В частности, Skeeter, Hammer Bro и Sledge Bro — последний никогда не создаёт землетрясение.
Большие растения-пираньи при убийстве их огнём выбрасывают монеты неестественным образом (нижняя анимация). Монетки вылетают не в разных направлениях, как из фонтана, а в одном.
…Несмотря на шестьсот вызовов RNG в коде игры, она не очень активно использует случайность так, чтобы это непосредственно влияло на геймплей. Учитывая всё вышесказанное, наверно, это и к лучшему.
Мне хотелось бы напомнить, что показанные выше видео были записаны благодаря взлому игры, однако это вполне реальный баг, который с ненулевой вероятностью может возникнуть естественным образом. И я задался вопросом: можем ли мы примерно вычислить количество игроков, на которых он повлиял?
Оценка количества игроков, на которых повлиял баг
К фиксированной точке rand_nsmb приводит 5 значений seed6, то есть вероятность столкнуться с ней при загрузке игры равна (5 / 0×100000000) ≈ 0,0000001164%.
На март 2020 года New Super Mario Bros. была продана тиражом 30,8 миллиона копий7. Чтобы грубо прикинуть, допустим, что каждый купивший её игрок запустил игру десять раз. То есть суммарно NSMB запустили… давайте округлим это значение до 300 миллионов раз.
Вероятность того, что никто не столкнулся с багом тогда равна (1 — 0,0000001164%)300,000,000 ≈ 70%, то есть существует вероятность 30%, что с ней столкнулся хотя бы один человек.
Вероятность в 30% того, что кому-то не повезло столкнуться с фиксированной точкой, не так уж велика. Но если также учесть 10 seed, приводящих к циклу из двух значений (а их нужно учесть, ведь цикл из двух случайных значений почти столь же ужасен), то есть вероятность 65%, что с ней столкнулся хотя бы один человек. Если добавить ещё 240 seed, приводящих к циклу из четырёх значений, то кто-то практически гарантированно (99,999998%) наткнулся на чрезвычайно плохой seed RNG.
Более профессиональный подход
Такой ручной анализ вполне приемлем и интересен, и благодаря нему я даже заметил ещё несколько неравномерностей, связанных с делением. Однако профессионалы обычно анализируют генераторы случайных чисел не так. Специалисты применяют статистические тесты, проверяющие множество разных аспектов. Чтобы получить более строгие результаты, я пропустил rand_nsmb через автоматизированный набор тестов RNG Dieharder.
Линейные конгруэнтные генераторы проектируется так, чтобы быть быстрыми, а не для прохождения статистических тестов, поэтому будет несправедливо, если бы мы просто смотрели на процент пройденных rand_nsmb тестов, не сравнивая её ни с чем. Поэтому я взял исходную функцию ranqd1. Это позволит нам непосредственно измерить влияние изменения, внесённого в код Nintendo.
Все тесты основаны на одном исходном seed (0), поэтому рассмотренные выше проблемы малых циклов не отражены в результатах. 0 приводит к наибольшему циклу, обеспечиваемому rand_nsmb, так что это максимально щедрый к алгоритму выбор.
Для выполнения тестов на моём ноутбуке потребовалось чуть меньше дня. Все результаты выложены на github. В графике выше показано общее количество пройденных тестов.
К чести rand_nsmb, она обгоняет по показателям ranqd1 в 35 из 114 тестов (31%), поэтому в каком-то смысле можно считать эту функцию более совершенной, чем оригинал. Но всё равно, если смотреть на результаты в целом, становится очевидно, что в общем случае она проявляет себя хуже.
В заключение
Никто из играющих в New Super Mario Bros. не заметит, что генератор случайных чисел игры проваливает какие-то непонятные статистические тесты; да это и не должно волновать игроков. Очевидно, что rand_nsmb не обязана быть криптографически сильной, и в более чем 99% случаев она идеально справляется со своей задачей. В основном меня беспокоит то, что разработчики зачем-то изменили функцию так, что она вызывает в некоторых случаях ужасное поведение, с которым вполне можно столкнуться во время обычной игры (хоть это и маловероятно).
Если система не поломана (и создана гораздо более опытными людьми), то не чините её.
«Linear congruential generator» («Parameters in common use») — Википедия.
«Random number information — The nature of randomness» — RandomNumberGenerator.com.
Если вы теперь думаете, что у меня медленный SSD… то нет, после полной генерации я переместил файл на другой накопитель.
Вот ещё несколько интересных входных чисел, которые можно попробовать в интерактивном виджете: 2576391288 (цикл из двух значений), 49939938 (первый цикл из четырёх значений), 459503 (первый цикл из восьми значений). ↩
Если бы фиксированная точка была каким-то другим числом, то это могло быть и не так.
285742064, 1144735523 itself, 2003728982, 2862722441 и 3721715900.
«Top Selling Title Sales Units» — Nintendo.
