Модуль 1 · Аркады и основы

Аркадный ИИ: автоматы и жадные призраки

Как четыре призрака с обзором в одну клетку и нулевым поиском пути создают «характер» — и почему аркадный ИИ это первый в истории случай «классика бьёт ML».

~16 мин

Суть за 20 секунд

Призраки Pac-Man не строят путь. Каждый на перекрёстке жадно выбирает соседнюю клетку, минимизирующую прямое расстояние до своей целевой клетки; ничьи решаются порядком «вверх → влево → вниз», разворот назад запрещён. Один тайл обзора, без памяти, O(1) — потому что на железе 1980-го больше нельзя. «Характер» берётся не из ума, а из того, куда каждый смотрит: Blinky целит в Pac-Man, Pinky — на 4 клетки впереди, Inky — через вектор от Blinky, Clyde трусит вблизи. Поверх — простой глобальный автомат Scatter ⇄ Chase ⇄ Frightened. Это жадный argmin, прямой предок «greedy decoding» в LLM — и контрапункт к A*/RL.

Механизм

Жадный выбор в одну клетку

У каждого призрака есть целевая клетка (target tile) — она пересчитывается каждый кадр по его личному правилу. На перекрёстке призрак смотрит на допустимые выходы (все, кроме разворота назад) и выбирает тот, чей центр ближе всего по прямой к цели. Сравнивают квадрат расстояния — корень не нужен:

d^{2} = {(x_{t} - x_{n})}^{2} + {(y_{t} - y_{n})}^{2}

n^{*} = \underset{n \in N}{\arg \min} d^{2}

где t — целевая клетка, n пробегает соседей N (без разворота). Ничья (одинаковый d²) ломается фиксированным приоритетом направлений — вверх, влево, вниз (но не вправо как тай-брейк и никогда назад). Это весь «интеллект»: ни очереди, ни закрытого множества, ни поиска — один argmin по 2–3 кандидатам.

Перекрёсток: 3 легальных выхода (назад запрещён), у каждого считаем d² до цели, идём в минимум. Вот и весь призрак.

Четыре цели — четыре «характера»

Алгоритм у всех один; различаются только правила вычисления целевой клетки — и из этого рождается ощущение разных личностей:

Blinky (красный) — цель = текущая клетка Pac-Man. Тупо в лоб, давит сзади.
Pinky (розовый) — цель = 4 клетки впереди Pac-Man по его направлению. Кажется, что подрезает и устраивает засаду.
Inky (голубой) — берёт точку 2 клетки впереди Pac-Man, проводит вектор от Blinky к этой точке и удваивает его. Цель зависит от позиции Blinky — поведение «непредсказуемое».
Clyde (оранжевый) — если до Pac-Man > 8 клеток, целит как Blinky; ближе 8 — убегает в свой угол (как в Scatter). Поэтому он то лезет, то трусливо отваливает.

Знаменитый баг закреплён в железе: когда Pac-Man смотрит вверх, из-за переполнения 8-битной арифметики Pinky целит не «на 4 вверх», а на 4 вверх И 4 влево; Inky наследует тот же сдвиг в своей точке «2 впереди». Namco баг не правил — он добавлял угол атаки, и так и осталось каноном.

Глобальный автомат: Scatter / Chase / Frightened

Поверх индивидуального таргетинга крутится общий конечный автомат на таймере:

Chase — цель по личному правилу (см. выше). Длится ~20 с.
Scatter — цель = фиксированный домашний угол призрака; все разбегаются, давая передышку. Первые фазы ~7 с.
Frightened — по съедении энергайзера: призраки разворачиваются, синеют, замедляются и на перекрёстках идут псевдослучайно (направление из PRNG). Таймер Scatter/Chase на это время паузится и возобновляется после.

Игра несколько раз чередует Scatter→Chase (7/20/7/20/5/20…), а дальше Chase почти навсегда. Каждая смена режима форсирует разворот призраков — это и анти-зацикливание, и честный «телеграф» игроку: видишь разворот — режим сменился.

Один маленький FSM на всех + личное правило цели у каждого. Смена режима = форсированный разворот.

Числовой пример. Blinky в клетке, цель = Pac-Man в (25,4). Три выхода: вверх (22,5), влево (21,6), вниз (22,7). Считаем d²: вверх (25−22)²+(4−5)² = 9+1 = 10; влево 16+4 = 20; вниз 9+9 = 18. Минимум — вверх (10). Будь вверх и вниз равны — выбрали бы вверх по тай-брейку. Один проход по трём кандидатам, ноль поиска.

🕹 В какие игры поиграть — и что заметить

От «ИИ в две строки» до четырёх призраков с эмерджентным характером. По каждому: как сделано и что спровоцировать, чтобы увидеть автомат руками. От реактивного слежения к жадному таргетингу.

Pong 1972 · реактивный автомат в 2 строки

ИИ-ракетка просто тянется по Y к мячу: if ball.y > paddle.y: move down else up. Ни предсказания, ни плана. Поэтому у неё есть честная дыра: подай мяч так, чтобы он пришёл к краю быстрее, чем ракетка доедет, — она физически не успеет. «ИИ», который весь умещается в одно сравнение.

🎮 Сыграй: в Pong бей резко по диагонали к дальнему краю — увидишь, что соперник не успевает. Это не «сложность», а потолок реактивного слежения без упреждения.

Space Invaders 1978 · детерминизм + псевдослучайность

Строй пришельцев движется по жёсткому детерминированному паттерну (влево-вправо-вниз), но выстрелы — из простого детерминированного ГПСЧ (псевдослучайность из сида). А ускорение по мере убыли врагов — изначально артефакт (меньше спрайтов → меньше работы за кадр → цикл быстрее), который оставили как фичу нагнетания.

🎮 Сыграй: заметь, как темп музыки и движение ускоряются, когда пришельцев мало. Это не дизайн «адаптивной сложности», а старый цикл, который буквально быстрее крутится с меньшей нагрузкой.

Pac-Man 1980 · 4 жадных таргетера + FSM

Вся теория выше — это он. Четыре одинаковых жадных автомата с разными правилами цели + глобальный Scatter/Chase/Frightened. Эмерджентный «характер» без единой строчки про личность: он целиком в выборе целевой клетки.

🎮 Сыграй: зажми призраков в угол — на перекрёстках они разойдутся в разные стороны (у каждого своя цель). Подразни Clyde: подойди вплотную — он отвалит (8 клеток), отойди — полезет. Развернись вверх и смотри, как Pinky/Inky промахиваются мимо тебя (баг переполнения).

Хардкор · дизайн: почему минимум правил даёт максимум «характера»можно пропустить

Pac-Man — хрестоматия эмерджентности: сложное поведение из простых правил. Разбор, почему это работает лучше «умного» ИИ:

Читаемость (legibility) важнее оптимальности

Идеальный преследователь (настоящий A* к игроку) был бы несправедлив и нечитаем: игрок не понимает логику и не может её обыграть. Жадный таргетинг с разными целями предсказуем настолько, чтобы его читать, и достаточно асимметричен, чтобы держать напряжение. Blinky давит сзади, Pinky подрезает спереди — вместе они «зажимают», хотя каждый туп.

Scatter — спроектированная передышка

Без фаз Scatter четыре преследователя слиплись бы в один смертельный комок. Периодический разбег по углам — это дизайнерский клапан давления: даёт окна для прохода и сбрасывает «слипание». Clyde-«трус» работает так же локально: создаёт безопасную зону у своего угла.

Детерминизм как глубина — и его цена

Полная детерминированность позволила экспертам учить паттерны (фиксированные маршруты на убийство уровня). Это и глубина мастерства, и проблема долговечности: выученный паттерн убивает реиграбельность. Поэтому Championship Edition и поздние ремейки добавили рандомизацию — осознанный размен «читаемость/мастерство» против «непредсказуемость/долговечность».

Хардкор · инженерия: цена в тактах и почему НЕ поиск путиможно пропустить

Бюджет. На 8080/Z80 ~2–3 МГц и десятках спрайтов поиск пути (BFS/A*) на каждого из 4 призраков каждый кадр — непозволительная роскошь. Жадный выбор — это 2–3 вычитания и сравнения на призрака на перекрёсток, O(1). Геймплейно его хватает, потому что лабиринт сам канализирует движение: коридоры не дают жадности застрять.
Распространённый миф (и в нашем исходнике тоже): «призраки ходят по BFS». Нет. Никакого построения пути — только локальный argmin по соседям. Это важно концептуально: «характер» возникает без поиска и без памяти.
Запрет разворота — не стиль, а защита от осцилляции: разрешишь разворот — призрак залипнет, дёргаясь туда-сюда у локального минимума. Разворот разрешён только как форсированный сигнал при смене режима.
8-битная экономика выходит боком. Тот же класс «дёшево, но переполняется», что дал баг Pinky, на уровне 256 даёт знаменитый kill screen: 8-битный счётчик уровня переполняется, и пол-экрана превращается в мусор. Цена предельно дешёвой арифметики.
Когда жадности мало. В открытом пространстве (не коридоры) жадный таргетинг застревает на вогнутых препятствиях — там и нужен настоящий A* (см. урок по pathfinding). Аркадному лабиринту он не нужен — топология делает работу за алгоритм.

Аналогия

Четыре охотника, каждый из которых умеет ровно одно: глянуть на свой ориентир и шагнуть в его сторону. Карты нет, плана нет, переговоров нет. Но ориентиры у них разные — один смотрит прямо на жертву, другой туда, где она будет, третий — на отражение через напарника. Сложив три тупых взгляда, они тебя зажимают. «Личность» — не в уме охотника, а в том, куда он приучен смотреть.

Почему это важно

Это первый и чистейший урок: богатое поведение не требует поиска или обучения — иногда хватает локального жадного правила, и оно даже лучше, потому что дёшево, детерминировано и читаемо игроком. Знание, где жадности достаточно, а где она проваливается (открытое пространство → A*, динамика без модели → RL), — это и есть инженерное суждение «не доставай дорогой инструмент, пока дешёвый принципиально вывозит». Аркадный ИИ — нулевая точка шкалы, на другом конце которой AlphaStar.

🔁 За пределами игр — куда это переносится

Урок даёт три переносимых приёма: жадный локальный выбор вместо глобального поиска, эмерджентность из простых правил и конечный автомат как каркас поведения.

ML / AI (твой домен): жадный argmin по соседям — это дословно greedy decoding (берём самый вероятный токен без поиска); beam search и MCTS (AlphaGo) — что начинается, когда жадности мало. «Призраки vs A*» = «greedy decode vs search». Реактивный таргетер без памяти — это policy без планирования (model-free), а Scatter/Chase/Frightened — ранний hierarchical/options RL: переключаемые субполитики. Детерминизм = воспроизводимый eval.

Системы: жадные эвристики везде — least-loaded балансировка, greedy-вытеснение кэша, nearest-server роутинг; конечные автоматы — workflow/протокол-движки, lifecycle ресурсов.

Робототехника / управление: реактивная архитектура (Брайтенберг, subsumption Брукса) против делиберативного планирования — тот же размен «дёшево и сейчас» против «дорого и оптимально».

Принцип: минимальные локальные правила могут давать богатое глобальное поведение. Начни с жадного/реактивного; усложняй до поиска или обучения только там, где локально доказуемо не выходит.

🔧 Запусти и поковыряй — на домашнем компе

Во что играть — выше (🕹). Здесь — увидеть таргетинг и FSM вживую:

🔧 Поковырять (debug) ~40 мин, эмулятор / Pac-Man Dossier

Возьми эмулятор Pac-Man с оверлеем целевых клеток (такие билды/моды показывают цветные маркеры target tile каждого призрака) или разбор на pacman-dossier. Понаблюдай, как маркер Pinky прыгает на 4 клетки вперёд, как Inky зависит от Blinky, и как при взгляде вверх маркер Pinky уезжает влево (баг). Засеки таймер: поймай моменты, когда все призраки разом разворачиваются — это смена Scatter↔Chase.

🧪 Потестить (глазами QA) ~15 мин

Проверяй автомат на стыках: forced-reverse точно на каждой смене режима? Clyde переключается ровно на 8 клетках (а не плавно)? Во Frightened направления реально псевдослучайны, и таймер Scatter/Chase паузится (после испуга режим возвращается тот же)? Это типовой чеклист «состояния и переходы FSM».

Чеклист: увидел разные target tile у 4 призраков; поймал баг «взгляд вверх» у Pinky; зафиксировал forced-reverse на смене режима.

Связи

основа

Игровой цикл — детерминированные фикс-тики делают поведение призраков повторяемым, отсюда выучиваемые паттерны прохождения.

контраст

Pathfinding: A* и NavMesh — жадный таргетинг это «pathfinding без пути»; A* — то, что нужно, когда лабиринт перестаёт канализировать движение.

дальше

FSM и Behavior Trees — Scatter/Chase/Frightened это учебный конечный автомат; BT — следующий шаг масштабирования поведения.

Вопросы пытливого ума

Постоянно слышу «призраки ходят по BFS/поиску пути». Это так?

Нет — и это частый миф (он есть даже в нашем исходном конспекте). Никакого построения пути: каждый призрак на перекрёстке делает жадный локальный выбор — argmin прямого расстояния до своей целевой клетки по 2–3 соседям, без очереди, закрытого множества и памяти. «Зажимающее» поведение — эмерджентное следствие разных целей, а не результат поиска. Понимать это принципиально: богатый результат получен без дорогого алгоритма.

Почему разворот запрещён, но смена режима его форсирует?

Запрет — анти-осцилляция: разреши разворот, и у локального минимума призрак задёргается назад-вперёд, зависнув. Поэтому в норме назад нельзя. Но при смене Scatter↔Chase цель скачком меняется, и единый форсированный разворот служит двум целям: мгновенно перенаправляет стаю под новую цель и телеграфирует игроку смену режима (видишь синхронный разворот — фаза сменилась). Исключение спроектировано как сигнал.

Баг Pinky (взгляд вверх → цель ещё и влево) — делает её хуже?

Скорее меняет, чем ломает. Из-за переполнения «4 вперёд» при взгляде вверх превращается в «4 вверх и 4 влево», поэтому засада Pinky смещается по диагонали. Namco баг не правил: он добавил неочевидных углов перехвата и не сломал игру. Классический случай, когда дефект железа стал частью «характера» — и почему вычищать каждую аномалию вслепую вредно.

Жадность работает в лабиринте — почему провалится в открытом поле?

В коридорах топология сама ведёт: выборов мало, тупик быстро отсекается, локальный минимум почти всегда совпадает с правильным ходом. В открытом пространстве с вогнутым препятствием жадность загоняет агента в «карман» (шаг к цели упирается в стену, обойти = временно увеличить расстояние, чего жадность не делает) → застревание. Там нужен поиск с учётом пройденной стоимости — A*. То есть достаточность жадности — свойство карты, не алгоритма.

Детерминизм даёт выучиваемые паттерны — это баг или фича?

И то и другое, это размен. Полная детерминированность дала экспертам паттерны — заученные маршруты, проходящие уровень «на автомате»: огромная глубина мастерства. Но она же убивает реиграбельность, когда паттерн выучен. Поэтому Championship Edition и ремейки впрыснули рандомизацию. Тот же выбор стоит перед любым ИИ-противником: предсказуемость (читаемость, мастерство) против вариативности (долговечность, честность).

Что почитать

Jamey Pittman, «The Pac-Man Dossier» — исчерпывающий разбор таргетинга, режимов и таймингов (первоисточник).
Don Hodges, «Pac-Man ghost behavior analyzed and fixed» — детальный разбор бага Pinky/Inky на ассемблере.
Ian Millington, «AI for Games» — реактивные автоматы и место жадных эвристик в общей карте game AI.
Модуль 1, «Key Algorithms: Ghost Targeting» + «Design Study» (01-foundations-1970-1985.md).

← назадКоллизии: AABB и тайловые дальше →Обзор · Модуль 1

Источник: модуль 1, «Key Algorithms to Understand: Pac-Man Ghost Targeting» + «Design Study» (01-foundations-1970-1985.md); факты сверены по Pac-Man Dossier.