Pac-Man — полностью детерминированная игра. Как я объяснял в своём видео об этой игре, все движения призраков зависят от того, где на текущий момент находится Pac-Man. Следовательно, обладая этими знаниями, можно точно спрогнозировать, куда будут двигаться призраки в любой момент времени. Но так ли это? Когда Pac-Man съедает большой шарик («энерджайзер»), призраки пугаются и начинают двигаться по паттерну, который кажется случайным и непредсказуемым. Это единственный момент, когда в игре используется генератор случайных чисел (RNG): для определения того, в каком направлении повернёт испуганный призрак на перекрёстке лабиринта. Хоть это решение тоже детерминировано, это единственный непредсказуемый элемент Pac-Man.  

В этой статье мы проведём глубокий анализ функции RNG игры и разберёмся, как призраки склонны действовать в этой ситуации. В конечном итоге мы выясним, что напуганных призраков обычно притягивает одна из областей лабиринта.

Генератор случайных чисел (random number generator, RNG), как можно понять из названия, отвечает за генерацию случайных чисел. У процессора, выполняющего код игры, нет источника случайности в виде монетки или кубика, поэтому эта функция пишется программно. Как оказалось, написать программу или функцию, подбирающую числа достаточно случайным образом, довольно сложно; можно даже сказать, что невозможно.

Написание кода генерации случайных чисел — это, по сути, создание списка команд для вычисления определённого значения. В таком случае, она на самом деле не случайна, а по-прежнему детерминирована. Однако если конечный результат выглядит достаточно случайным, можно работать с ним, как будто он на самом деле случайный, точнее, псевдослучайный.

В Pac-Man используется очень простая функция RNG, но с неожиданной особенностью. В памяти находится 16-битное значение, считающееся индексом RNG. В начале игры и каждого уровня оно равно нулю. Этот индекс используется в качестве порождающего значения (seed) для генерации следующего индекса, перезаписывающего старый. Например, самый первый генерируемый индекс — это число 1. Функция RNG получает в качестве входного значения число 0 и возвращает число 1. Когда в следующий раз потребуется случайное число, оно использует в качестве входного значения 1. В данном случае, если на входе будет 1, то на выходе получится 6. Как я и сказал, правило очень простое: мы берём входной индекс, умножаем его на 5 и прибавляем 1. Вот и всё! А, ну и ещё выполняется деление с остатком на 8192. Это просто означает, что если результат больше 8192, то мы делим его на 8192, а затем берём остаток.

Например, восьмой индекс RNG равен 7544. Если умножить его на 5 и прибавить 1, то получится 37721. При делении на 8192 мы получим 4 и остаток 4953. То есть девятый индекс RNG равен 4953.

Эта функция вполне неплохо справляется с генерацией случайных чисел. Иногда паттерн достаточно очевиден (особенно в начале с 0, 1, 6, 31), но чаще всего он приемлем. Однако важно распределение чисел. Одинакова ли вероятность генерации всех чисел? Оказывается, что да.

По крайней мере, для чисел меньше 8192, разумеется. До повторения эта функция обходит все 8192 числа от 0 до 8191. Последнее число в паттерне — 4915. Это хорошее свойство функции RNG, потому что оно означает отсутствие перекоса в сторону каких-либо результатов, по крайней мере, при отдельном произвольном доступе. (Если потребуется генерировать множество случайных чисел одновременно, могут возникнуть сильные корреляции, но по многим причинам это не станет для нас проблемой.)  

Однако обратите внимание, что я называю эти результаты индексами RNG, а не самими выводами функции RNG. Причина этого в том, что индекс — это не окончательный вывод функции, а просто вспомогательное значение, используемое для создания вывода. Этот индекс применяется в качестве смещения в коде игры для получения одного байта. Он-то и является выводом. И это не индекс какой-то таблицы: в качестве вывода RNG используются первые 8192 байта ассемблерного кода Pac-Man.

Основная часть этих байтов — машинный код, обозначающий ассемблерные команды, которые составляют различные функции кода игры; ничто из этого не связано со случайными числами. Представьте аналогию: допустим, вам нужно выбрать случайное слово на английском. Это будет похоже на использование той же функции для получения индекса, но затем мы используем этот индекс для поиска слова в любимой книге. Если входной индекс был равен 6189, то после вычислений выходной окажется равным 6370, поэтому вы будете искать 6370-е слово в книге.

Хоть этот способ поиска байта и позволяет избавиться от корреляции между идущими последовательно случайными числами, он влияет на равномерность вывода. Представьте, насколько высока вероятность случайно выбрать из книги слово «the»! Ниже показан график распределения 256 байт в первых 8 килобайтах кода игры.

Как видите, оно крайне неравномерно. При равномерном распределении каждое число должно было встретиться по 32 раза. Однако ноль встречается больше 600 раз: в коде есть пустые места, которые заполняются одними нулями. Число 77 тоже часто встречается, даже чаще, чем ноль. Это вызвано тем, что оно соответствует байту $4D, а в области памяти с $4D00 по $4DFF хранится большинство основных переменных игры. Поэтому в каждой команде чтения или записи этих переменных будет присутствовать байт $4D.

Некоторые числа вообще не встречаются в первых 8 килобайтах, например, 65, 141, 146 и 186. Может показаться, что это плохо, но, к счастью, есть одна тонкость, практически полностью спасающая ситуацию. Функция RNG используется лишь для определения того, куда на перекрёстке будет двигаться испуганный призрак. Допустимых вариантов всего четыре: вверх, вниз, влево или вправо. Их можно описать всего двумя битами. 00 обозначает вправо 01 — вниз, 10 — влево, а 11 — вверх. Поэтому в выводе функции RNG важны только два младших бита! Ну, вроде это намного лучше, ведь так? По крайней мере, по сравнению с предыдущим распределением любое другое будет выглядеть лучше. Чтобы распределение было равномерным, каждый из четырёх вариантов должен встречаться 2048 раз из 8192.

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

Биты 11, соответствующие движению вверх, встречаются всего 1338 раз, то есть в 16,3% случаев.  

Это один из двух недостатков алгоритма движения испуганных призраков — управляющая их поведением функция RNG неравномерна. У неё есть сильный перекос в движение влево и вниз, а вероятность двигаться вверх гораздо ниже. Можно предположить, что из-за этого призраки будут предпочитать левый нижний угол лабиринта, но давайте не будем торопиться...

На всякий случай приведу саму функцию RNG. В ней всего 13 ассемблерных команд, то есть она очень проста. В первой строке в CPU загружается старый индекс. В строках 2–4 индекс умножается на 5. В пятой строке к нему прибавляется единица. Строки 6–8 — это деление с остатком на 8192, выполняемое логическим AND старших 8 битов индекса с $1F; по сути, это урезание индекса до 13 бит. Этот индекс используется для получения байта из ROM, а затем новый индекс сохраняется в памяти, переписывая старый. К сожалению, эта функция находится в коде игры по адресу $2A23, вне пределов досягаемости индекса RNG, ограниченного значением $1FFF. Из-за этого байты, составляющие функцию RNG, не могут быть сами выводом функции RNG.  

Итак, испуганные призраки используют вывод RNG, чтобы решить, в каком направлении им двигаться. Но что, если они физически не могут двигаться в этом направлении?

Допустим, призрак находится на этом перекрёстке, но RNG приказывает ему двигаться вверх. Наверху стена, так что же произойдёт дальше? Вместо того, чтобы генерировать ещё одно случайное число, призрак просто попробует следующее направление по часовой стрелке. В данном случае призрак попробует двигаться вправо. Но призраки также не могут поворачивать на 180 градусов! Если этот призрак пришёл к перекрёстку справа, то не может выбрать двигаться вправо, поэтому он пробует следующее направление, то есть вниз, а это допустимое направление.  

В результате получается перекос в принятии решений: если призрак выбрасывает значение RNG, соответствующее движению вверх, вправо или вниз, то все они соответствуют перемещению вниз. Единственный способ двинуться влево на этом перекрёстке при движении справа — сразу выбрать «влево». Согласно показанному выше графику, вероятность этого 29,9%. То есть вероятность перемещения вниз составляет аж 70,1%.

И это второй изъян в поведении испуганных призраков — распределение случайных чисел по направлениям тоже неравномерно. Можно использовать эту информацию для создания таблицы вероятностей каждого типа перекрёстка. Так как у самого RNG тоже есть перекос, ни одна из этих ситуаций не симметрична. Здесь стоит упомянуть кое о чём ещё: испуганные призраки вызывают RNG не только на тайлах перекрёстков. Они вызывают функцию каждый раз, когда перемещаются с одного тайла на другой, даже находясь внутри туннелей. Так как призраки с двух сторон зажаты стенами и при этом не могут поворачивать на 180 градусов, в туннеле они могут двигаться только в одном допустимом направлении. И это надо учитывать, ведь при вызове функции RNG даже в этих тривиальных случаях она меняет значение индекса RNG. Это может помочь с перетасовкой индекса, чтобы не появлялись заметные паттерны (допустим, позволяющие предсказать по текущему направлению призраков их следующее направление).

А теперь давайте вернёмся к туннелям. Существует шесть типов тайлов туннелей: два прямых туннеля и четыре угловых. В каждый из этих тайлов призрак может войти с двух направлений, то есть получается 12 вероятностей. Эти 12 случаев можно сгруппировать в четыре группы: в первой единственный допустимый вариант — это движение вправо, то же самое для трёх остальных направлений.

Разумеется, даже несмотря на то, что распределение случайных чисел приводит к такому распределению направлений, единственное допустимое направление — это прямо вперёд, и призрак имеет вероятность 100% продолжить движение в том же направлении.

Всё становится любопытнее в случае трёхсторонних перекрёстков. Ниже показаны четыре их типа. Призрак может прийти с одной из трёх сторон, что даёт нам ещё 12 разных случаев. Их тоже можно разбить на группы, соответствующие тому, какие из двух направлений допустимы. Есть шесть таких групп, ниже показаны вероятности поворота призраков в каждом из направлений.

Две группы, разделённые между двумя противоположными направлениями — это не так уж плохо, потому что каждое направление вбирает в себя вес одного из соседних направлений. Самый честный случай — это когда призрак должен выбирать между движением вверх или вниз — случайный выбор направления между влево или вправо приводит к вероятности 46,3% пойти вверх, а случайный выбор направления между вправо или влево даёт вероятность 53,7% пойти вниз. Однако остальные четыре группы выбора двух соседних направлений невероятно перекошены. Почти во всех них вероятность выбора одного направления в три раза больше. 

Наихудшая ситуация возникает при выборе между влево и вправо — испуганный призрак имеет шансы пойти вверх всего 16,3%!

Наконец, у нас есть четырёхсторонний перекрёсток, на который призрак может прийти со всех четырёх сторон. Выше показано, как выглядят их распределения. Во всех четырёх случаях вдвое больше вероятность того, что призрак повернёт в ближайшем по часовой стрелке направлении. Так происходит, потому что единственное недопустимое направление — это назад; если оно выбрано, то, как мы говорили выше, следующим призрак выберет направление на 90 градусов по часовой стрелке, то есть влево от себя.

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

На мой взгляд, лучше всего анализировать эту проблему будет при помощи цепи Маркова. На случай, если вы не знаете, что такое цепь Маркова, я вкратце её опишу. Допустим, у нас есть некий процесс, который может существовать в одном из множества состояний. Мы можем представить эти состояния в виде вершин графа. Пусть у нас будет три уникальных состояния: A, B и C. На каждом шаге времени этого процесса текущее состояние может меняться. Вероятность перехода в другое состояние определяется исключительно текущим состоянием. Допустим, если мы находимся в состоянии A, у нас есть вероятность 50/50 перейти в состояние B или в состояние C. Можно представить эти переходы между состояниями в виде взвешенных направленных рёбер этого графа. Аналогично, если мы находимся в состоянии B, пусть у нас есть вероятность 30% перейти в состояние C, 60% перейти в состояние A и 10% остаться в состоянии B. Мы представим это в виде ребра из B в B. Так можно продолжать и дальше. Это цепь Маркова.

Мы можем симулировать пример этого процесса, допустим, начав из состояния A, а затем перемещаясь из состояния в состояние на основании указанных на рёбрах вероятностей. Если проделать так миллион раз, а затем подсчитать, сколько раз мы посетили каждое состояние, то так мы найдём среднее время, проведённое в каждом состоянии. Однако при достаточно большом графе для схождения к осмысленному значению понадобится экспоненциально долгое время, поэтому есть способ получше.

Можно начать с «массы» 100 в состоянии A, а затем разделять массу пропорционально исходящим рёбрам каждой вершины. В данном случае 100 разделяется напополам для B и C. При этом состояние A остаётся пустым (с нулём), потому что ранее B и C были пустыми. Затем на следующем шаге состояние A имеет массу 0, поэтому ничего не отдаёт. Состояние B отдаёт 60% от своих 50 состоянию A, 30% состоянию C и оставляет 10% себе, а состояние C даёт 30% состоянию A, 50% состоянию B и оставляет 20% себе. На этом шаге состояние A имеет массу 45, состояние B — 30, а состояние C — 25. Если пошагово выполнять такие действия, то достаточно быстро числа сойдутся к стабильному состоянию (если цепь обладает свойством «эргодичности»; в контексте нашей статьи это неважно, но можете изучить его, если любопытно).

Однако забавно то, что если цепь Маркова эргодична, то это стабильное состояние цепи вне зависимости от того, какими были исходные состояния. Мы начали с массы 100 в состоянии A, но могли бы начать с массы 100 в состоянии B или C, и пришли бы к тому же стабильному состоянию.

Мы можем построить цепь Маркова, описывающую каждый перекрёсток лабиринта Pac-Man в виде вершины графа, а рёбрами станут пути между ними. Весами рёбер будут показанные выше перекошенные вероятности. Тогда мы можем бросить массу 100 испуганных призраков в любую точку графа и итеративно обходить его, пока не достигнем стабильного состояния. В конечном итоге мы получим тепловую карту того, где предпочитают тусоваться в лабиринте испуганные призраки. Давайте сделаем это! В этом не должно быть ничего особо сложного. Так как туннели между перекрёстками в какой-то степени излишни, пока мы не будем их рассматривать. Когда мы поймём, что происходит, и убедимся, что всё работает правильно, то вернём их обратно. Для начала можно создать по одной вершине графа на каждый перекрёсток лабиринта. Нам нужно будет по два ребра на каждый путь между ними, по одному в каждом направлении.

Теперь нам вроде бы достаточно просто присвоить рёбрам веса согласно вероятностям направлений RNG? Не будем торопиться. Давайте взглянем на отдельный перекрёсток. Из этой вершины исходят три ребра, обозначающие три направления, в которых призрак может двигаться с этого перекрёстка. Однако мы знаем, что призрак не может разворачиваться на 180 градусов. Когда призрак приходит на трёхсторонний перекрёсток, то на самом деле у него есть два варианта, а не три. Причина этого в том, что мы не полностью передали состояние призрака нашими вершинами. Они не только должны описывать позицию призраков в лабиринте, но и кодировать, в каком направлении они движутся. Это значит, что каждому перекрёстку в лабиринте должно соответствовать несколько вершин, по одной на каждое направление, с которого призрак может выйти на перекрёсток. У трёхсторонних перекрёстков будет три вершины, а у четырёхсторонних — четыре. Чтобы было понятнее, я добавлю в них маленькие стрелки.

Теперь нам нужно правильно присоединить рёбра. Если призрак приближается к этому перекрёстку справа, это описывается вершиной со стрелкой влево, и так далее.

Теперь займёмся исходящими рёбрами. Если призрак движется вверх, то может пойти или влево, или вправо. Слева он может продолжить двигаться вправо или пойти вниз. А справа он может пойти вниз или влево.

Далее можно добавить веса рёбер с ранее вычисленными процентами. Призрак, попадающий на перекрёсток справа, может пойти влево с вероятностью 30% и вниз с вероятностью 70%. И так далее, принцип понятен.

Также видно, что разделение перекрёстков на несколько вершин позволяет другим направлениям прибытия на него влиять на вероятности направлений. Здесь призрак имеет вероятность 70% спуститься вниз, если он идёт справа, но если он вошёл слева, то вероятность равна только 29%. Нам просто нужно разбить подобным образом каждый перекрёсток. Это чуть сложнее из-за ограничения, не позволяющего призракам двигаться назад.

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

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

Ну а теперь мы, наконец, можем симулировать поведение испуганных призраков в этой огромной цепи Маркова. Я упрощу внешний вид этого графа. Поскольку в конечном итоге нас интересует, где призраки находятся в лабиринте, то нам не нужно знать, в каком направлении они двигаются; поэтому я возьму все вершины, соответствующие каждому тайлу, и сгруппирую их в мета-вершины. Масса этих мета-вершин будет равна суммарной массе вершин внутри них, она соответствует количеству призраков в этом тайле на данный момент вне зависимости от их направления. И я не буду больше показывать рёбра графа, потому что вполне понятно, что соседние вершины в лабиринте соединяются друг с другом.

Теперь вместо того, чтобы запихивать 100 призраков в один тайл, я размещу 50 призраков на два тайла рядом с их домом. На каждом тайле 25 призраков будут смотреть влево, а 25 — вправо.

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

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

Но какова же первопричина этого перекоса в левый нижний угол? Напомню, что в поведении призраков есть два изъяна. При помощи цепи Маркова мы можем экспериментировать с вероятностями, разделять и изолировать эти два отдельных свойства, чтобы посмотреть, как они влияют.

Во-первых, давайте начнём с решения обеих проблем. Ниже я настроил вероятности выбора направления так, чтобы на трёхсторонних перекрёстках она была идеальными 50/50, а на четырёхсторонних перекрёстках — идеальными 1/3. При симуляции этого лабиринта мы видим, что распределение призраков достаточно равномерное. Как я и говорил выше, призраки с большей вероятностью будут находиться на перекрёстке просто потому, что есть больше способов добраться к этому тайлу. Также это демонстрирует, что виновником определённо является один из этих изъянов.

Давайте для начала исправим функцию RNG. Я поменяю вероятность выбрасывания призраком одного из четырёх направлений на равные 25%. Призрак всё равно будет поворачивать этот вариант на 90 градусов, если выберет движение назад или в стену, то есть на некоторых перекрёстках разделение всё равно будет 75 к 25. Похоже, призраки всё равно предпочитают нижний левый угол, но теперь не так сильно.

И это вполне логично. Да, способ поворота выбираемого направления сильно перекошен на поворот влево, но здесь есть вращательная симметрия. Каждое перекошенное правило движения — часть четырёх правил, различающихся друг от друга на 90 градусов, и все они должны постепенно компенсировать друг друга.

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

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

Ага, мы нашли виновника! На самом деле, распределение оказывается ещё более перекошенным, чем в исходной версии. Механика поворота позволяет нам «освободиться» от перекоса функции RNG.

Например, так как на этом перекрёстке призрак, пришедший слева, не может вернуться налево, то при выбрасывании «влево» с обычными правилами он будет двигаться вверх. Хоть направление вверх само по себе имеет наименьшую вероятность, невозможность пойти влево, по сути, утраивает вероятность поворота вверх. Без такой помощи вероятность пойти вверх у призрака равна всего лишь 23%, а не 46%. Из-за этого крайне маловероятно, что в подобных обстоятельствах призрак будет находиться в верхней части лабиринта какое-то существенное время.

Наконец, нам нужно проверить, всё ли мы сделали правильно. Да, цепи Маркова — замечательный инструмент, но действительно ли они подходят для описания поведения испуганных призраков? Есть только один способ это выяснить. Давайте не будем симулировать всё в песочнице, а запустим саму игру!

Это очень легко протестировать минимальным вмешательством в игру. Достаточно сделать так, чтобы призраки всегда были испуганными, и поместить Pac-Man вне границ лабиринта, чтобы он не смог никого из них съесть. Потом мы просто оставим призраков заниматься своими делами и будем сэмплировать их позиции раз в несколько минут. Я максимально ускорил игру и оставил её на несколько часов. Записав тысячи примеров данных местонахождения призраков, можно создать из них тепловую карту.

Вот, какими оказались мои результаты:

И да, они на удивление похожи на теоретические! В конце концов оказалось, что наши расчёты всё-таки пригодились.

Но так ли это? Мы можем использовать этот перекос только в том случае, если призраки будут оставаться испуганными намного дольше, чем это бывает в игре. На самом деле, основной фактор, определяющий местоположение испуганного призрака в лабиринте — это его расположение в момент, когда Pac-Man съедает энерджайзер. Думаю, самое полезное правило здесь в том, что испуганные призраки предпочитают поворачивать влево относительно себя. Единственные исключения из этого правила: моменты, когда они движутся вправо в стену, то предпочтут повернуть вправо, чтобы двигаться вниз, и когда они движутся вниз в стену, то с небольшим перекосом предпочтут повернуть направо, чтобы пойти влево.

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