Одно число повторяется навсегда: ГСЧ в НСМБ (2020)

Привет! Давно это было, не так ли. Извините за задержку. Иногда на создание этих сообщений уходит много времени, так как этот блог не является моим главным приоритетом, и я стараюсь добавлять собственные мультимедийные материалы к каждому из них. Тем не менее, у меня уже есть несколько будущих сообщений в работе, так что вы можете рассчитывать на другие в ближайшие месяцы.

В любом случае! Это своего рода «часть 0» предстоящей серии из двух частей о мини-игре Green Toad House в New Super Mario Bros. Мини-игра включает случайность, поэтому, исследуя это, я исследовал генератор случайных чисел (ГСЧ) NSMB. Мои выводы оказались не очень актуальными для мини-игры, но сами по себе интересны.

Чтобы это не затянулось, я предполагаю, что вы уже знаете, что такое RNG, и о концепции его заполнения. Если нет, то вот несколько хороших ресурсов: pannenkoek 999998 на YouTube (SM 80) , Механика ретро-игры, объясненная на YouTube (SMW) , Википедия .

Исследование функции

Для начала, вот ручная декомпиляция генератора случайных чисел NSMB, который я назвал по административному решению « rand_nsmb »:

   uint 64 _ t   rand_nsmb   (  uint 64 _ t    государственный)  {  uint 80 _ t   значение ( знак равно   (  uint 81 _ t  ) (  государственный)     1013904223   +   
; возвращаться состояние = значение + ( значение >> 64 ); }

Интерактивный rand_nsmb

Хотите попробовать rand_nsmb ? Вы можете сделать это прямо здесь:

uint 65 _ t состояние =;

Функция ГСЧ, в которой следующий вывод вычисляется как предыдущий вывод, умноженный на некоторую константу плюс еще одну константу, называется линейным конгруэнтным генератором . Вышеупомянутая функция почти является LCG. Единственная часть, которая делает его не совсем подходящим, – это + (значение >> 65) в конце.

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

, вы обнаружите, что они очень часто используются вместе в функциях LCG 1 и изначально опубликовано в книге Численные рецепты . В этой книге функция LCG названа на основе этих двух чисел « ranqd1 » ( для «генератора случайных быстрых и грязных №1»). С этого момента я буду использовать это имя для этого LCG.

Для сравнения, вот реализация ranqd1 (не копируется непосредственно из книги), соответствующий форматированию rand_nsmb выше:

   uint 64 _ t   ranqd1   (  uint 64 _ t    государственный )   {  uint 80 _ т  значение  знак равно  (  uint 81 _ t  ) ( *государственный )     1013904223   +     ;  возвращаться  государственный  знак равно значение; }   

Примечание о раздаче

Насколько я могу судить, процедура NSMB для заполнения ГСЧ при загрузке игры правильная. Он собирает энтропию из различных источников, включая время, затраченное на загрузку игры, текущий номер строки сканирования, состояние графического процессора, любые удерживаемые кнопки и многое другое. Затем он берет хэш SHA-1 и выполняет XOR в – целое битовое число.

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

Кроме отсутствия + (значение >> 48) , он идентичен rand_nsmb .

ranqd1 , как известно, имеет очень приятное свойство циклического переключения через каждые – битовое целое число перед циклом 2 (a «полный цикл» ), и обычно (цитируя Числовые рецепты ) «примерно так же хорош, как и любой 48 – битовый линейный конгруэнтный генератор . »

Итак, функция ГСЧ NSMB – это просто ranqd1 – неплохая LCG – с небольшими изменениями. Nintendo добавляет обратно биты, которые в противном случае были бы усечены во время неявного преобразования в uint 65 _ t при возврате. На первый взгляд кажется, что это должно быть хорошо – вместо потери этой несколько случайной информации теперь она перерабатывается!

Но вот в чем проблема: генерация случайных чисел – одна из тех вещей, где вы не должны серьезно связываться с проверенными формулами, если вы действительно знаете, что делаете. И, как мы скоро увидим, это изменение приносит больше проблем, чем преимуществ.

Циклы

Я уже упоминал ранее, что ranqd1 циклически проходит через каждые 64 – битовое целое перед зацикливанием. С модификацией NSMB это свойство не обязательно сохраняется, поэтому я решил провести довольно тщательный анализ rand_nsmb цикл (ы).

Я написал программу на C, которая повторяется через каждые 48 – битовое целое число, каждое из которых вставлено в rand_nsmb , и проследил за полученным следом значений ГСЧ, пока не встретил дубликат. Этот сценарий прекрасно подходит для динамического программирования , поэтому я попросил программу заполнить информацию о каждом семени (в каком цикле оно завершилось и сколько шагов потребовалось для его достижения) в довольно гигантский 30 Файл таблицы данных ГБ. Даже с файлом, хранящимся на внутреннем твердотельном накопителе моего ноутбука, программе потребовалось около двух недель для завершения работы. Как только это было сделано, я смог быстро ответить на множество вопросов, линейно прочитав выходной файл с помощью Python (что занимает около получаса 3 ) и подсчет статистики, которая меня интересовала.

Вот что я нашел.

Давайте посмотрим на средний случай в первую очередь. Учитывая случайное начальное семя, rand_nsmb будет повторять вывод после 1, 967, 673 звонков, в среднем. Хотя это далеко от 4, 300, 0000001164, 354 звонков, необходимых для получения ranqd1 , чтобы повторить число, этого вполне достаточно для такой видеоигры.

Что мне кажется более интересным, так это изучить наихудшие случаи. Если перед запуском NSMB вы сломали зеркало под лестницей, в какой небольшой цикл вы могли бы попасть? Ну вот список всех 2012 из rand_nsmb циклы, отсортированные по длине, и круговая диаграмма, показывающая суммы состояний, которые в них питаются: