Минимакс: дерево, в котором половина уровней против тебя

Если ты знаешь, почему на ходу противника берут минимум, и помнишь, что значение позиции - это результат при идеальной игре ОБОИХ, - листай до «Теперь сам».

Как думаешь, в чём разница с прошлой главой

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

Прежде чем читать дальше, ответь: можно ли по-прежнему говорить «лучшее в этой ветке»? И если да, то «лучшее» для кого на том уровне, где ходит противник?

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

Торг через посредника, который всегда работает против тебя. Ты предлагаешь три варианта сделки. Посредник из каждого выбирает худшее для тебя продолжение и приносит обратно. Поэтому оценивать свой вариант надо не по лучшему, что из него МОЖЕТ выйти, а по худшему, что из него БУДЕТ выведено противником.

Отсюда и название, в котором склеены оба слова: ты берёшь максимум из того, что противник уже свёл к минимуму.

Механизм: два правила - на своём ходу и на чужом

МИНИМАКС
значение(позиция):
    если игра кончилась      → результат (выигрыш / проигрыш / ничья)
    если ход НАШ             → max по значениям всех ходов
    если ход ПРОТИВНИКА      → min по значениям всех ходов

цена: порядка b^d - столько листьев у дерева, где b - среднее число
      ходов в позиции, d - глубина

Результат партии записываем числом с нашей точки зрения: выигрыш 1, проигрыш −1, ничья 0. Тогда «лучше для нас» значит просто «больше», а противник, наоборот, тянет число вниз. Формула b^d - прикидка порядка, а не точный счёт: в настоящей игре число ходов меняется от позиции к позиции (в крестиках-ноликах - от девяти до одного), а партии обрываются раньше, чем кончатся клетки.

Что именно доказывает минимакс, стоит сказать точно: значение позиции - это результат при идеальной игре ОБЕИХ сторон. Не «что скорее всего случится», не «что будет против слабого противника», а гарантия: если мы играем по минимаксу, результат будет не хуже посчитанного значения, что бы ни делал противник.

Правило

Минимакс - это рекурсия по дереву игры, в которой правило свёртки меняется с уровнем: на своём ходу берём максимум по детям, на ходу противника - минимум. Значение листа - результат законченной партии (выигрыш, проигрыш, ничья) или, если дерево обрезано, оценка позиции формулой. Значение корня - результат при идеальной игре обеих сторон, то есть гарантия, а не прогноз. Цена - порядка b^d, и это главная проблема: у крестиков-ноликов полное дерево 549 946 узлов (посильно), у шахмат - порядка 10¹²⁰, больше, чем атомов в обозримой части вселенной, поэтому там дерево обрезают по глубине. Удобная запись минимакса - НЕГАМАКС: если значение всегда считать с точки зрения того, кто ходит, то оба уровня свёртываются одной формулой max по ходам (−значение(позиция после хода)), и дублирование кода исчезает.

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

Клетки доски нумеруем с нуля, слева направо и сверху вниз: верхняя строка - клетки 0, 1, 2, средняя - 3, 4, 5, нижняя - 6, 7, 8.

Позиция: X в двух противоположных углах (клетки 0 и 8), O занял центр и правый верхний угол (клетки 4 и 2), ход X. Ходов сделано по два у каждого, так что позиция законная.

X . O
. O .
. . X     ход X

Минимакс для неё даёт 1, то есть X выигрывает при любой игре O. Проверим рассуждением, а не на веру.

У O готова угроза: диагональ 2-4-6, не хватает клетки 6. Значит ход X вынужденный - в левый нижний угол:

X . O
. O .
X . X     ход O

И этот вынужденный ход оказывается выигрывающим. Теперь у X ДВЕ угрозы сразу: левый столбец (X в клетках 0 и 6, нужна клетка 3) и нижняя строка (X в клетках 6 и 8, нужна 7). Одним ходом O может закрыть только одну. Своих угроз у O больше нет: диагональ перекрыта, а на остальных линиях через центр стоит по одному нолику. Значит на следующем ходу X достраивает вторую линию и выигрывает. Это и есть «двойная угроза» - главный мотив в крестиках-ноликах, и движок подтверждает: после хода X в левый нижний угол значение позиции по-прежнему 1.

Замер движка на обеих позициях (про альфа-бетуРазбирается в разделе 16, глава «Перебор в играх - минимакс и альфа-бета»: Альфа-бета: то же значение, вдвое большая глубина за ту же цену - следующий урок):

позиция                         минимакс        альфа-бета (урок ниже)
X в 0 и 8, O в 2 и 4, ход X       178 узлов       83 узла
                                16 233 шага     7 572 шага
после хода X в 6, ход O            37 узлов       31 узел
                                 3 205 шагов    2 691 шаг

Сто семьдесят восемь узлов - это дерево из пяти пустых клеток с проверкой на выигрыш в каждом узле. А вот что получается, когда пустых клеток больше: позиция «X в углу, O в центре» стоит 7332 узла и 667 518 шагов - в предел движка (300 000) она уже не укладывается, хотя до конца партии там всего семь ходов. Этот замер, как и полное дерево с пустой доски, снят с поднятым пределом. Узлы посчитаны отдельным прогоном со счётчиком, шаги - программой без него.

Разбор: негамакс - одна формула вместо двух

Вот минимакс для крестиков-ноликов, которым сняты все замеры выше. В pole девять клеток: 0 - пусто, 1 - крестик, 2 - нолик; pobeda(igrok) проверяет восемь линий, est_hod() - есть ли пустая клетка (обе функции - в заготовке задачи этой главы):

def mm(hod_X):
    if pobeda(1):
        return 1
    if pobeda(2):
        return 0 - 1
    if est_hod() == False:
        return 0
    if hod_X:
        luchshee = 0 - 2                 # меньше любого результата
        i = 0
        while i < 9:
            if pole[i] == 0:
                pole[i] = 1
                v = mm(False)
                pole[i] = 0              # откат хода
                if v > luchshee:
                    luchshee = v
            i = i + 1
        return luchshee
    luchshee = 2                         # больше любого результата
    i = 0
    while i < 9:
        if pole[i] == 0:
            pole[i] = 2
            v = mm(True)
            pole[i] = 0
            if v < luchshee:
                luchshee = v
        i = i + 1
    return luchshee

print(mm(True))

В этом коде два почти одинаковых блока: один берёт максимум, другой минимум. Дублирование раздражает и плодит ошибки (легко забыть поменять знак в одном из них). Приём, который это убирает: считать значение ВСЕГДА с точки зрения того, кто ходит.

если значение считается «за того, кто ходит», то
значение(позиция) = max по ходам ( − значение(позиция после хода) )

потому что «хорошо для меня» = «плохо для соперника» с обратным знаком

def negamaks(hod_igroka):
    if konec():
        return rezultat(hod_igroka)      # с точки зрения того, кто ходит
    luchshee = -2
    for hod in hody():
        sdelat(hod)
        v = 0 - negamaks(1 - hod_igroka)  # знак меняется при спуске
        otkatit(hod)
        if v > luchshee:
            luchshee = v
    return luchshee

Имена здесь условные - это схема, а не программа: konec() - партия закончена, rezultat(...) - её итог для того, кто сейчас ходит (1, −1 или 0), hody() - свободные клетки, sdelat и otkatit - поставить знак и снять его. Начальное -2 - число меньше любого результата; в игре с другой шкалой сюда ставят «меньше наименьшего возможного».

Условие применимости у негамакса одно, и оно важное: игра должна быть с нулевой суммой - выигрыш одного ровно равен проигрышу другого. В крестиках-ноликах, шашках, шахматах это так. Если игроки максимизируют разные величины (например, каждый свои очки, и сумма не постоянна), знак менять нельзя, и нужны два отдельных блока.

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

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

Второе: забыть откат хода. Та же ловушка, что во всей главе про поиск с возвратом: поставил - сыграл - СНЯЛ. В игровом дереве она ещё коварнее, потому что доска одна и ошибку видно не сразу.

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

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

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

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

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

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

Третий - понимание игровых движков. Любая программа, играющая в шахматы или шашки, внутри устроена как минимакс с обрезкой и оценкой; слова «глубина поиска», «горизонт», «оценка позиции» из её логов - это понятия этой главы, до двух последних дойдём через урок.

Теперь сам

У позиции три хода, и чем больше число, тем лучше для нас. После первого хода противник может ответить так, что получится 4 или 7; после второго - 6 или 5; после третьего - 2 или 9. Какое значение у позиции и какой ход правильный?

ход 1 → min(4, 7) = 4
ход 2 → min(6, 5) = 5
ход 3 → min(2, 9) = 2
значение позиции = max(4, 5, 2) = 5, выбираем второй ход