Детерминизм позволяет восьми машинам повторить один игровой мир: Age of Empires передавала команды вместо состояния тысяч объектов. Одинакового сида недостаточно – важны порядок вычислений и полный снимок симуляции. Основатель «Школы траблшутеров» Олег Брагинский и ученик Антон Бессарабов разбирают локстеп, откат и проверку повторов.

Рис. 1. Команды и начальные условия возвращают тот же мир
Полторы тысячи лучников и 28,8 кбит в секунду
Пол Беттнер и Марк Террано изложили схему на GDC 2001 в докладе 1500 Archers on a 28.8. Целевой машиной был Pentium 90 с 16 МБ памяти и модемом 28,8 кбит/с, целевой частотой – стабильные 15 кадров в секунду.

Рис. 2. У команды меньше сетевой багаж
Расчёт отверг метод пересылки состояния. Передача координат, статуса, действия, разворота и урона по каждому юниту упёрлась бы в потолок около 250 подвижных единиц – вшестеро меньше заявленных полутора тысяч.
Восемь игроков укладываются в небольшой поток команд: в среднем одна за 1,5–2 секунды на человека, в бою – три-четыре. На рис. 2 приведена расчётная модель: 64 бита на команду против передачи состояния 1’500 юнитов по 20 байт десять раз в секунду.
Схему называют детерминированным локстепом: машины обмениваются вводом, а мир каждая считает сама. Команды хода N исполняются на ходу N+2 – запас, за который сообщение успевает дойти и получить подтверждение.
Длина хода подстраивалась под сеть. В сообщении Turn Done клиент передавал устойчивую частоту кадров и худший средний пинг; управление скоростью занимало два байта. При скачке задержки хост быстро удлинял ход, а затем медленно сокращал обратно.
Детерминизм как условие
Генератор случайных чисел синхронизировали и задавали общее стартовое значение – сид. Каждая машина обязана обратиться к генератору одинаковое число раз в одном порядке: иначе даже при совпадающем начале последовательности разойдутся.
Несимуляционная случайность вынесена наружу. Звуки местности и прочий антураж брали числа отдельно, а генератор симуляции сохраняли и пересевали от последнего значения, чтобы оформление не сдвигало расчёт.
Показателен разбор реального рассинхрона. Олень, оказавшийся при генерации карты на доли единицы не там, позже уводил сбор пищи и охоту по разным ветвям – и расхождение, начавшееся в геометрии, проявлялось в экономике через минуты.

Рис. 3. Незаметное расхождение получает время на рост
Проблема плавающей точки
IEEE 754 задаёт форматы чисел и правила округления основных арифметических операций. Совмещённое умножение-сложение вошло в редакцию 2008 года, а не в стандарт 1985-го. Совпадение результатов всей программы на разных машинах стандарт сам по себе не гарантирует.
Сложение чисел с плавающей точкой неассоциативно: в двоичной арифметике binary64 выражение (0,1 + 0,2) + 0,3 даёт 0,6000000000000001, а 0,1 + (0,2 + 0,3) – 0,6. Разница в 1,11·10⁻¹⁶ занимает один младший разряд; разрешённая оптимизация может изменить порядок операций.
Источников расхождения несколько. Регистры x87 поддерживают расширенную 80-битную точность, а выгрузка в память может добавить округление. Совмещённое умножение-сложение (FMA) округляет один раз вместо двух; флаг -ffast-math разрешает переассоциацию.
Трансцендентные функции требуют отдельной проверки. Редакция IEEE 754-2008 относит синус, экспоненту и степень к рекомендуемым операциям раздела 9.2. Реализации библиотек могут различаться последними битами, поэтому названия формата и функции недостаточно для воспроизводимости.
Расхождение может усиливаться. В учебной модели начальная разница 2⁻⁵² при удвоении за шаг достигает единицы через 52 шага, при росте на 1% – через 3’623 шага, примерно за минуту при частоте 60 Гц. Темп зависит от модели: симуляция не обязана усиливать каждую ошибку.
Фиксированная точка на целых числах, согласованная математическая библиотека, запрет небезопасных оптимизаций и фиксация версии компилятора помогают обеспечить детерминизм. Выбранный набор мер проверяют на всех поддерживаемых платформах.
Контрольная сумма и запоздалый сигнал
Расхождение ловят контрольными суммами. Age of Empires сверяла мир, объекты, поиск пути и выбор цели; клиента с разошедшейся суммой помечали вышедшим из синхронизации и останавливали игру.

Рис. 4. Место остановки ещё не выдаёт виновника
Сигнал приходит позже причины, что усложняет отладку. Учебная схема показывает расхождение на ходу 83 и обнаружение на ходу 93. Искать дефект нужно в более ранних вычислениях: остановка указывает на момент проверки, а не обязательно на момент ошибки.
Разрядность суммы влияет на риск пропуска. При 10’000 независимых сравнениях случайных разных состояний 16-битная равномерная сумма хотя бы раз совпадёт с вероятностью около 14%. Для 32 бит риск близок к 0,00023%, для 64 – к 5,4·10⁻¹⁴%; увеличение разрядности не даёт абсолютной гарантии.
Инструменты собирали прямо в симуляцию. Разработчики снимали трассы сообщений до 50 МБ и дампы объектов мира, а в следующем движке завели макросы синхронизации по тегам подсистем, вырезаемые из релизной сборки.
Первая оговорка касается охвата. Разные контрольные суммы подтверждают расхождение; одинаковые не доказывают полного совпадения. Проверка охватывает только включённое состояние и допускает коллизии.
Вторая оговорка касается виновника. Проверка останавливает симуляцию при несовпадении сумм, но причина может находиться в коде, выполненном раньше и в другой подсистеме.

Рис. 5. Стратегия заставляет машины договориться о мире
Откат: детерминизм как условие отзывчивости
Файтинги пришли к той же математике с другой стороны. Задержанный ввод прячет пинг ожиданием и портит ощущение. Откат показывает предсказание сразу и при расхождении пересчитывает прошедшие кадры заново.
Тони Кэннон начал работу над GGPO после неудачного сетевого опыта в Street Fighter II: Hyper Fighting. Ранний прототип появился в 2006 году; официальный сайт датирует создание GGPO SDK 2009-м. В октябре 2019 года библиотеку открыли под лицензией MIT; среди известных применений – Skullgirls.
При 60 кадрах в секунду односторонняя задержка 50 мс соответствует трём кадрам ожидания удалённого ввода, 100 мс – шести, 166 мс – примерно десяти. Пинг обычно измеряет путь туда и обратно. Семь снимков по 256 КиБ занимают 1,75 МиБ; глубина отката зависит и от задержки ввода.
Пересчёт обязан повторять исходный результат. Для детерминированного отката сохраняют полное состояние и порядок действий; фиксированная точка – один из способов обеспечить воспроизводимую арифметику, а не обязательное условие для любого движка.

Рис. 6. В файтинге задержку чувствуют пальцы
Третья оговорка касается терминологии. Откат – сетевой приём, GGPO – конкретная библиотека. Наличие rollback в описании игры само по себе не подтверждает использование этого SDK: реализацию и происхождение кода нужно проверять отдельно.
Повтор как предиктор
Детерминизм приносит пользу и за пределами сетевого обмена. Первая выгода – размер повтора: начальное состояние, версия симуляции, сид и список команд могут занимать килобайты вместо гигабайтов видео. Для точного воспроизведения сохраняют все необходимые исходные условия.
Вторая выгода – «оракул» теста, проверка ожидаемого результата. Сохранённую партию запускают на новой сборке: несовпадение контрольных сумм указывает на изменение поведения. Разработчик определяет, запланировано ли отличие или вызвано дефектом.
Третье – воспроизведение дефекта и ради него приём ушёл за пределы игр. Команда FoundationDB начала работу в 2009 году с того, что написала детерминированную симуляцию раньше самой базы данных.
Главный риск остался прежним. Неучтённый вызов системных часов или генератора случайных чисел нарушает воспроизводимость. Запись команд помогает повторить дефект только при сохранении необходимых условий симуляции.
Детерминированная симуляция стала методом тестирования. Antithesis, основанная выходцами из FoundationDB, вышла из закрытой разработки в феврале 2024 года с детерминированным гипервизором, повторяющим исполнение инструкция за инструкцией.
Воспроизводимый прогон помогает исследовать ошибку, но не выбирает сценарии испытаний.
Остаётся решить, какие сочетания отказов проверить и как распределить бюджет запусков. Сходная задача возникает при оценке игрового баланса методом Монте-Карло.
Что запомнить?
- В учебной модели поток команд составляет около 0,29 кбит/с против 2’400 кбит/с для состояния юнитов.
- В модели с удвоением ошибки один младший разряд binary64 становится единичным расхождением за 52 шага.
- Детерминизм требует одинакового числа обращений к генератору в одинаковом порядке.
- Между причиной рассинхрона и сигналом проверки может пройти несколько ходов.
- Откат невозможен без детерминизма: пересчёт обязан повторить исходный проход.
Заключение
Практический порядок работы:
- выписать источники недетерминированности: часы, потоки, сеть, диск и неучтённую случайность
- засеять генератор симуляции и отделить его от генератора оформления
- включить в контрольную сумму состояние, а не только то, что удобно считать
- хранить исходные условия и команды повторов, проверяя на каждой сборке поведение симуляции
- зафиксировать версию компилятора и запретить переассоциацию, если симуляция считает вещественными числами.
Поставьте воспроизводимость в требования до первой строки симуляции: позднее внедрение затронет архитектуру и тесты. Сид задаёт начало случайной последовательности. Детерминизм позволяет при одинаковых условиях получить ту же партию второй раз.
Источники и расчётные модели
Сетевая архитектура описана в докладе Беттнера и Террано, требования к откату – в документации GGPO. Сравнения трафика, усиления ошибки и вероятностей коллизий в статье служат учебными моделями; начальные условия и допущения указаны рядом с расчётами.
Беттнер П., Террано М. 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond. GDC, 2001.
NVIDIA. Floating Point and IEEE 754. Разделы о порядке операций и FMA.
Кэннон Т. GGPO Rollback Networking SDK. Описание алгоритма и требования к движку.
Пшеничкин А. So you think you want to write a deterministic hypervisor? Antithesis, 2024.