Самой важной частью шахматной программы, которая вносит основной вклад в силу игры, является направленный перебор. А самой главной частью направленного перебора являются отсечения и сокращения наиболее неперспективных ходов. Отбрасывая наименее важные ветви, программа вкладывает ресурсы машины в наиболее перспективные варианты. Чем больше отсекает программа, тем дальше она углубляется по дереву вариантов. И чем глубже она считает, тем сильнее играет.
Если бы программа считала до конца - до конечного результата в партии, то ей не потребовалась бы даже оценочная функция. Исторически, программы считали все глубже и глубже, и соответственно играли все лучше и лучше.
Здесь мы рассмотрим три наиболее значимых метода ограничения перебора вариантов. Они наиболее действенны, поскольку применяются по всей глубине дерева, хотя и срабатывают не в каждой позиции. Именно они приводят к наибольшему сокращению ветвления вариантов в дереве перебора, а значит и к наибольшему углублению.
Среди них наиболее важным являются Альфа-Бета отсечения (Alpha-Beta Pruning). Это метод отсечений без потерь, то есть он всегда выдает тот же ход и оценку позиции, что и полный перебор, независимо от качества оценочной функции, но делает это гораздо быстрее.
Двумя другими важными методами являются методы отсечений/сокращений с потерями информации. Такие методы обычно называют эвристиками. Один из них, это метод отсечений с помощью пропуска хода - иначе говоря, нулевой ход (Null Move Pruning), второй - метод сокращений на поздних ходах (Late Move Reductions, LMR).
В большинстве позиций отсечения начинаются с пробного перебора и попытки отсечь нулевым ходом, затем программа пытается отсечь альфа-бетой и если с ее помощью отсечь не получается, тогда подключается LMR и сокращает глубину перебора на оставшихся ходах.
Давайте рассмотрим эти методы более подробно. Ниже приведены схемы небольшого участка дерева перебора. Верхняя диаграмма предполагает позицию с которой начинается перебор вариантов или позицию где‑то в глубине дерева, на локальном участке. Каждая линия, это один из возможных ходов в данной позиции, который перебирается на определенную (заданную) глубину. По ним ход за ходом получаются следующие позиции на бОльшую глубину, из которых генерируются следующие ходы и так далее
Просчитаем на схеме ниже первый возможный ход в начальной позиции на заданную глубину и получим его оценку (например +5). Теперь перейдем к проверке второго возможного варианта. Но сначала попытаемся отсечь его с помощью нулевого хода.
Общая очередность перебора будет следующая:
1. Principal Variation (PV)
Как уже написано выше, сначала смотрим основной вариант (PV). Это любая ветка в начале перебора или лучшая с предыдущего перебора, если таковой ранее проводился, но c добавлением полухода глубины. На схеме ниже она находится слева.
Допустим мы исследовали основной вариант и получили оценку +5. Теперь переходим к следующему варианту, который уже попытаемся отсечь.
2. Null Move Pruning
Используя метод нулевого хода попытаемся отсечь вторую ветку по-быстрому, до начала основного перебора. Для этого после первого хода варианта производим в ветке "нулевой" ход и далее пробный перебор с сокращенной глубиной. Иначе говоря сейчас в нижней позиции на схеме ход противника, но мы пропускаем его и снова ходим за себя. Мы нарушаем правила шахмат, но нам нужно лишь получить информацию об отсечении.
Главный принцип - если даже после двух наших ходов подряд, оценка все равно ниже чем у основного варианта (на схеме +3 меньше, чем +5), то такой вариант никуда не годится, поэтому сразу же отсекаем его.
Логика следующая - поскольку право хода обычно является преимуществом, то два хода подряд просто огромное преимущество. И если даже они не помогли, значит вариант плох и не достоин рассмотрения. Можно отсекать. Конечно, для случаев цугцванга есть специальные ограничения.
Если же мы напротив, получили оценку выше, чем у основного варианта (допустим +18), значит у хода есть некоторые перспективы. Мы отменяем нулевой ход и приступаем к основному перебору. Генерируем ходы из нижней позиции на схеме теперь уже по всем правилам шахмат.
3. Ordering
Соответственно генерируются ответы соперника и производится их сортировка в порядке перспективности. По каким правилам - будет описано ниже.
4. Alpha-Beta Pruning
Теперь попытаемся снова отсечь, на этот раз альфа-бетой.
Схема альфа-бета отсечений, после неудачного применения нулевого хода (+18):
Смотрим на схеме ходы из нижней позиции. Сначала делаем первый ход по сортировке. Исследуем его на полную (то есть заданную) глубину.
Допустим, мы получили для первого рассмотренного хода оценку +2. Это предполагаемый ответ нашего соперника. Лучше чем на +2 в данном варианте мы уже не можем рассчитывать, поскольку здесь ход выбирает соперник, а на ответ с большей оценкой он не согласится. Отсекаем.
Действительно, мы предполагаем, что соперник не враг себе и выберет лучший ход для себя, а не для нас. То есть из всех ответов это будет ход с наименьшей оценкой. Если у других ответов оценка будет выше +2, то он их не выберет, а если ниже, то он их выберет, но тогда оценка станет еще меньше. В таком случае оценку выше +2 мы никак не получим. А это в свою очередь не устраивает уже нас, поскольку у нас в запасе есть основной вариант с оценкой +5, который мы и выберем. Значит никакие ответы в текущем варианте нас уже не устроят и нет смысла их рассматривать. Следовательно, в головной позиции схемы отсекаем второй вариант и переходим к следующему.
Если говорит технически, то +2 меньше чем +5, а значит у нас произошло отсечение по бете. Правда в реальных программах обычно используют инвертированную модель перебора и отсекают по превышении беты. Но здесь мы не будем на этом останавливаться.
Из схемы выше очевидно, что в первую очередь необходимо смотреть ответы, которые вызовут отсечение. Поэтому перебор следует начать с варианта, который принесет нам оценку ниже +5. Иначе перебор может затянуться. Конечно мы не можем заранее знать, какой ход принесет нам такую оценку, но можем попытаться хотя бы провести предварительную сортировку ходов на основании формальных признаков. Такая сортировка выполняется перед началом основного перебора по пункту 3.
В человеческих шахматах принцип альфа-бета отсечений тоже используется. В двух словах его логику можно описать так:
"Если в каком-то варианте мы сразу же наткнулись на сильный ответ противника, то вариант можно отбросить немедленно". То есть забраковать, не рассматривая остальные ответы. Действительно, какой смысл идти на плохой вариант? У оппонента тут есть как минимум один сильный ход и соответственно хорошая игра. Таким образом, человек может сильно экономить время на расчете подобных вариантов.
Но чтобы реализовать альфа-бету для машины, сперва надо бы определить что такое "сильный ответ" и как его найти "сразу". Первое понятно - мы просто сравниваем с оценкой основного варианта, и если она лучше, то немедленно отсекаем текущий вариант.
Второе сложнее. Человек сразу видит сильный ответ, а для машины нам придется предварительно отсортировать технически возможные ходы из позиции в порядке их выгоды для соперника. "Сильный ответ противника", это соответственно ход с наименьшей оценкой для нас. Но поскольку мы заранее не знаем какие будут оценки ходов не проводя перебора, то попробуем их оценить предварительно, на основании простых внешних признаков.
Итак, перед нами стоит задача начать перебор с ответа, оценка в котором предполагается быть меньше или равной +5. Тогда мы сможем отсечь вариант немедленно. Пусть не будет никаких лишних вычислений. Смотрим только простые признаки. Теперь вернемся к пункту 3 и рассмотрим методы сортировки.
3. Ordering
Необходимо отсортировать ходы в порядке убывания их силы для соперника. Исторически сложился следующий порядок выборки ходов:
а) Сначала проверяем в хеш-таблицах, не просматривалась ли эта позиция ранее с требуемой или большей глубиной. Если такая позиция присутствует, то берем лучший ход для нее из таблицы.
Хеш-таблицы, или таблицы перестановок (Transposition table), это таблицы уже просматривавшихся ранее позиций с известной оценкой и лучшим ходом в них. По мере перебора в таблицу заносятся новые позиции, а старые удаляются по превышению выделенного объема оперативной памяти. Для хранения и поиска позиций используются хеш-ключи по методу Зобриста.
б) Смотрим "выгодные" взятия. То есть взятия с положительным материальным балансом, отсортированные по данному параметру. Взятия резко повышают оценку сопернику, иначе говоря "выгодность" хода, поэтому разумно предположить, что они будут отсекать в первую очередь.
Стандартные методы для данной процедуры - MVV/LVA или SEE.
MVV/LVA сортирует все возможные взятия в позиции по принципу соотношения ценности атакующей и атакуемой фигуры. В первую очередь смотрим взятие, где наименее сильная фигура бьет наиболее сильную, затем смотрим взятие с меньшей разницей и т. д.
SEE - сортировка взятий в позиции по соотношению числа и силы фигур нападающих и защищающих некоторое поле шахматной доски. То есть подсчет "выгодности" каждого размена отталкивается от общего числа нападений и защит на определенное поле. Это то же самое, что подсчет числа "боёв" на определенное поле у людей, которые ленятся считать размены перебором вариантов.
SEE - очень "ходовой" метод. Его используют во многих частях программы для разных целей. В старых программах его даже использовали вместо ФВ (QS), чтобы не тратить ресурсы и память для расчета разменов.
в) Смотрим тихие ходы. Сначала, это так называемые "Киллеры" (Killers), иначе говоря "убойные ходы" - ходы, которые недавно вызывали отсечение.
Логика заключается в том, что в похожих позициях обычно и отсекающие ходы одинаковые. Значит надо в первую очередь попробовать ходы недавно вызывавшие отсечение. Запоминаем два или три последних отсекавших тихих хода и рассматриваем их по принципу - самый последний отсекавший смотрим в первую очередь. По мере продвижения по дереву ряд киллеров обновляется новыми отсекавшими ходами, которые вытесняют наиболее старые. Для каждой глубины ведем отдельный список киллеров.
г) Смотрим тихие ходы в порядке статистики истории отсечений (History).
По мере перебора мы ведем статистику отсекавших ходов, но уже безотносительно подобия позиции. Ходы которые отсекают чаще и бОльшие ветки поднимаются в списке, а остальные соответственно опускаются. Будем вести таблицу таких отсечений и динамически ее обновлять. В современных программах таких таблиц несколько. Они ведутся в том числе и для взятий.
д) "Невыгодные" взятия и остальные ходы.
*****
Теперь представим, что мы отсортировали ходы, посмотрели первый ответ соперника и отсечения альфа-бетой не произошло. Допустим оценка первого хода в схеме выше была не +2, а +7. Это больше беты, а значит отсечения нет - надо смотреть следующие ответы. Здесь, для ходов с номером по сортировке >1 возможен еще один способ сокращения перебора. Он называется LMR.
5. Late Move Reductions (LMR)
Выше мы предположили, что после рассмотрения первого ответа соперника получена оценка +7. Давайте обновим схему:
Суть метода в том, что при нормальной сортировке, оценки ходов после первого будут только расти, а значит соперник их все равно не выберет. Поэтому мы можем сэкономить и рассмотреть их с сокращенной глубиной. Причем, чем выше номер хода по сортировке, тем сильнее мы можем подрезать ветку. Если же вдруг какой-то ход покажет неожиданно низкую оценку, то его всегда можно пересчитать на полную глубину.
Иначе говоря, с оценкой +7 первый ход по сортировке не вызывает отсечения. Нужно смотреть следующие по номеру ходы (ответы). При идеальной сортировке их оценки после перебора должны быть ещё выше, а значит отсечения снова не состоятся. Сопернику такие ответы тоже не нужны - оценка растет для нас, а значит для него эти варианты только хуже. Выбор хода за ним, и он просто не будет так ходить. И выберет первый ход с оценкой +7, а потому мы также должны ожидать именно такой ответ.
Казалось бы, тогда и не нужно смотреть остальные ходы, если они никому не нужны. Но сортировка у нас простейшая - явно не идеальная. Поэтому смотреть ходы после первого нам все-таки придется. Вдруг на одном из них получим оценку ниже +7 и тогда лучший для соперника вариант изменится? Или даже получим оценку ниже +5 (бета) и отсечение все же произойдет?
Здесь возможен компромисс. Поскольку сортировка у нас более-менее справляется, то ходы с оценкой ниже +7 будут редко появляться в переборе, а значит давайте смотреть ходы после первого с меньшей глубиной. И чем больше номер хода по сортировке, тем с меньшей глубиной его можно рассматривать, поскольку вероятность, что он выйдет на первую линию уменьшается. То есть, если ход, который идет вторым номером разумно "подрезать" совсем чуть-чуть, то глубину каждого следующего хода будем сокращать все больше и больше. В этом суть метода Late Move Reductions (LMR) - сокращения на поздних ходах.
Но если какой-то ход все-таки покажет неожиданно низкую оценку, то его нетрудно пересчитать с полной глубиной. Как показывает практика, сокращать глубину на всех поздних ходах и изредка производить повторные переборы на полную глубину гораздо выгоднее, чем считать все подряд.
Итак, если сортировка хороша, то по мере просмотра ходов их переборная оценка должна подниматься (+9, +12, +11). Но если оценка для какого-то из поздних ходов неожиданно упадет, то скорее всего мы напортачили с сортировкой. Если оценка очередного хода будет ниже оценки лучшего ответа соперника (+7) или даже беты (+5, т.е. хуже основного варианта), то мы производим перерасчет такого хода уже с полной глубиной.
Если перерасчет подтвердит понижение оценки, то значит у нас поменялся лучший ответ соперника. Может даже произойдет отсечение, если оценка будет ниже беты. А если нет, то значит случилась ложная тревога - перебор с сокращенной глубиной давал некорректную оценку. Если нет отсечения по бете, то продолжаем смотреть оставшиеся ходы с сокращенной глубиной, не исключено, что для какого-то из них оценка снова обвалится.
*****
Подведем итоги. Рассматривая в совокупности все три метода отсечений, мы можем увидеть, что отсечения или сокращения происходят чуть ли не в любом случае, практически всегда. Не тем, так другим способом.
Данные методы определяют силу игры современных шахматных программ. Резко сокращая перебор, программы резко наращивают глубину. Видят далеко, учитывают все последствия, тем самым сильно повышая качество игры.
Следует предупредить, что описание методов выше идет в терминах минимакса. А в реальных программах, у любого мало-мальски сильного движка реализована схема негамакса. То есть все рассуждения реализованы с инверсией. Логика не меняется, но берется с противоположным знаком. Поэтому, например отсечения в программах происходят по превышению беты. В IV части мы обсудим это подробнее. В целом, суть перебора остается прежней, а написанное выше все же полагаю проще для понимания.
В следующей части мы перейдем от локального рассмотрения методов на отдельных узлах, к обсуждению их полезности в более широком контексте всего дерева перебора. Если кому-то не очень интересно дальнейшее погружение в тонкости организации перебора, он может прочитать сокращенную версию этой статьи, сразу перейдя к обсуждению оценочной функции в V части, а оттуда к заключению в последней части.
Продолжение следует...