Сборка мира: инварианты и правила конфликтов

Если ты формулируешь инварианты состояния и проверяешь их после каждого шага, а правила конфликтов делаешь независимыми от порядка, листай до «Теперь сам».

Как думаешь, что пойдёт не так

Все отряды шагают одновременно: каждый заявляет клетку, сервер собирает заявки и двигает всех разом. Модуль пути проверен, модуль заявок проверен. Что может сломаться, если ни один модуль не ошибается?

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

На что это похоже

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

Механизм: инвариант, правило, устойчивость

Инвариант мира - условие на всё состояние игры, верное после каждого хода: в клетке не больше одного отряда, у игрока не отрицательный склад, отряд стоит на суше. Это тот же инвариант, что в разделе 1, но не цикла, а целой системы, и проверяет его функция, которую сервер вызывает после хода - в отладке всегда, в бою выборочно. Проверка после каждого хода называет ХОД, на котором мир сломался (выборочная - только ход не позже этого), а не тот, на котором это заметил игрок, - как проверка инварианта кучи в разделе 26.

Конфликт заявок разбирает правило. Хорошее правило детерминировано: результат зависит от заявок, но не от порядка, в котором они пришли по сети. «Шагает отряд с меньшим номером» таким правилом является - номера не зависят от сети. «Кто первый заявил» - нет: на двух машинах игроков заявки могут прийти в разном порядке, и миры разойдутся.

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

Правило

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

Разбор: два отряда в одну клетку

Пять отрядов, две пары спорят за клетки 13 и 32. Сначала без правила, потом с правилом «меньший номер».

# Ход сервера: каждый отряд заявляет клетку, куда хочет шагнуть, - и все
# шагают одновременно. Инвариант мира: в клетке не больше одного отряда.
otryady = {1: 12, 2: 14, 3: 22, 4: 31, 5: 33}       # номер -> клетка
zayavki = {1: 13, 2: 13, 3: 23, 4: 32, 5: 32}       # номер -> куда хочет

def invariant(o):
    # проверка после хода: клетки всех отрядов различны
    zanyato = set()
    for n in o:
        if o[n] in zanyato:
            return "в клетке " + str(o[n]) + " два отряда"
        zanyato.add(o[n])
    return "в порядке"

def hod_naivno(o, z):
    # каждый шагает, куда заявил, - конфликт никто не разбирает
    novye = {}
    for n in o:
        novye[n] = z[n]
    return novye

def hod_s_pravilom(o, z):
    # правило: при споре за клетку шагает отряд с меньшим номером,
    # остальные стоят. Решение не зависит от порядка заявок
    pobeditel = {}
    for n in sorted(z.keys()):
        if z[n] not in pobeditel:
            pobeditel[z[n]] = n
    novye = {}
    for n in o:
        if pobeditel[z[n]] == n:
            novye[n] = z[n]
        else:
            novye[n] = o[n]
    return novye

a = hod_naivno(otryady, zayavki)
print("без правила:", a)
print("    инвариант:", invariant(a))
b = hod_s_pravilom(otryady, zayavki)
print("с правилом: ", b)
print("    инвариант:", invariant(b))

без правила: {1: 13, 2: 13, 3: 23, 4: 32, 5: 32}
    инвариант: в клетке 13 два отряда
с правилом:  {1: 13, 2: 14, 3: 23, 4: 32, 5: 33}
    инвариант: в порядке

Без правила инвариант нарушен на первом же ходу: отряды 1 и 2 в клетке 13, и проверка это назвала. С правилом отряды 1, 3 и 4 шагнули, 2 и 5 остались на местах, инвариант держится. Правило перебирает заявки в порядке номеров, поэтому от порядка их прихода не зависит. Граница правила: «меньший номер выигрывает» нечестно к игроку, у которого номера отрядов большие, - в игре такие правила часто делают зависимыми от номера хода ((номер + ход) mod n), чтобы преимущество чередовалось, но всё равно детерминированными.

Разбор: цепочка блокировок

Отряды 1 и 2 спорят за клетку 13. Отряд 3 заявил клетку 14, где стоит отряд 2, - рассчитывая, что тот уйдёт.

# Цепочка: отряды 1 и 2 спорят за клетку 13; проигравший 2 стоит в 14,
# а отряд 3 заявил именно 14 - он думал, что 2 оттуда уйдёт
otryady = {1: 12, 2: 14, 3: 15}
zayavki = {1: 13, 2: 13, 3: 14}

def invariant(o):
    zanyato = set()
    for n in o:
        if o[n] in zanyato:
            return "в клетке " + str(o[n]) + " два отряда"
        zanyato.add(o[n])
    return "в порядке"

def odin_raz(o, z):
    # правило из прошлого разбора: спор решает меньший номер
    pobeditel = {}
    for n in sorted(z.keys()):
        if z[n] not in pobeditel:
            pobeditel[z[n]] = n
    novye = {}
    for n in o:
        if pobeditel[z[n]] == n:
            novye[n] = z[n]
        else:
            novye[n] = o[n]
    return novye

def do_ustojchivosti(o, z):
    # повторяем: кто стоит, тот занимает свою клетку, и заявка в неё
    # тоже снимается. Каждый круг кого-то останавливает - кругов не
    # больше, чем отрядов
    stoit = set()
    krugov = 0
    while True:
        krugov = krugov + 1
        zanyato = {}
        for n in stoit:
            zanyato[o[n]] = n
        pobeditel = {}
        for n in sorted(z.keys()):
            if n not in stoit and z[n] not in zanyato:
                if z[n] not in pobeditel:
                    pobeditel[z[n]] = n
        novye_stoyat = set()
        for n in o:
            if n not in stoit and pobeditel.get(z[n], -1) != n:
                novye_stoyat.add(n)
        if len(novye_stoyat) == 0:
            break
        for n in novye_stoyat:
            stoit.add(n)
    rez = {}
    for n in o:
        if n in stoit:
            rez[n] = o[n]
        else:
            rez[n] = z[n]
    return [rez, krugov]

a = odin_raz(otryady, zayavki)
print("одно правило:     ", a, "|", invariant(a))
b = do_ustojchivosti(otryady, zayavki)
print("до устойчивости:  ", b[0], "|", invariant(b[0]), "| кругов", b[1])

одно правило:      {1: 13, 2: 14, 3: 14} | в клетке 14 два отряда
до устойчивости:   {1: 13, 2: 14, 3: 15} | в порядке | кругов 3

Одно применение правила разобрало спор за 13, но не заметило, что проигравший отряд 2 остался в 14 - куда шагнул отряд 3. Инвариант нарушен. Повтор до устойчивости сделал три круга: в первом остановился отряд 2, во втором - отряд 3, чья цель оказалась занята, в третьем никто новый не остановился. Граница правила: если отряды стоят по кругу и каждый заявил клетку следующего, правило пропускает всех - круг сдвигается целиком, клетки освобождаются одновременно. Хочет ли игра это разрешать - решение дизайнера, и его тоже записывают в спецификацию.

Что ломается без этого

Два отряда в клетке. Модули верны, а на стыке отряды сливаются; через десять ходов падает модуль боя, который не ждал двух отрядов в клетке, - и ищут ошибку в нём.

Повтор партии расходится. Конфликты разбирались «кто первый заявил»; повтор из журнала на другой машине дал другой исход, и спор о результате турнира не разрешить.

Правило в один проход. Прямые споры разобраны, цепочки - нет, и раз в несколько партий инвариант ломается в непредсказуемом месте.

Зачем это в работе

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

Теперь сам

1. Отряды 1, 2, 3 в клетках 10, 20, 30 заявили 20, 30, 10 - каждый клетку следующего. Что сделает правило до устойчивости?
2. Отряды 4 и 7 спорят за клетку 50, отряд 9 заявил клетку отряда 7. Кто где окажется?
3. Почему правило «кто первый заявил» ломает повтор партии из журнала?