В третьей части мы взглянем на дерево перебора в общем контексте поиска. Увидим, каким образом методы отсечений из предыдущей части влияют на дерево в целом или на значительные его части, а также для полноты картины оценим влияние этих методов в историческом контексте. Эту и следующую части можно пропустить, если общего описания основных методов ограничения перебора ранее кажется достаточным.
Итак, давайте взглянем на дерево перебора более обобщенно. Сначала рассмотрим только дерево альфа-бета отсечений с идеальными сортировками, пока что без нулевого хода и LMR. Некоторая часть типичного дерева для такого перебора показана на рисунке ниже. Верхний узел (позиция) не обязательно относится к корневому. Штриховыми линиями намечены ходы удаленные из перебора альфа-бетой. На схеме показаны только три возможных хода из каждой позиции, но в реальном дереве шахматной игры их, естественно, будет около 30 — 40.
Как нетрудно заметить, отсечения в дереве происходят не на каждом узле. По мере увеличения глубины по каждой ветке альфа-бета отсекает как бы «через раз». Если на каком-то узле достаточно рассмотреть один ход для отсечения остальных вариантов, то на следующей глубине приходится уже смотреть все продолжения. Далее в глубину ситуация повторяется. Это вызвано тем, что альфа-бета отсечения производятся по превышению беты, а поскольку на некоторых узлах бета равна бесконечности, то соответственно ее невозможно превысить и отсечений не происходит.
Позиции, или иначе говоря — узлы, nodes, где возможны отсечения альфа-бетой, принято называть Cut-nodes. Узлы где они невозможны, называются All-nodes — буквально узлы, где рассматриваются все возможные продолжения. Количество узлов обоих типов в дереве перебора примерно одинаково. Более наглядно типы узлов показаны на изображении ниже. Как видим, на схеме еще присутствуют узлы, обозначенные как PV-nodes. Это узлы основного варианта расчетов — цепочки лучших ходов и сильнейших ответов на них, которую мы обычно видим на экранах как «первую линию». На подобных схемах ее как правило размещают слева.
Таково классическое деление дерева перебора по типам узлов в системах с альфа-бета отсечениями. В современных программах типы узлов понимают немного иначе, но мы обсудим это позже.
Альфа-бета отсечения — это один из немногих методов отсечений без потерь, то есть он выдает тот же ход и оценку, что и полный перебор на ту же самую глубину. Иначе говоря от его использования мы ничего не теряем, но существенно выигрываем во времени. Сокращение перебора в дереве вариантов от использования метода составляет около квадратного корня от количества позиций для полного перебора (это очень много, например одна минута вычислений вместо одного года).
Достаточно очевидно, что так как альфа-бета как бы «перепрыгивает» глубину через одну, то даже с идеальными сортировками сама по себе она не в состоянии увеличить глубину более чем в два раза, по сравнению с полным перебором. То есть метод имеет свои ограничения. Тем не менее он позволяет сократить количество рассматриваемых вариантов в каждой позиции с 30 — 40 возможных, до 11 — 14 только альфа-бетой, а при хорошей сортировке ходов приблизиться к теоретическому пределу альфа-беты — около 6 вариантов в среднем на позицию. Это уже дает возможность при наличии вычислительного ресурса хотя и с трудом, но увеличивать глубину. При полном переборе это было бы практически невозможно.
Подобный поиск был типичным для программ с конца 70-х и до конца 80-х годов. Используя также хеш-таблицы (таблицы перестановок для повторяющихся позиций) программы сокращали ветвление вариантов до 5,5 на переборную позицию.
Начиная с Каиссы 1972, которая лет на 5 опережала свое время и заканчивая Дип Блю 1997, который четверть века спустя примерно на столько же отставал, отсечения выполнялись преимущественно альфа-бетой с сортировками. Еще в 80-е было показано (а предполагалось и ранее), что сила программ быстро растет с увеличением глубины, особенно на первых порах. Этот рост составляет примерно 150 — 200 пунктов рейтинга на каждую единицу глубины, что почти равно одному шахматному разряду. Учитывая, что прогресс качества оценочной функции как в те времена, так и позднее был невелик, а методы отсечений с потерями до начала-середины 1990-х ещё не играли особой роли, то сила программ была обычно пропорциональна глубине до которой они досчитывали.
На этом и базировалась идея Дип Блю — используя сверхбыстрые специализированные микросхемы и распараллеливание, достигнуть уровня чемпиона мира. Но так как дерево перебора все равно растет очень быстро, то даже при ветвлении 5,5 (а на самом деле почти 8 из-за потерь на распараллеливание и прочих факторов) огромные и по современным меркам мощности Дип Блю не позволяли ему углубиться дальше 12 полуходов итеративного перебора.
Тем не менее альфа-бета отсечения привели к огромному прогрессу в силе игры. Например, если бы Дип Блю использовал действительно полный перебор, то его глубина сократилась бы до 7 полуходов и играл бы он не сильнее первого шахматного разряда.
Давайте теперь взглянем непосредственно на цифры. Например, Каисса 1972 года вычисляла около 200 позиций в секунду, почти досчитывала до глубины 5 полуходов в середине партии и оценочно играла на 1700 — 1800 пунктов рейтинга. Это уровень 1 — 2 шахматного разряда.
Далее пошло по нарастающей. Программы буквально «выгрызали» каждую следующую глубину. Чтобы увеличить глубину на один полный ход (т.е. два полухода, белых + черных), машину требовалось ускорить примерно в 5,5^2 = 30 раз. На два хода — в тысячу раз, на четыре хода — в миллион раз и т. д.
Быстрый прогресс в микроэлектронике позволил резко увеличить скорость, переход на специализированное железо увеличил ее еще на несколько порядков, сколько-то добавило распараллеливание. И результат пришел. Программам (читай — Дип Блю) все-таки удалось дотянуться до высшего уровня. Смотрим:
1976г. Каисса - 200 поз/сек, глубина 5, рейтинг 1800, I - II разряд1983г. Белле - 100 тыс.поз/сек, глубина 8, рейтинг 2200, кмс-мастер спорта1989г. Дип Сот - 700 тыс.поз/сек, глубина 10, рейтинг 2550, гроссмейстер1997г. Дип Блю - 125 млн.поз/сек, глубина 12, рейтинг 2800, чемпион мира
Цифры выше не совсем бьются, но нужно учесть, что не смотря на принципиальную схожесть алгоритмов перебора, программы все-таки были разные. Кроме того, числа здесь разной точности, полученные в разное время, разными людьми и некоторые из них оценочного характера.
Для более поздних программ сравнение по глубине уже не работает. Его нельзя проводить, поскольку в ведущих программах началось использование методов отсечений с потерями, и к примеру, чтобы играть на рейтинг 2800 требовалось считать уже на 15 — 16 единиц итеративной глубины. То есть дополнительные отсечения пришлось компенсировать увеличением глубины по основным линиям. Но зато они позволили уменьшить требования к скорости компьютеров и уровня 2800 достигли уже обычные персоналки.
*****
С начала-середины 1990-х появились и начали набирать популярность отсечения методом нулевого хода (Null Move Pruning, NMP). Уже к концу столетия ни одна серьезная программа не обходилась без них.
Давайте теперь добавим нулевой ход на общее дерево перебора на схеме выше, для чего отметим на нем кроме альфа-бета отсечений, еще и те ходы (ветви), которые принципиально возможно отсечь с помощью NMP. По сравнению со схемой NMP из предыдущей части значок отсечений намеренно сдвинут на уровень вниз, для большей наглядности. На пунктирных линиях возможные отсечения не показаны, дабы не загромождать схему:
Как мы видим, отсечения посредством нулевого хода происходят только на Cut-nodes, аналогично альфа-бете. Это происходит, потому что нулевой ход тоже отсекает по превышении беты. Но если альфа-бета может отсекать на Cut-nodes все ходы кроме первого (альфа-бета обязана его просмотреть на полную [заданную] глубину, чтобы принять решение об отсечении), то нулевым ходом можно отсекать и первый ход на этих узлах. В этом отношении мы можем даже условно рассматривать нулевой ход, как нулевой по сортировке. В таком случае сам термин «нулевой ход» — изначально неудачная калька при переводе с английского, даже обретает некоторый смысл.
Нулевой ход производит отсечения окончательно. Если выполнить отсечение выше по дереву, то ветка ниже рассматриваться уже не будет, и очевидно, что нижние отсечения не состоятся. По крайней мере до следующей итерации, где перебор вернется в тот же узел. Поэтому если произошло отсечение выше по схеме, то нижние значки NMP-отсечений «недействительны». Но отсечения нулевым ходом происходят не всегда, поэтому в свою очередь, если отсечения выше нет, то они возможны ниже по дереву.
Еще можно отметить, что несмотря на то, что отсечения происходят на Cut-nodes, нулевой ход прежде всего предотвращает появление в дереве All-nodes. По грубой прикидке методом нулевого хода отсекается примерно 60% из всех потенциальных All-nodes.
Именно отбрасывание All-nodes в первую очередь позволяет производить дальнейшее сокращение ветвления (branching factor) у программ. На рубеже веков введение и совершенствование нулевого хода позволило снизить ветвление с типичного в конце 80-х значения 5,5, до гораздо меньшего 3,5. Это позволило играть на уровне Дип Блю и топ-гроссмейстеров даже программам запускавшимся на рабочих станциях на скорости всего 3 — 4 млн.поз/сек. В то же время нулевой ход, это метод отсечений с потерями информации, а значит программам необходимо было наращивать глубину до 15 — 16, чтобы достичь уровня Дип Блю, который считал до глубины 12, но не упускал ни одного полезного хода.
После пропуска хода NMP-отсечения выполняются не сразу, а производится некоторый пробный перебор на сокращенную глубину. Это позволяет повысить надежность отсечений, но в то же время не сильно увеличивать объем перебора. Программы 00-х обычно сокращали глубину пробного перебора всего на 3 полухода при общей глубине 15 — 16. Кажется немного, но экономия могла достигать 6 х 6 х 6 = 216 раз. А учитывая рекурсивное исполнение, пробный перебор проводился в значительной степени «бесплатно», не слишком перегружая компьютер и в то же время обеспечивая солидную надежность. В настоящее время величина сокращений регулируется динамически и они могут сильно варьироваться в зависимости от обстоятельств.
Пробный перебор не включается в основное дерево перебора, поскольку пропускать ходы не по правилам шахмат. Он только определяет — производить отсечение или нет. При этом нулевой ход допускает рекурсивное исполнение, то есть после нулевого хода в дереве пробного перебора допускается снова выполнять нулевой ход неограниченное число раз, пока это позволяют условия. Но конечно не подряд.
Если пробный перебор показал, что отсечение нулевым ходом возможно, то проводится еще верификационный перебор — из той же позиции и тоже на сокращенную глубину. В нем уже не будет пропуска хода. Такой перебор необходимо произвести, чтобы исключить возможность цугцванга, когда нулевой ход использовать нельзя, поскольку сам принцип нулевого хода опирается на преимущество права выступки. А при цугцванге право хода является фатальным недостатком позиции.
Соответственно, нулевой ход не применяется в играх, где право выступки не дает заметного преимущества. Например в шашках, где оппозиция важнее права на ход. В шахматах нулевой ход также не допускается, когда с нашей стороны на доске не остается фигур, кроме пешек. Шахматы без фигур по сути превращаются в шашки, поэтому значение оппозиции тоже становится решающим. В шашках же место нулевого хода заняли MultiCut или ProbCut, тогда как в шахматах эти методы находятся на вторых ролях. Но мы их тоже рассмотрим, когда углубимся в код поиска Стокфиша.
Отсечения методом NMP не состоятся, если пробный перебор не выявит превышения беты или верификационный перебор выявит некорректность нулевого хода, или же изначально в программе не будут выполнены условия для запуска нулевого хода. В таких случаях придется проводить обычный перебор, как описано в предыдущей части. Конечно, пробный и верификационный перебор, это дополнительный перебор, но выгода от использования NMP настолько велика, что небольшой дополнительный перебор с лихвой компенсируется отсечениями в дереве на неосновных ветках.
Надо понимать, что при нулевом ходе пробный перебор будет проведен в любом случае, независимо от того произведет он отсечение или нет. Поэтому, любые оптимизации на нем желательны. Чтобы такой перебор не стал напрасным избыточным счетом, обременяющим основной перебор, помимо использования рекурсивного исполнения и сокращенной глубины его также желательно проводить в тех областях дерева, где отсечения могли бы произойти наиболее часто. Для этого используется ряд правил. Например, NMP рассматривается только для позиций со статической оценкой больше беты. Логика в том, что позиции уже имеющие высокую оценку, даже после пропуска хода в целом сохранят ее и с большей вероятностью отсекутся.
Но мы немного забежали вперед. Отложим вопросы программирования до тех пор, когда непосредственная реализация методов будет проиллюстрирована на примерах кода. А пока перейдем к LMR.
*****
Сокращение на поздних ходах (LMR) начало набирать популярность с середины 00-х, когда появились использующие его сильные программы с открытым исходным кодом — Фрукт и Глаурунг. В первую очередь благодаря LMR, с годами степень ветвления в дереве перебора программ постепенно сократилась с 3,5 до 2. В современных программах она опустилось ниже 1,5. Конечно помогают и другие методы, но все же LMR является определяющим в данном вопросе.
Аналогично тому как мы поступали ранее, укажем LMR на общем дереве перебора в дополнение к отсечениям альфа-бетой и нулевым ходом. Варианты пунктиром из Cut-nodes считаем отсеченными альфа-бетой. Поэтому для наглядности возможный LMR на них отображать не будем:
В отличие от нулевого хода LMR не отсекает ветку окончательно, а лишь сокращает глубину перебора на ней. Поэтому на ветке варианта возможно выполнять LMR по нескольку раз. То есть, если на схеме произошло сокращение глубины выше по дереву, то далее его можно произвести и ниже по дереву, если конечно позволяют условия. Отсечения нулевым ходом после LMR тоже возможны.
Если нулевой ход действительно отсекает 60% All-nodes, то на остальных All-nodes отсечений не происходит и при иных обстоятельствах на них пришлоcь бы считать все продолжения. В самом деле — альфа-бета здесь не работает, а отсечение нулевым ходом отклонено. Поэтому самым важным методом сокращения перебора на этих узлах становится LMR. Именно здесь происходит основное снижение ветвления. В то время как на Cut-nodes до LMR доходит лишь в третью очередь, то на All-nodes, не отсеченных нулевым ходом, LMR очень значимо сокращает величину перебора.
*****
Давайте подведем некоторые итоги. Как мы видим, на Cut-nodes отсечения происходят фактически сразу. На практике альфа-бета обычно отсекает здесь после рассмотрения первого или второго хода, конечно если ранее уже не произошло отсечение нулевым. В свою очередь, значительная часть All-nodes отсекается нулевым ходом, а на всех остальных All-nodes происходит резкое сокращение глубины вследствие использования LMR. Таким образом эти три метода дополняя друг друга, отсекают, отсекают и отсекают, доводя дерево перебора чуть ли не до голого ствола.
Но кроме трех основных, существуют так же и другие методы, которые в совокупности тоже вызывают очень даже немало отсечений. Некоторые из них мы рассмотрим в следующей части. Так же проясним кое-какие важные термины и коснемся иных вопросов.
Продолжение следует…
Предыдущие части цикла:
ссылка на оригинал статьи https://habr.com/ru/articles/1036214/