Конспект раздела: финальный проект «Архипелаг»

Одна мысль на весь раздел

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

Карта игры: механика - задача - раздел

МЕХАНИКА                     ЗАДАЧА                          РАЗДЕЛ
пещеры и острова связаны     случайный остов, union-find     9, 11
стратегический мост          мосты и точки сочленения        10
отряд идёт к цели            Дейкстра / A*, h согласованная   11
многие к одной цели          поле расстояний от цели         10, 11
что видит отряд              прямая Брезенхема               19, 23
сырьё по рецептам            запоминание по графу без циклов 10, 15
трюм                         рюкзак 0/1 / дробный            14, 15, 22
выгодный круг обмена         отрицательный цикл после -log   11
место в рейтинге             Фенвик по оси очков             8, 19
подбор соперников            сортировка / паросочетание      12, 14
фильтр чата                  Ахо-Корасик                   17
сохранения                   хеш Зобриста                    7, 19
ИИ соперника                 минимакс, альфа-бета, таблица   15, 16
очередь событий              двоичная куча                   9
честный кубик                выборка с отказом               20
моды                         неразрешимость - предел шагов   21

Дерево решений для любой механики

механика из диздока
├── что значит «умно / лучше»?          -> спросить, записать критерий
├── сколько стоит при наибольшем размере
│   ├── не влезает в долю бюджета      -> другая модель:
│   │                                    общий расчёт, предподготовка
│   └── влезает                        -> структура под частые операции
├── какая гарантия игроку
│   ├── область конечна                -> перебор = доказательство
│   ├── свойство из устройства         -> доказать один раз
│   ├── ответ проверяется быстро       -> сертификат на каждый ответ
│   ├── ничего из этого                -> стресс-тест с границами
│   └── неразрешимо / NP-трудно        -> предел или приближение
└── собрано с другими модулями
    ├── инвариант мира после хода
    ├── правило конфликтов без порядка, до устойчивости
    └── профиль и тест удвоения

Как главы связаны

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

Числа раздела

бюджет хода: 100 мс × 1,5 · 10⁷ простых оп/с = 1,5 · 10⁶
             (запись в dict, sorted - дороже простой операции)
поле расстояний: 1838 проверок против 21 937 у сорока поисков
кубик b % 6: [43, 43, 43, 43, 42, 42]; с отказом - по 42
пещеры 6 × 10: сломано 59 стен = 60 - 1
A* с честной h: 258 клеток против 359 у Дейкстры, цена 46
рецепты «столица»: 228 вызовов наивно, 23 с запоминанием
рынок: честный круг 1.0, а сумма -log = -1,4 · 10⁻¹⁷
чат: 489 шагов автоматом против 15 178 наивно
хеш 64 бита: первое совпадение ~ 5 · 10⁹ позиций
ИИ: 18 камней - 11 204 узла против 242 при хорошем порядке
упаковка ход · 1000 + номер: контрпример [[1, 1000]]
сетка на фиксированной карте растёт с p ≈ 2

Объясни своими словами

Почему «отряд ходит умно» - это три разные задачи, и кто выбирает между ними?
Почему двести поисков пути к одной крепости заменяются одним - и когда это перестаёт работать?
Чем доказательство честности кубика отличается от проверки миллионом бросков?
Почему «каждый остров к ближайшему» дешевле минимального остова и всё равно хуже?
Почему проверка рецептов на круги идёт ДО расчёта сырья, а не во время?
Почему сравнивать логарифмы курсов без допуска опасно, а с допуском - тоже?
Почему у правила конфликтов важна независимость от порядка заявок?
Почему стресс-тест на маленьких номерах не нашёл ошибку упаковки?
Почему сетка, которая «решила» обзор, через полгода снова тормозит?