Что игре нужно доказать, а что - проверить или ограничить

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

Как думаешь, честный ли кубик

Генератор случайных чисел отдаёт байт от 0 до 255, все значения равновероятны. Грань кубика программист получает как b % 6 + 1. Честный ли кубик? Как это проверить - бросить миллион раз?

Ответь себе до чтения. Миллион бросков покажет частоты около 16,4% и 16,7%, и разницу в две десятые процента легко списать на случайность. Но область здесь конечна - 256 байтов, - и её можно перебрать целиком. Перебор конечной области - это не опыт, а доказательство: он отвечает точно. 256 не делится на 6, поэтому четыре грани получают на один байт больше двух других.

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

Сдача экзамена по билетам. Если билетов 30, а выучено 29, не нужно гадать, каковы шансы, - их можно пересчитать точно: 29 из 30. Гадать приходится, только когда билетов бесконечно много или их нельзя пересмотреть. Так же с гарантиями игры: где область обозрима, её пересчитывают; где нет - проверяют, где нельзя даже проверить - ставят предел.

Механизм: четыре способа закрыть обещание

Порядок выбора такой. Сначала спроси, конечна ли и обозрима ли область, - тогда переберите её. Потом - следует ли свойство из устройства: остов связен всегда, доказывать надо один раз. Потом - можно ли проверить готовый ответ быстрее, чем найти: тогда сертификат на каждый ответ. Если ни то, ни другое - стресс-тест против медленного эталона. А если сама задача неразрешима или NP-трудна, честное обещание - не «найдём», а «остановим» или «найдём не хуже».

Правило

Для каждой гарантии игроку назови способ: доказательство (область конечна или свойство следует из устройства), сертификат (ответ проверяется быстрее, чем ищется), стресс-тест (ни того, ни другого) или предел (задача неразрешима). Гарантия без способа - обещание, которое никто не выполняет.

Разбор: честный кубик полным перебором

Генератор отдаёт байт b от 0 до 255. Перебираем все 256 значений и считаем, сколько байтов дают каждую грань, - для двух способов.

# Генератор отдаёт байт 0..255, каждый с вероятностью 1/256. Нужна грань
# кубика 1..6. Проверяем не опытом, а полным перебором всех 256 байтов:
# на конечной области перебор и есть доказательство.

def kak_chasto(brosok):
    grani = [0, 0, 0, 0, 0, 0]
    for b in range(256):
        g = brosok(b)
        if g > 0:
            grani[g - 1] = grani[g - 1] + 1
    return grani

def po_modulyu(b):
    return b % 6 + 1

def s_otkazom(b):
    # 252 = 6 · 42: байты 252..255 отбрасываем и бросаем заново;
    # 0 - знак «байт не годится, бросай заново»
    if b >= 252:
        return 0
    return b % 6 + 1

for imya, f in [["b % 6 + 1:   ", po_modulyu],
                ["с отказом:   ", s_otkazom]]:
    g = kak_chasto(f)
    vsego = 0
    for x in g:
        vsego = vsego + x
    print(imya, g, "| шестёрка", round(100 * g[5] / vsego, 2), "%")
print("честная грань:", round(100 / 6, 2), "%")

b % 6 + 1:    [43, 43, 43, 43, 42, 42] | шестёрка 16.41 %
с отказом:    [42, 42, 42, 42, 42, 42] | шестёрка 16.67 %
честная грань: 16.67 %

256 = 6 · 42 + 4: остаток от деления на 6 проходит по кругу 42 полных раза, и ещё четыре байта, 252-255, дают остатки 0-3. Поэтому грани 1-4 получают по 43 байта, а 5 и 6 - по 42. Это смещение по модулю: остаток от деления равномерного числа неравномерен, если размер области не делится на модуль. Лечение - выборка с отказом: байты 252-255 выбрасывают и бросают заново. Оставшиеся 252 байта делятся на 6 ровно, и каждая грань получает по 42. Перебор считает исходы одного броска; повторный бросок снова равномерен на тех же 252 значениях, поэтому итог после всех повторов распределён так же, как принятые байты. Повторный бросок нужен с вероятностью 4 / 256, то есть в среднем бросков 256 / 252 ≈ 1,016. Граница правила: смещение растёт, когда область мала относительно модуля. Генератор на три бита (0-7) с % 6 даёт граням 1 и 2 вдвое больше шансов, чем остальным.

Разбор: мод, предел и честная потеря

Моды - программы игроков на мини-языке. Сервер выполняет их каждый ход и не может ждать. Узнать заранее, завершится ли программа, нельзя: это проблема останова из раздела 21, и по теореме Райса оттуда же нельзя заранее узнать никакое нетривиальное свойство поведения программы. Остаётся предел - 300 команд. Предел на число команд ограничивает время, только если каждая команда дешёвая: удвоение единицы 300 раз даёт 2³⁰⁰ - число из 301 бита, и арифметика с ним уже не стоит одну операцию. Поэтому настоящий сервер ограничивает и размер чисел, или меряет время мода, а не команды.

# Мод - программа на мини-языке над одной переменной x. Сервер выполняет
# каждый мод каждый ход и не может ждать: у мода предел - 300 команд.
LIMIT = 300

def vypolnit(programma, x):
    # команды: ["+", k], ["*", k], ["//", k]; переходы к команде i:
    # ["если >", k, i], ["если ==", k, i], ["если чётно", i],
    # ["перейти", i]; ["стоп"]
    i = 0
    shagov = 0
    while programma[i][0] != "стоп":
        shagov = shagov + 1
        if shagov > LIMIT:
            return "остановлен на пределе, x = " + str(x)
        k = programma[i]
        if k[0] == "+":
            x = x + k[1]
        elif k[0] == "*":
            x = x * k[1]
        elif k[0] == "//":
            x = x // k[1]
        elif k[0] == "если чётно" and x % 2 == 0:
            i = k[1]
            continue
        elif k[0] == "если >" and x > k[1]:
            i = k[2]
            continue
        elif k[0] == "если ==" and x == k[1]:
            i = k[2]
            continue
        elif k[0] == "перейти":
            i = k[1]
            continue
        i = i + 1
    return "закончил за " + str(shagov) + " команд, x = " + str(x)

# урожай: удваивать запас, пока не станет больше 1000
urozhaj = [["если >", 1000, 3], ["*", 2], ["перейти", 0], ["стоп"]]
# «счастливое число»: правило Коллатца из раздела 1, пока не дойдёт до 1
kollatc = [["если ==", 1, 7], ["если чётно", 5], ["*", 3], ["+", 1],
           ["перейти", 0], ["//", 2], ["перейти", 0], ["стоп"]]
# мод с ошибкой: забыл выход из цикла
vechnyj = [["+", 1], ["перейти", 0], ["стоп"]]

print("урожай с 3:    ", vypolnit(urozhaj, 3))
print("Коллатц с 6:   ", vypolnit(kollatc, 6))
print("Коллатц с 27:  ", vypolnit(kollatc, 27))
print("вечный цикл:   ", vypolnit(vechnyj, 0))

урожай с 3:     закончил за 28 команд, x = 1536
Коллатц с 6:    закончил за 35 команд, x = 1
Коллатц с 27:   остановлен на пределе, x = 3644
вечный цикл:    остановлен на пределе, x = 150

Урожай и Коллатц с 6 закончили. Вечный цикл остановлен - ради этого предел и ставили. Но Коллатц с 27 остановлен тоже, хотя без предела он заканчивается за 486 команд: правило Коллатца из раздела 1 у числа 27 идёт 111 шагов, и мод честный. Это цена предела, и она неустранима: отличить «скоро закончится» от «никогда не закончится» в общем случае нельзя, поэтому любой предел отрезает часть честных программ. Выбор предела - решение о том, сколько честных модов допустимо потерять ради того, чтобы ход длился 100 мс.

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

Смещение, которое заметили игроки. Кубик с % 6 выдаёт шестёрки на 0,26 процентного пункта реже - на полтора процента в относительном счёте. За десятки тысяч бросков сообщество это посчитает, и «рандом подкручен» станет главной темой форума.

Сервер, который ждёт мод. Без предела один мод с забытым выходом из цикла останавливает ход для всех восьми игроков.

Обещание оптимума там, где его нет. «Автоматическая расстановка башен - лучшая возможная» - и игрок находит расстановку лучше. Задача NP-трудна; честная надпись - «хорошая» или гарантия приближения, если она доказана.

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

Лимит времени выполнения у облачных функций, предел шагов у смарт-контрактов, тайм-аут у запроса к базе - всё это тот же ответ на неразрешимость: раз заранее не узнать, остановится ли код, его останавливают снаружи. А смещение по модулю - классическая ошибка при генерации паролей и токенов: random_byte % len( алфавит) с алфавитом из 62 символов даёт первым восьми символам лишний шанс.

Теперь сам

1. Генератор отдаёт число 0-999, нужна карта из колоды в 52 карты. Как получить её без смещения? Какая доля значений уйдёт в отказ?
2. Сервер поднял предел модов до 500 команд. Закончит ли теперь Коллатц с 27?
3. Свойство «путь отряда кратчайший» - доказывать каждый раз или проверять сертификатом? Почему?