В этой части мы коснемся некоторых наиболее ходовых понятий, которые часто используются в терминологии компьютерных шахмат и без которых затруднительно конструктивное обсуждение вопросов перебора. Также рассмотрим некоторые второстепенные методы направленного перебора, которые тем не менее глубоко интегрированы в структуру поиска. И в концовке обсудим общий порядок обхода всего дерева перебора целиком.
Представленная здесь информация на первых порах может показаться не такой уж и важной, но если в дальнейшем планируется углубиться в код поиска реальных программ, то она поможет прояснить некоторые вопросы.
Наглядным пособием нам будет служить схема, которая приведена ниже. В ее основе лежит схема LMR из II части, но расширенная в глубину на один полуход и приведенная ближе к стандартам реальных программ. Перебор, как обычно, стартует с основного варианта (PV) по левой ветке, затем переходит на среднюю, где обычно происходят отсечения, и т. д.
В первую очередь следует прояснить, что означают альфа и бета. Альфа (alpha) — это «наша» лучшая оценка в какой-то из ранее просмотренных веток. То есть оценка нашего лучшего варианта, который у «нас» есть в наличии. В то же время это та оценка, к которой мы можем обратиться в случае, если текущая ветка, в которой мы ведем перебор, не оправдает наши ожидания из-за получения в ней низкой оценки. В таком случае мы всегда можем ее избежать, выбрав ветку, где получена альфа.
Бета (beta) — аналогичная оценка «для противника» полученная где-то выше и в другой ветке по дереву перебора. Все варианты с оценкой выше беты с нашей точки зрения «слишком хороши, чтобы быть правдой», поскольку соперник точно так же может их избежать, так как имеет возможность выбрать вариант по другой ветке с оценкой пониже. Именно потому варианты с оценкой выше беты отсекаются альфа-бета процедурой, методика которой подробно расписана во II части.
Здесь существует один важный нюанс, о котором уже упоминалось ранее. В реальных программах используется негамаксная процедура выбора хода, поскольку она проще для написания и вычислений. Она позволяет использовать унифицированную строку поиска независимо от глубины и отсекать всегда по превышению беты. Согласно нее, каждая позиция рассматривается с точки зрения того, чей ход в ней. То есть по мере углубления сторона «за нас» и «за противника» постоянно меняются местами. Иначе говоря, как бы мы ни углублялись по дереву, каждая следующая позиция всегда «за нас», а выше и ниже «за противника». Поскольку меняются местами стороны, то приходится менять местами и их оценки. Альфа становится бетой, а бета альфой. На следующем полуходе глубины они снова поменяются местами и т. д.
Если рассматривать каждую позицию с точки зрения того кто имеет право хода и отсекать всегда по превышению беты, то нужно учесть, что приоритеты сторон противоположны и они стремятся улучшить каждый свою оценку в разных направлениях шкалы оценок. Но при углублении, и соответственно смене сторон, необходимо сохранять принцип — чем больше оценка, тем лучше. Поэтому каждый раз при смене стороны нужно менять и знак оценки. Плюс становится минусом, а минус плюсом. При дальнейшем спуске по дереву знак снова изменится, и т. д.
Для примера, так выглядит заголовок функции основного поиска Стокфиша:
search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode)
А так, строка рекурсивного перебора в ней:
value = -search<PV>(pos, ss + 1, -beta, -alpha, newDepth, false);
При расчете на следующую глубину ветки, альфа заносится вместо беты, а бета вместо альфы. Обе оценки берутся с противоположным знаком. Когда же из перебора по данной ветке нам вернется оценка, ей необходимо возвратить правильный (то есть противоположный, -search) знак. Таким образом, знак оценки снова изменится. Конечно, пять инверсий на одну строку может немного сбивать с толку.
Для большей наглядности эти и другие изменения проиллюстрированы ниже на схеме. Схема по большей части заимствована из описания LMR во II части, но знак оценки изменяется соответственно правилам негамакса. Аналогично меняются местами и лучшие оценки каждой из сторон — альфа и бета.
Вначале, когда перебор начинает осуществляться по левой ветке, ни своих, ни оценок противника у нас еще нет. Поэтому альфа принимается равной наименее возможному значению, то есть минус бесконечности. Бета соперника соответственно будет приравнена к плюс бесконечности. Далее, по мере получения оценок позиций альфа («наша» оценка, или иначе говоря, оценка той стороны, чей ход в рассматриваемой позиции), будет повышаться, а бета понижаться. Каждое следующее улучшение оценки увеличивает альфу, а улучшение оценки у противника уменьшает бету.
Допустим, на схеме ниже после исследования варианта слева мы получили его оценку, +5. Это наша альфа. То есть альфа стороны, которая ходит из верхнего узла (позиции). Таким образом, альфа повышается от минус бесконечности до +5. Бета не изменилась, так как ход соперника пока неизвестен, поэтому бета по-прежнему приравнена к плюс бесконечности. Вариант временно становится нашим основным вариантом (PV), и он таковым останется, если только мы не найдем варианты с большей оценкой.
Переходим ко второму варианту, углубляемся на один полуход. Здесь мы смотрим на позицию с точки зрения соперника. Наша альфа стала для соперника бетой. Оценка, которая лучше для нас, хуже для него. Поэтому меняем знак оценки на противоположный. То есть прежняя альфа, теперь бета с переменой знака. Поскольку ни одного продолжения еще не оценено, то альфа в узле, тоже со сменой знака, пока минус бесконечность.
Чем ниже бета, тем чаще будут происходить отсечения. А поскольку отсечения это основной способ ограничения перебора, и соответственно роста силы игры, то низкое значение беты становится ключевым фактором.
Так как при углублении по дереву на один полуход альфа и бета меняются местами, т.е. альфа становится бетой, то повышение альфы не менее значимый фактор. Наконец, альфа ведь повышает «нашу» оценку позиции, что улучшает «наши» шансы на победу в партии.
После просмотра первого ответа, мы получаем лучший ход соперника, его альфу. Альфа узла поднимается от минус бесконечности до -7. В данном случае оценка лучшего хода в позиции и альфа равны, но так бывает далеко не всегда.
Далее смотрим второй ответ. На схеме он расширен в глубину. Кстати сказать, мы точно так же смотрели и ветку основного варианта, и первого ответа, просто для наглядности перебор в них на схеме не отображается.
Перейдя вниз по ветке второго ответа, мы аналогично меняем местами стороны, а значит альфу с бетой и знак оценки. Теперь альфа опять стала +5. В этой позиции по мере перебора альфа повышается с +5 до +6, но отсечения не происходит, поскольку оценка лучшего хода меньше беты (+7). Продолжая перебор, мы достигаем хода с оценкой +9. Поскольку эта оценка выше беты, то производим отсечение, не рассматривая остальные ходы. На уровень выше поднимаем оценку +9.
Не забываем менять знак, так как уровнем выше соперники поменялись местами. Таким образом оценка второго ответа равна -9. Она меньше оценки лучшего ответа (-7) на этой глубине и меньше альфы (-7), поэтому альфа не меняется. Далее переходим к изучению третьего ответа. Перебор продолжается аналогичным образом.
*****
Интервал в оценках между альфой и бетой называется «окно» (window). Как уже упоминалось выше, в начале перебора альфа и бета принимаются равными бесконечности. Но так как отсечения происходят по превышению беты, а та равна бесконечности, то поначалу отсечения идут не очень активно. Дерево перебора очень большое, движок тормозит — бесконечность вообще не превысить, а по получении первых оценок значение беты обычно все еще слишком высоко для частых отсечений.
Прежде чем бета понизится до значений близких к реальным, программа произведет много лишних вычислений, которых при иных обстоятельствах можно было бы избежать. Поэтому для ускорения в начале перебора используют метод Aspiration windows.
В этом случае оценки альфы и беты спекулятивно принимают близкими к более реально ожидаемым значениям. Отсечения пойдут намного быстрее. Но, в свою очередь, если при таком переборе границы будут превышены, то перебор придется проводить заново на полном интервале.
Тем не менее, спекулятивное уменьшение размера окна все равно выгоднее с точки зрения экономии расчетов. Изначально программа выбирает интервал исходя из предыдущего перебора, если таковой проводился. Современные программы при выходе за пределы окна просто немного расширяют или сдвигают спекулятивный интервал.
Таким образом, чем меньше разница между альфой и бетой, тем быстрее производятся отсечения. По мере перебора альфа и бета сближаются друг с другом. Если бы «окно» между ними было минимальным, то альфа-бета отсечения производились бы наиболее эффективно.
На этом основан метод Principal Variation Search (PVS). Мы можем использовать тот факт, что если первым ходом по сортировке отсечения не произошло, то для остальных ходов его скорее всего тоже не будет, если конечно сортировка корректна. Таким образом, в большинстве случаев оценка будет меньше альфы, а следовательно и беты. Мы можем провести перебор первого хода по сортировке с полным окном, а затем спекулятивно понизить значение беты до значения альфа+1 для второго и последующих ходов — окно станет минимальным и перебор ходов с номером по сортировке >1 пойдет быстрее. Если же какой-то из поздних ходов неожиданно превысит альфу, а значит и нашу недостоверную бету, тогда произведем его перерасчет с полным окном. Редкие повторные переборы при превышении альфы потребуют гораздо меньше расчетов.
В этом отношении метод PVS похож на LMR. Аналогично он производит упрощенный перебор ходов, которые почти наверняка не улучшат оценку, но потребуют много ресурсов для вычислений. PVS дает гораздо меньший эффект, чем LMR, поскольку лишь ускоряет альфа-бета отсечения. Но зато PVS не провоцирует некорректные отсечения. Его условно можно рассматривать как один из методов сортировки, но с предварительным перебором.
В другом отношении PVS выполняет ту же работу, что и Aspiration windows. Он так же спекулятивно манипулирует размером альфа-бета окна. Аналогично, по превышении альфы оценка становится недостоверной и происходит повторный перебор с полным окном. Но если Aspiration windows используется только в начале перебора, то PVS можно использовать повсеместно. Метод применяется практически при каждом вызове функции поиска (search) с номером хода >1.
Строка поиска с PVS, на ходах после первого по сортировке, выглядит примерно так:
value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, newDepth, !cutNode);
Как видим, окно здесь минимальное. Бете присвоено значение альфа+1.
Итак, при использовании PVS, первый ход по сортировке в каждой позиции дерева рассматривается с полным окном, а остальные с минимальным (нулевым).
Со временем PVS еще более усовершенствовали. Теперь полное окно в некоем поддереве используется только один раз — это происходит в «левой» линии из головной позиции поддерева, а все остальные ходы рассматриваются с минимальным окном. Но конечно по превышению альфы и повторном переборе узлы будут переоценены, и типы окон в ветках поддерева могут измениться.
С введением PVS оценка типов узлов тоже поменялась. В современных программах типы узлов определяются несколько иначе, чем по классической схеме. Например в Стокфише к PV-node приравнены все узлы, которые рассматриваются с полным окном, а не только цепочка узлов из корневой позиции. Так что PV-node здесь чуть ли не синоним полного окна. В свою очередь все узлы с минимальным окном относятся к типу NonPV, в составе которого чередуются Cut- и All-nodes. На All-nodes появляется бета, но это спекулятивная бета — в любом случае при превышении альфы, а значит и данной беты, будет произведен перерасчет с полным окном.
Здесь пожалуй стоит прерваться. Мы как-то слишком рано углубились в частные вопросы реализации PVS. За подробностями отсылаю на Chessprogramming wiki:
https://www.chessprogramming.org/Principal_Variation_Search
*****
Еще один способ ускорить программу носит в основном технический характер.
Немного неожиданно, но одним из самых ресурсоемких процессов в ходе перебора является банальная генерация ходов. То есть определения, какие в каждой позиции вообще существуют ходы, разрешенные правилами. Спускаясь по дереву в каждую новую позицию, программа в первую очередь должна найти в ней все ходы, чтобы запустить процесс сортировки. Но бОльшая часть возможных ходов в позиции в современных программах обычно отсекается. Тогда получается, что их генерация по большей части напрасна, так как они в основном даже не рассматриваются.
Решить эту проблему позволяет реализация генерации ходов «порционно» — это так называемая инкрементальная генерация ходов (Incremental move generator). Ходы генерируются частями, по ходу процесса сортировки. Сначала «выгодные взятия», затем киллеры и т. д. Но даже в современных программах генерация ходов по-прежнему отнимает немало ресурсов. Хотя, конечно, сейчас упор в вычислениях несколько сдвинулся в сторону нейросети и она в первую очередь становится «бутылочным горлышком» для скорости перебора.
Чтобы генератор ходов работал быстро, важно правильное представление шахматной доски в программе. Иначе говоря, записи позиции в таком виде, которая наиболее удобна для быстрой обработки компьютером. В настоящее время среди ведущих программ безраздельно господствует побитовое представление доски, называемое битбордами. Или точнее его модификация «Магические битборды» (Magic Bitboards).
Тип представления доски в программе очень важен для скорости и занимает значительную часть кода. Но поскольку эта часть программы носит больше технический характер, то ее описание выходит за пределы тематики данной статьи. Поэтому ограничусь только ссылками на статью о магических битбордах в wiki:
https://www.chessprogramming.org/Magic_Bitboards
и обзорную статью Владимира Медведева (WinPooh):
https://drive.google.com/file/d/10cM5-RwXatSpZxSZGAV6AhwjyTbnurRH/view
*****
Теперь, когда мы немного разобрались с организацией перебора в реальных программах, попробуем взглянуть на все дерево перебора целиком. В частности надо разрешить вопрос, в каком порядке обходить это самое дерево. Взглянем на схему ниже:
Обход дерева происходит следующим образом. Перебор начинается с корневого (верхнего) узла. Вследствие рекурсивного вызова функции программа сначала углубляется по ветке основного варианта до заданной глубины, где получает числовую оценку позиции с помощью QS и оценочной функции. На схеме эта ветка находится слева.
Потом программа исследует соседние с той позицией варианты (1). Затем она переходит в ветку с менее близким соседством, где исследует варианты (2) аналогичным образом. Конечно большая часть из этих вариантов отсекается. Далее программа через дерево переходит к еще менее близким вариантам (3) и т. д. Получается своеобразный каскад. Основной вариант берется из предыдущих вычислений, а если таковых нет, то подбирается оценочным или случайным образом.
Когда программа завершает обход всего дерева, перебор на заданную глубину считается законченным. При этом находится или подтверждается основной (лучший) вариант.
Затем программа повторяет процедуру. Из корневой позиции она снова спускается по основному варианту, продляет его на один полуход глубины и аналогично обходит все дерево. По сути перебор начинается заново — теперь программа снова обходит дерево по известным правилам, но с добавлением единицы глубины. Основной вариант, который суть цепочка лучших ходов по мнению программы, с предыдущего раза может измениться, но чаще всего он остается прежним.
Такой метод обхода дерева называется итеративным углублением (Iterative deepening). За каждую итерацию перебора глубина прирастает на один полуход. По веткам производятся еще различные дополнительные продления и сокращения, согласно некоторым правилам. Но в счете итеративной глубины они не учитываются, поэтому в современных программах реальная глубина ветки может существенно отличаться от номинальной (итеративной) глубины.
Может показаться, что такой метод не слишком эффективен, поскольку для достижения каждой следующей глубины программе нужно снова обойти все дерево. Но как ни парадоксально повторный обход дерева позволяет ускорить перебор.
На практике перебор происходит быстрее, чем если бы мы сразу считали на большую глубину. Заполняются таблицы перестановок, истории и т. д., и с каждой следующей итерацией производится намного, намного больше отсечений. Предыдущая итерация выполняет функции предварительного перебора, который кратно уменьшает величину перебора для следующей итерации.
Кроме того, перебор сразу на большую глубину может затянуться, поскольку нельзя заранее предсказать, в каких ветках будет много отсечений, а в каких нет. Такой перебор нельзя прерывать до окончания обхода дерева, иначе некоторые ветки останутся совсем без рассмотрения. Итеративное углубление позволяет решить эту проблему. Между итерациями перебор всегда можно прервать, а если нужно остановиться немедленно, то всегда можно взять результаты с предыдущей глубины. Это позволяет относительно гибко регулировать время отпущенное на ход, что важно в соревнованиях и тестах.
Еще одно преимущество заключается в экономии оперативной памяти, так как не нужно хранить в памяти все дерево целиком, поскольку мы его постоянно переобходим. Достаточно ограничится только цепочкой ходов основного варианта, чтобы программа знала с какого варианта начинать углубление каждый следующий раз, а далее варианты просматриваются по известным правилам. Если в процессе перебора основной вариант изменился, то старый отбрасывается и запоминается новый. Его и будем использовать при начале перебора на следующей глубине. Такой способ обхода дерева называется Depth-First.
Этот подход был особенно ценен при разработке ранних шахматных программ, когда каждый байт памяти был на счету. Но это важно и сейчас, когда деревья перебора выросли до огромных размеров. Поэтому такой способ обхода дерева используют все движки на классической базе. Конечно некоторое количество позиций хранится в хеш-таблицах, но их число очень ограничено, кроме того, каждая позиция хранится по отдельности и они не образуют единого дерева.
Напротив, обход дерева методом Монте-Карло (MCTS), который применяла Альфа Зеро, относится к подходу Best-First, где решение о том, какой вариант углубить в первую очередь, принимается после окончания предыдущего углубления. Выбор производится по оценке и некоторой статистике, которая обновляется после подведения итогов предыдущего углубления и потому следующий пролонгируемый ход нельзя знать заранее. Поскольку мы не знаем, какую цепочку ходов будем продлять дальше, то для этого требуется хранить все дерево перебора в памяти целиком. Все его позиции и связи между ними.
При таком подходе оперативная память быстро заканчивается, и потому не позволяет хранить большие деревья позиций. Соответственно для скоростных движков на классической базе (и их больших деревьев) этот метод практически бесполезен. При необходимости выделить даже всего несколько байт на позицию, десятки миллионов позиций в секунду при переборе быстро приведут к исчерпанию памяти компьютера.
И еще один момент. В описании выше мы неявно предполагали, что по достижении заданной глубины перебор прерывается и вызывается оценочная функция. Но на самом деле сначала вызывается функция форсированного варианта Quiescence Search (QS) и только потом производится оценка позиции. Обоснования такого подхода мы коснулись в концовке I части.
Хотя по своей сути QS и относится скорее к продлениям, оценку которую он возвращает, традиционно принято считать динамической оценкой позиции. Поэтому, кроме специальных случаев, далее так же будем поступать и мы.
*****
На этом мы закончим с общим обзором поиска по дереву вариантов, который начался еще в I части. В VI и VII частях мы снова вернемся к нему, обратившись к конкретной реализации перебора на примере кода программы Стокфиш. Пока же я могу предложить вам самостоятельно посмотреть код программ попроще.
Ниже я дам ссылку на ряд версий программы разработанной Игорем Коршуновым (WildCat), которые он выкладывал в свое время на форуме Иммортала. В архиве находятся версии за весь цикл разработки, от программы действительно полного перебора, до версии уровня намного сильнее чемпиона мира. Все ранее рассмотренные методы в наиболее продвинутой версии присутствуют. Есть и кое-что еще.
Поскольку Игорь приложил к коду проекты для VisualC++, то с кодом может повозиться даже человек не умеющий программировать. По крайней мере с оценочной функцией (файлы Eval) или с поиском (файлы Search).
https://drive.google.com/file/d/1R0hBvoVtWkXN8DTXnl5ROpZL3cd1iok0/view
В архиве есть не только код, но и исполняемые файлы. Для визуализации ходов потребуется графическая оболочка (GUI), простейшую из которых я тоже положил в архив. Связь между GUI и движком осуществляется по UCI-протоколу, но вам знать его не обязательно. Надо только указать в оболочке путь к файлу программы.
https://drive.google.com/file/d/1CHshNGVDWAOaKjhtngSHZ_8XjsINiWLY/view
Общую информацию по более продвинутым оболочкам можно получить на вики страницы разработки Стокфиша на гитхабе:
https://github.com/official-stockfish/Stockfish/wiki/Download-and-usage#download-a-chess-gui
Наиболее популярными и универсальными среди них являются бесплатная Arena и коммерческий Fritz (от ChessBase). Для тестирования и игры программ между собой лучше подходят простая CuteChess или более продвинутая Banksia. Там же на гитхабе Стокфиша можно найти и некоторые наборы стартовых позиций, чтобы разнообразить начала партий:
https://github.com/official-stockfish/books
Всякая интересная информация по ссылке:
https://github.com/official-stockfish/Stockfish/wiki/Useful-data
Ну а мы пока перейдем к разбору типичной оценочной функции.
Продолжение следует…
Предыдущие части цикла:
ссылка на оригинал статьи https://habr.com/ru/articles/1037564/