Неразрешимость игры Braid

Игра Braid — изданный в 2008 году платформер-головоломка, основным элементом которого является способность главного героя поворачивать время вспять.

Игровые объекты

Тим (англ. Tim) — главный герой игры. Возвышение перед ним иллюстрирует максимальную высоту его прыжка. На возвышении находится часть паззла. Цель игры — заполучить ее.

Монстр (англ. monstar). Ходит по прямой линии, падает с возвышений, разворачивается, когда сталкивается с препятствием. Если Тим приземлится монстру на голову, то монстр погибнет, а Тим подскочит выше, чем при своем обычном прыжке. Лобовое столкновение с монстром для Тима смертельно.

Рычаг (англ. lever) и платформа (англ. platform). Подъем платформы контролируется нажатием рычага. Платформу можно установить таким образом, чтобы она поднималась при нажатии рычага и падала, столкнувшись с другим объектом.

Односторонние поверхности (англ. one-way surfaces) позволяют проходить сквозь них в одну сторону, но не пускают обратно. На иллюстрации Тим может запрыгнуть на поверхность (2), но не сможет спуститься вниз. Монстр пройдет из области (1) в область (2), но не пройдет назад.

Пушка (англ. cannon). С некоторой периодичностью пушка стреляет определенными игровыми объектами (монстрами, кроликами, огненными шарами или облаками).

Кролик (англ. bunny). Монстр убивает кролика, сталкиваясь с ним. Это может быть использовано, чтобы отделить одного монстра от группы монстров.

Тим и часть паззла

Монстр

Односторонние поверхности

Платформа с рычагом

Пушка

Кролик

Перемотка времени

Игрок может зажимать определенную клавишу, чтобы отматывать время назад, чтобы исправить соверешенную ошибку или даже отменить смерть персонажа. Обычно эта механика упрощает прохождение игроку, но никак не влияет на вычислимость игры. Однако, в Braid некоторые объекты существуют вне времени и на них не действует перемотка. Например, вневременной кролик продолжит прыгать вперед, даже когда весь мир возвращается назад во времени. На таких объектах основывается большинство уникальных головоломок в Braid. После отмотки времени назад Тим может промотать его снова вперед, аналогично командам undo и redo в различных редакторах. Как и с командами undo и redo, совершение каких-либо действий после отмотки времени назад не позволит промотать его вперед.

Неразрешимость

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

Теорема:

Проблема останова игры Braid неразрешима.

Доказательство:

[math]\triangleright[/math]

Если по Braid возможно построить машину Тьюринга, то проблема останова игры неразрешима. Следовательно, необходимо описать процесс построения МТ в игре Braid. Построим счетчиковую машину, эквивалентную МТ. Подаваемая на вход программа будет содержать следующие операции: Прибавить: увеличивает на 1 значение выбранного счетчика. Вычесть и перейти: сравнивает с нулем значение выбранного счетчика. Если оно больше нуля, из него вычитается единица; если равно нулю, происходит переход на указанную строку в программе. Остановиться. В нашей машине счетчиками будут являться группы монстров. Программа будет выполняться Тимом: чтобы пройти уровень, ему нужно нажать на каждый рычаг на своем пути. Каждый рычаг выполняет либо операцию добавить, либо вычесть и перейти. Чтобы допустить переходы (goto), некоторые участки пути могут вести к более ранним местам на этом пути. Для это нам понадобится соорудить из простых игровых объектов служащие нашим целям устройства (англ. gadgets). Устройства Устройство нажатия рычага Устройство нажатия рычага Заставляет Тима нажать на рычаг ровно единожды. Тим начинает в точке (1). Он может только упасть вниз к точке (2) и нажать на рычаг. Когда он нажмет на рычаг, платформа под ним поднимется вместе с ним к односторонней поверхности (3) с такой скоростью, чтобы Тим не смог нажать на рычаг еще раз. Поверхность (3) не даст Тиму спуститься вниз, и ему останется лишь пройти к выходу из устройства (4). Когда платформа достигнет поверхности (3), она вернется к своему начальному состоянию, что позволяет использовать устройство столько раз, сколько потребуется. В игре один рычаг может контролировать больше одной платформы, а платформы могут контролироваться более чем одним рычагом, поэтому такое устройство позволит управлять платформами в одной точке уровня из другой точки на этом уровне. Устройство-перекресток Устройство-перекресток Позволяет отправлять Тима или монстров вниз по маршрутам произвольной длины. Устройство-счетчик Устройство-счетчик Позволяет прибавлять или вычитать единицу. В точке (1) находится некоторое количество монстров [math]n[/math] — значение счетчика. Этим значением могут управлять устройства вычитания и прибавления единицы. Устройство прибавления единицы Пушка постоянно выстреливает новых монстров. Они отскакивают от платформы (2) и умирают на шипах. Устройство активируется, когда Тим нажимает рычаг, контролирующий платформу (2). Платформа ненадолго приподнимается, пропуская под собой одного монстра, и падает обратно. При каждой активации вышедший таким образом монстр проходит через одностороннюю поверхность (3) и оказывается заперт в участке (1), увеличивая таким образом счетчик на 1. Устройство вычитания единицы Пушка постоянно выстреливает новых кроликов. Как и в устройстве прибавления единицы, они отскакивают от платформы и умирают на шипах. При каждой активации платформа ненадолго сдвигается, пропуская одного кролика, который долетает до нижней границы (1) и касается ее. Если в участке (1) есть монстры, кролик погибнет от столкновения с одним из них, а тот при столкновении подскочит до верхней платформы и выйдет к участку (5). В противном случае кролик долетит до шипов (4) и погибнет там. Таким образом, при каждой активации, если значение счетчика не 0, один монстр убирается из счетчика и отправляется по определенному маршруту. Стоит заметить, что он не погибает, а идет по своему пути, что мы используем в устройстве ветвления. Устройство ветвления Устройство ветвления Отправляет Тима по одному из двух различных путей в зависимости от того, есть ли в устройстве монстр. Тим попадает в устройство в точке (1). Площадка и лестница (2) находятся слишком высоко, чтобы запрыгнуть на них, поэтому, если в устройстве монстра нет, Тим может только дойти до конца и выйти в точке (3). Если же монстр есть, Тим не может пройти к выходу (3), и ему остается только прыгнуть на монстра, тем самым убивая его и подскакивая выше, чем при обычном прыжке. Единственное место для этого — участок (2), и при прыжке на монстра Тим окажется на площадке без возможности спуститься вниз. Он может покинуть устройство только поднявшись по лестнице. Наличие или отсутствие монстра определяет, какой из выходов сможет использовать Тим. Конструкция машины Разместим три устройства-счетчика далеко друг от друга. Состоящий из устройств нажатия рычага и ветвления маршрут, который мы построим для Тима, и будет подаваемой на вход программой. Например, если мы хотим прибавить 1 к счетчику №2 в начале программы, то первая комната на пути будет устройством нажатия рычага, связанным с устройством прибавления единицы во втором устройстве-счетчике. Аналогично, рычаг может быть связан с устройством вычитания единицы в каком-либо счетчике. Тогда при активации, если значение счетчика не равно нулю, один монстр покинет счетчик. Чтобы выполнить переход при равенстве нулю, нам нужно отправить монстра в соответствующее устройство ветвления. Для этого все монстры, покидающие счетчик, будут попадать в соответствующую ему комнату, по которой они будут ходить. В полу этой комнаты будет множество платформ, работающих в качестве люков. Отправим Тима во второе устройство нажатия рычага, которое и откроет один из люков. Построенный нами путь под этим люком будет вести в устройство ветвления. Теперь Тим отправится в это устройство, но его маршрут сделаем значительно длиннее, чтобы он не мог опередить монстра, направляющегося туда же. В зависимости от того, был ли счетчик нулевым, Тим встретит или не встретит монстра в устройстве ветвления и пойдет по определенному пути. Операции прибавить и вычесть и перейти описаны. Операция остановиться проста: построим комнату с частью паззла и выходом с уровня. В эту комнату будет вести выход из очередного устройства, посещенного Тимом, при этом вполне возможно, что в данной конфигурации уровня в нее нельзя будет попасть, потому что Тим всегда будет выбирать другой выход в устройстве ветвления. Тогда уровень оказывается непроходимым. Таким образом, определение того, возможно ли пройти данный уровень, эквивалентно проблеме останова.

[math]\triangleleft[/math]

См.также

• Задача о выводе в полусистеме Туэ
• Задача о замощении
• Однозначность грамматики
• Неразрешимость задачи об эквивалентности КС-грамматик
• Игра «Жизнь»

Источники информации

• Linus Hamilton — Braid is undecidable