Когда дерево не кончается: глубина, оценка позиции и углубление

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

Как думаешь, что делать, когда дерево не кончается

Крестики-нолики мы досчитали до конца: 549 946 узлов, ничья. В английских шашках позиций порядка 5·10²⁰, и их всё-таки досчитали - в 2007 году, после почти двух десятилетий счёта: при идеальной игре ничья. В шахматах дерево партии оценивают числом около 10¹²⁰, и там досчитать до конца нельзя - ни с альфа-бетой, ни без неё.

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

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

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

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

Механизм: обрезка, оценка и горизонт

ПОИСК С ОБРЕЗКОЙ
значение(позиция, осталось):
    если игра кончилась        → точный результат партии
    если осталось == 0         → ОЦЕНКА позиции формулой   ← здесь теряется гарантия
    иначе                      → минимакс по ходам, осталось − 1

ОЦЕНКА ПОЗИЦИИ - дешёвая формула, число «насколько позиция хороша для нас»
     она не доказывает ничего, она УГАДЫВАЕТ

ЭФФЕКТ ГОРИЗОНТА - беда, которой у полного перебора нет:
     неприятность, которую поиск ВИДИТ в пределах своей глубины,
     он отодвигает оттягивающими ходами за горизонт -
     и считает, что избежал её

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

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

Правило

Поиск с обрезкой по глубине перестаёт быть доказательством и становится прогнозом: его ответ верен настолько, насколько верна оценка позиции на горизонте. Качество игры определяется и глубиной, и качеством оценки, и одно другого не заменяет: с бессмысленной оценкой глубина не помогает вовсе. Итеративное углубление - считать глубины 1, 2, 3... подряд - стоит примерно в b/(b−1) раза дороже одного прогона на полную глубину (замер: в 1,5-2,6 раза), а даёт два важных свойства: готовый ответ в любой момент остановки и подсказку по порядку ходов для следующей итерации. Значения позиций кешируют в таблице транспозиций, и в кеш кладут не только число, но и его ТИП - точное значение, верхняя или нижняя граница: альфа-бета возвращает из отсечённых узлов границы, а не значения.

Разбор: ответ обрезанного поиска не сходится, он скачет

Берём дерево из прошлого урока (b = 3, глубина 6, настоящее значение 32) и считаем его с обрезкой на разной глубине. Оценка позиции нарочно грубая - значение самого левого листа поддерева:

обрезка на глубине   2     3     4     5     6 (до конца)
ответ поиска        15    52    15    72    32

Ни одного приближения к настоящему значению. Поиск на глубине 5 уверенно отвечает 72 - вдвое больше правды; на глубине 4 - 15, вдвое меньше. На втором дереве (b = 2, глубина 10, значение 36) ответы глубин 3, 4 и 5 совпадают между собой - 81, 81, 81, - и все три неверны.

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

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

Разбор: сколько стоит пересчитывать одно и то же

Итеративное углубление выглядит расточительно: считаем глубину 1, потом 2, потом 3, и так до d - то есть повторяем работу много раз. Замер говорит, что это дешевле, чем кажется:

дерево            один прогон глубины d   углубление 1..d    отношение
b = 3, d = 6      417 узлов                675 узлов           1,6
b = 2, d = 10     730 узлов               1 911 узлов          2,6
b = 4, d = 6     1 464 узла               2 163 узла           1,5

Причина арифметическая. Прогон на глубину k у полного перебора стоит порядка bᵏ, то есть каждый следующий прогон в b раз дороже предыдущего. Сумма всех прогонов от 1 до d - геометрическая прогрессия b^d · (1 + 1/b + 1/b² + ...), и она не больше чем в b/(b−1) раз превышает последний прогон. При b = 4 это 1,33, при b = 3 - 1,5, при b = 2 - 2. Замер даёт больше - 1,5, 1,6 и 2,6, - потому что считали альфа-бетой, а у неё дерево растёт с глубиной медленнее, чем в b раз (при идеальном порядке - только в √b), и мелкие прогоны весят относительно больше. Чем шире дерево, тем дешевле углубление: в настоящих играх, где b порядка тридцати, накладные расходы - от трёх процентов у полного перебора до двадцати с небольшим у идеально упорядоченной альфа-беты.

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

дерево          углубление без подсказки      с подсказкой прошлой итерации
b = 3, d = 6      675 узлов,  9 647 шагов       598 узлов, 13 757 шагов
b = 2, d = 10   1 911 узлов, 30 151 шаг       1 427 узлов, 37 333 шага
b = 4, d = 6    2 163 узла,  29 025 шагов     2 089 узлов, 44 325 шагов

Узлов стало меньше - на 3, 11 и 25 процентов, - а шагов больше на четверть-половину: подсказку надо хранить и читать на каждом узле, и эта бухгалтерия обошлась дороже сэкономленных узлов. До двух-пяти раз, которые давал идеальный порядок в прошлом уроке, отсюда очень далеко. Объяснение не в том, что приём плох, а в том, что у нас оценка на горизонте - шум: лучший ход при обрезке на глубине 3 ничего не знает о том, что будет лучшим при обрезке на глубине 4, потому что обе оценки случайны. В игре с осмысленной оценкой позиции мелкий поиск предсказывает глубокий хорошо, и там эта подсказка - основной источник порядка ходов.

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

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

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

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

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

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

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

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

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

Второй - честность в формулировках. «Система просчитала все варианты» почти никогда не правда; правда - «просчитала на глубину N с такой-то оценкой». Понимание разницы между доказательством и прогнозом - это то, что отличает инженера от пересказчика пресс-релиза.

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

Теперь сам

Поиск с обрезкой на глубине 4 и на глубине 5 дал одно и то же значение позиции. Можно ли считать, что ответ «устоялся» и дальше углубляться незачем?

замер из этого урока, дерево b = 2, d = 10:
глубина 3 → 81, глубина 4 → 81, глубина 5 → 81
правда:    36

три совпавших подряд ответа - и все три неверны