Альфа-бета: то же значение, вдвое большая глубина за ту же цену

Коротко

Альфа-бета - это отсечение по оценке, перенесённое на игровое дерево. Вниз передаются две границы: альфа - что максимизирующий уже себе гарантировал, бета - что минимизирующий уже себе гарантировал. Как только альфа >= бета, оставшиеся ходы в узле смотреть незачем: наверху эту ветку всё равно отвергнут. Значение корня не меняется никогда. При идеальном порядке ходов просматривается b^⌈d/2⌉ + b^⌊d/2⌋ − 1 листьев вместо b^d (при чётной глубине это 2·b^(d/2) − 1) - замер совпал с теорией до единицы: 53 листа вместо 729. Но при худшем порядке альфа-бета дороже минимакса, и это тоже замер.

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

Как думаешь, зачем смотреть остальные ходы

Вернись к дереву из прошлого урока. Первый ход уже разобран: что бы ни делал противник, мы получим не меньше 3. Переходим ко второму ходу, и первый же ответ противника даёт 2.

Прежде чем читать дальше: имеет ли смысл смотреть ОСТАЛЬНЫЕ ответы противника на второй ход? Что они могут изменить - и в какую сторону меняется значение узла, когда противник находит ещё более неприятный ответ?

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

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

Так работает альфа-бета. Отбрасывается не плохой вариант, а вариант, который УЖЕ не может стать лучшим, сколько в нём ни копайся.

Механизм: две границы, которые едут вниз по дереву

АЛЬФА - лучшее, что максимизирующий игрок уже обеспечил себе
        где-то выше по дереву. Нижняя граница результата.
БЕТА  - лучшее, что уже обеспечил себе минимизирующий.
        Верхняя граница результата.

инвариант: интересны только значения в интервале (альфа, бета)

в узле МАКСИМУМА:  нашли значение v → альфа = max(альфа, v)
в узле МИНИМУМА:   нашли значение v → бета  = min(бета,  v)
в любом узле:      если альфа >= бета → выход, остальные ходы не смотрим

Почему отсечение законно - это главное место урока. Пусть мы в узле минимума и уже нашли там значение 2, а альфа равна 3 (выше по дереву максимизирующий уже гарантировал себе 3). Значение этого узла будет не БОЛЬШЕ двойки - минимум только уменьшается. Значит узел даёт максимизирующему не больше 2, а у него уже есть 3; он эту ветку не выберет при любом её точном значении. Остальные ходы могут уточнить значение узла, но не могут изменить решение наверху - значит их не нужно считать.

Пройдём по дереву из прошлого урока - три хода, ответы противника 3, 5, затем 2, 9, затем 1, 8:

корень (максимум): альфа = −∞, бета = +∞
  ход 1 (минимум): лист 3 → значение 3;  лист 5 → остаётся 3.  Вернули 3
корень: альфа = 3
  ход 2 (минимум, альфа = 3): лист 2 → значение 2, бета = 2
         альфа 3 >= бета 2 → выход.  Лист 9 НЕ смотрели
  ход 3 (минимум, альфа = 3): лист 1 → значение 1, бета = 1
         альфа 3 >= бета 1 → выход.  Лист 8 НЕ смотрели
корень: max(3, 2, 1) = 3

Просмотрено четыре листа из шести, а ответ тот же, что у минимакса. Это и есть ответ на вопрос из начала урока: остальные ответы противника на второй ход могут только уменьшить значение узла, а оно уже меньше тройки, которая у нас в кармане.

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

Правило

Альфа-бета передаёт вниз интервал (альфа, бета) - диапазон значений, которые ещё могут повлиять на ответ. В узле максимума альфа поднимается найденными значениями, в узле минимума бета опускается; при альфа >= бета оставшиеся дети не рассматриваются. Значение корня совпадает с минимаксным всегда, и это первое, что проверяют тестом. Число просмотренных листьев зависит от ПОРЯДКА ходов: при идеальном порядке (лучший ход первым) просматривается b^⌈d/2⌉ + b^⌊d/2⌋ − 1 листьев, то есть примерно корень из полного числа - при тех же ресурсах глубина поиска удваивается. При худшем порядке отсекается мало (в замерах ниже - 13-20% листьев), и альфа-бета оказывается ДОРОЖЕ минимакса: бухгалтерия стоит больше, чем экономят отсечения.

Разбор: замер на абстрактном дереве, четыре порядка

Дерево полное, ветвление b, глубина d, значения листьев случайные и лежат в списке znach слева направо; у узла с номером uzel дети имеют номера uzel * b + k. Вот альфа-бета для такого дерева целиком:

def ab(uzel, gl, maks, alfa, beta):
    if gl == d:
        return znach[uzel]                       # лист
    if maks == 1:                                # узел максимума
        luchshee = 0 - 1000
        k = 0
        while k < b:
            v = ab(uzel * b + k, gl + 1, 0, alfa, beta)
            if v > luchshee:
                luchshee = v
            if luchshee > alfa:
                alfa = luchshee                  # поднимаем альфу
            if alfa >= beta:
                return luchshee                  # остальных детей не смотрим
            k = k + 1
        return luchshee
    luchshee = 1000                              # узел минимума - зеркально
    k = 0
    while k < b:
        v = ab(uzel * b + k, gl + 1, 1, alfa, beta)
        if v < luchshee:
            luchshee = v
        if luchshee < beta:
            beta = luchshee                      # опускаем бету
        if alfa >= beta:
            return luchshee
        k = k + 1
    return luchshee

print(ab(0, 0, 1, 0 - 1000, 1000))               # в корне интервал - «всё что угодно»

Минимакс - тот же код без параметров alfa, beta и без трёх строк с ними в каждом блоке. В корень передаются числа заведомо меньше и больше любого значения листа: здесь листья от 1 до 99, поэтому хватает −1000 и 1000.

Считаем узлы, листья и шаги движка. «Как есть» - листья в случайном порядке. «Идеальный порядок» - дети каждого узла заранее переставлены так, что лучший ход стоит первым; «худший» - так, что последним. Чтобы так переставить, пришлось сначала посчитать всё дерево минимаксом: в настоящей игре этого сделать нельзя, так что две нижние строки - границы возможного, а не рецепт.

b = 3, d = 6 (729 листьев, значение 32)
                                 узлов   листьев    шагов
минимакс                          1093       729   10 489
альфа-бета, как есть               417       233    5 018
альфа-бета, идеальный порядок      125        53    1 497
альфа-бета, худший порядок         939       606   11 432

b = 2, d = 10 (1024 листа, значение 36)
                                 узлов   листьев    шагов
минимакс                          2047      1024   20 964
альфа-бета, как есть               730       304    9 202
альфа-бета, идеальный порядок      208        63    2 586
альфа-бета, худший порядок        1705       815   21 530

b = 4, d = 6 (4096 листьев, значение 26)
                                 узлов   листьев    шагов
минимакс                          5461      4096   50 630
альфа-бета, как есть              1464       946   17 087
альфа-бета, идеальный порядок      268       127    3 150
альфа-бета, худший порядок        4839      3555   57 383

Три вещи в этой таблице.

Первое: значение везде одинаковое - 32, 36, 26. Порядок ходов и отсечения не меняют ответ, только цену. Это и есть главный тест на правильность реализации.

Второе: идеальный порядок попал в теорию до единицы. Формула b^⌈d/2⌉ + b^⌊d/2⌋ − 1 даёт для наших трёх деревьев 53, 63 и 127 листьев - ровно столько и просмотрено. Такого точного совпадения теории с замером в курсе ещё не было, и оно не случайно: при идеальном порядке у дерева остаётся ровно две «ленты» полных уровней, и их размеры и есть эти степени.

Третье, самое неприятное: при худшем порядке альфа-бета дороже минимакса по шагам - 11 432 против 10 489, 21 530 против 20 964, 57 383 против 50 630. Листьев она при этом просматривает меньше (606 из 729), но за каждую проверку альфа >= бета и за передачу границ надо платить, и на плохом порядке плата превышает экономию. Это тот же вывод, что был про отсечения в целом: сделка, а не улучшение.

Разбор: откуда берётся корень из числа листьев

Почему идеальный порядок даёт именно b^(d/2), стоит понять, а не запомнить.

Пусть лучший ход везде стоит первым. Тогда в каждом узле:
  ПЕРВЫЙ ребёнок считается полностью - он задаёт точное значение узла
  ОСТАЛЬНЫЕ b−1 детей нужны только для опровержения: достаточно
      одного их хода, который покажет «этот вариант не лучше»

то есть на каждом втором уровне ветвление падает с b до 1:
  уровень 1: b ветвей   (все дети корня надо хотя бы попробовать)
  уровень 2: 1 ветвь    (опровергли одним ходом)
  уровень 3: b ветвей
  уровень 4: 1 ветвь
  ...
⇒ просмотренных путей ≈ b · 1 · b · 1 · ... = b^(d/2)

Это прикидка порядка, и в ней спрятана половина ответа. Корень из числа листьев при b = 3, d = 6 - это 27, а в таблице 53. Откуда вторая половина: опровергнуть вариант одним ходом можно, только если значение ЭТОГО хода известно точно, то есть под ним снова нужен полный перебор всех ответов. Роли чередуются, и получаются две «ленты» листьев - одна начинается с полного уровня, другая с уровня из одной ветви. В каждой по b^(d/2) листьев, один лист у них общий: 27 + 27 − 1 = 53. При нечётной глубине ленты разной длины, отсюда потолок и пол в точной формуле.

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

Замер на крестиках-ноликах, где порядок ходов «как в списке клеток», то есть никакой:

позиция                      минимакс            альфа-бета
пустая доска              549 946 узлов        18 297 узлов   в 30 раз меньше
                           49,4 млн шагов       1,73 млн шагов
X в углу, O в центре        7 332 узла             844 узла
                            667 518 шагов         80 928 шагов  ← минимакс в предел
                                                                движка (300 000) не влезает
X в клетке 0, O в клетке 1  8 232 узла             749 узлов
                            777 493 шага          74 205 шагов

Значения совпадают: 0 (ничья), 0 (ничья), 1 (выигрыш X - нолик, ответивший на угол стороной, проигрывает). Узлы здесь посчитаны отдельным прогоном со счётчиком, шаги - программой без него.

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

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

Второе: вернуть из отсечённого узла «значение». После выхода по альфа >= бета возвращённое число - не точное значение узла, а только граница. Для ответа в корне этого достаточно, но если где-то в коде это число КЭШИРУЕТСЯ как точное, ошибка расползётся по дереву. Кеш здесь - таблица позиций: одна и та же позиция получается разными порядками ходов, и её значение запоминают, чтобы не считать дважды (в игровых программах её называют таблицей транспозиций). В такую таблицу кладут не только значение, но и пометку «точное / не выше / не ниже».

Третье: перепутать знаки при отсечении в негамаксе. В негамаксе при спуске меняются местами и знаки, и границы: -negamaks(..., -бета, -альфа). Забыть поменять местами альфу и бету - значит получить отсечения, которые режут нужное; ответ станет неверным молча.

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

Пятое: проверять правильность на одном дереве. Правильная проверка - сравнить значение корня с минимаксом на десятке случайных деревьев. Любая ошибка в границах даёт расхождение почти сразу; на одном дереве она может и не проявиться.

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

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

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

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

Теперь сам

В узле минимума уже найдено значение 2, а альфа равна 5. Можно ли не смотреть остальные ходы, и что вернуть из узла?

Ответ. Смотреть не надо, вернуть надо 2 - но помня, что это ГРАНИЦА, а не точное значение.

узел минимума: значение узла ≤ 2 (минимум может только падать)
альфа = 5:     максимизирующий выше уже обеспечил себе 5
⇒ эта ветка даёт ему не больше 2, он её не выберет
⇒ остальные ходы не изменят РЕШЕНИЯ наверху

Возвращённая двойка попадёт в сравнение max(5, 2) и проиграет - значит её неточность ни на что не повлияет. А вот если бы мы положили её в таблицу позиций как точное значение узла, она потом всплыла бы в другом месте дерева, где альфа другая, и там испортила бы ответ. Отсюда правило: в кеш кладут не только число, но и его тип - точное значение, верхняя граница или нижняя.

Главное

Альфа-бета - это отсечение по оценке в игровом дереве: вниз едут две границы, альфа (что уже обеспечил себе максимизирующий) и бета (что обеспечил минимизирующий), а при альфа >= бета оставшиеся ходы узла не рассматриваются - наверху эту ветку всё равно отвергнут при любом её точном значении. Значение корня совпадает с минимаксным всегда; это и есть тест на правильность реализации. Выигрыш целиком зависит от порядка ходов: при идеальном порядке просматривается b^⌈d/2⌉ + b^⌊d/2⌋ − 1 листьев (замер совпал с формулой до единицы - 53 вместо 729), то есть при тех же ресурсах глубина поиска удваивается. При худшем порядке отсекается мало, и альфа-бета оказывается дороже минимакса - 11 432 шага против 10 489. Из отсечённого узла возвращается граница, а не точное значение, и в кеш его кладут только с пометкой об этом.