В этой части мы наконец-то обратимся к коду реальных программ. Примером нам будет служить код поиска шахматной программы Стокфиш. В настоящее время это безусловно сильнейшая шахматная программа в мире.
Начиная с этой части, мне придется обратиться к области, которую я не знаю в достаточной степени. Все-таки, не будучи программистом обсуждать код программ довольно рискованно. Но по-видимому без этого не обойтись. Все описания выше должны быть проиллюстрированы текстами какой-либо сильной программы.
Начать наверное стоит с пояснения - то что обычно называется шахматной программой, или иначе "движком", на самом деле запускается из консоли. К пользователю программа обращается через графическую оболочку - GUI. Графическая оболочка сама по себе в шахматы не играет. Она только отрисовывает доску и отображает ходы, которые посылает ей движок. Также она предоставляет всевозможные сервисные функции, запускает различные виды анализа, позволяет работать с базами партий. Через нее подключаются дебютные книги и наборы стартовых позиций, эндшпильные базы и т. д. Ссылка на страницу с описанием популярных графических оболочек была дана в конце IV части.
Оболочка общается с движком через UCI-протокол. Это набор стандартизованных команд, который понимают обе программы. Сейчас UCI это общепринятый стандарт шахматных протоколов, хотя существуют и другие, например WinBoard. Одна оболочка может руководить не одним движком, а запустить, например, несколько шахматных программ одновременно для анализа, устраивать между ними турниры и т. д.
Краткий гайд по основным командам UCI и настройкам Стокфиша можно найти здесь:
https://github.com/official-stockfish/Stockfish/wiki/UCI-&-Commands
https://drive.google.com/file/d/1_1Vd52xvGOJYPs1y_f15lGlkauErOR02/view
Исходные тексты программы Стокфиш можно найти на ее официальной страничке на гитхабе. Не так давно вышла 18-я версия этого движка. На ее код мы и будем ориентироваться:
https://github.com/official-stockfish/Stockfish/tree/cb3d4ee9b47d0c5aae855b12379378ea1439675c
В данном обзоре мы будем в основном рассматривать поиск по дереву вариантов, т.е. перебор. Поэтому файл с которым придется работать это search.cpp. К нему мы будем обращаться по умолчанию.
Код поиска, это основа с которой стартует содержательная часть программы. Фактически можно сказать, что отсюда стартует сама шахматная программа.
Здесь запускаются все виды перебора. Отсюда идет обращение к оценочной функции и другим частям кода. Когда поиск (search) заканчивает перебор, достигая заданной глубины (depth уменьшается до 0), а затем проведет форсированный перебор, он обращается к оценочной функции в файле evaluate.cpp, из под которого уже идет обращение к нейросети. Весь связанный с нейросетью код храниться в папке nnue.
*****
Но прежде, чем мы перейдем непосредственно к структуре программы, необходимо коснутся использования термина глубины (depth) в шахматных программах. В движках обычно используется несколько параметров для ее отсчета. Эти параметры используются для разных целей и нередко возникают проблемы с пониманием их работы.
В первую очередь, глубина может отсчитываться как бы с разной стороны дерева. При текущем переборе определенной ветки, параметр глубины (depth) отсчитывается в сторону уменьшения от параметра заданного функцией перебора (search). При depth = 0 по условию включается Quiescence Search (см. окончание части I). Таким образом, глубина считается как бы в обратную сторону - максимальное значение у нее в "корне" функции, и далее она уменьшается в направлении конца ветки. Таким образом, говоря о "углублении" в дерево перебора, мы можем быть немного дезориентированы уменьшением при этом параметра depth.
В свою очередь есть параметры глубины, которые используются более интуитивно - с возрастанием от корня к конечным (их еще называют листовыми, листьями) позициям. Так, например в Стокфише есть такой параметр как rootDepth, который используется при запуске итеративного цикла из корня. Есть еще selDepth, который учитывает глубину продлений вдобавок к итеративной, а также ply - они в общем-то похожи, у них только немного разная точка отсчета.
*****
Поиск Стокфиша можно рассматривать как некий каскад из четырех частей - функций. Перебор начинается с запуска функции start_searching. В процессе исполнения она запускает функцию итеративного углубления (iterative_deepening). Та запускает основную функцию поиска (search), из которой в свою очередь поиск продляется форсированными вариантами (функция qsearch). Все функции находятся в файле search.cpp. Рассмотрим их по порядку.
1. Начало перебора
Графическая оболочка сначала инициализирует движок, отправляя ему команду uci, а следом шлет настройки, которые выставил пользователь.
Старт общего перебора запускается из строки:
183 start_searching()
Здесь производится запуск главного и всех остальных потоков, раздача заданий каждому из них, сравнение результатов и их останов. То есть под данным заголовком по большей части идет распараллеливание.
Первым стартует основной поток (Main thread) и он уже запускает остальные. Все потоки запускаются в количестве указанном в настройках. Под start_searching в файле search.cpp находятся только команды вызова функций. Сами функции можно посмотреть в файлах thread.
Потоки запускаются сначала на холостом ходу (idle_loop), не производя никакой работы и не загружая процессор. Только когда движок получает от оболочки команду go, вместе с текстом партии или позицией, потоки выходят из спящего режима и начинается перебор вариантов через функцию start_thinking (не путать со start_searching).
Потоки практически независимы друг от друга и оперативно обмениваются результатами через хеш-таблицы, общие для всех потоков. Использование общих хеш-таблиц не только помогает потокам выбирать лучший ход пользуясь результатами параллельных поисков, но также уменьшает дублирование перебора, хотя и не в полной мере. Почти все остальные таблицы, и в первую очередь таблицы истории, у каждого потока свои. То есть за исключением хеш-таблиц, в каждом потоке таблицы с разными данными. Это ключевой источник вариативности перебора.
Несинхронизированная запись потоками в хеш-таблицы позволяет делать поиск недетерминированным. Накапливающиеся расхождения записей в таблицах истории у потоков приводят к различию их деревьев перебора, что в свою очередь позволяет находить "потерянные" варианты отдельными потоками. Иначе говоря, хеш-таблицы обеспечивают обмен информацией между потоками, а таблицы истории обеспечивают вариативность. Это изрядно усиливает перебор и эффективно масштабирует его на любое количество ядер процессора.
С недавнего времени у Стокфиша стали общими не только хеш-таблицы, но и некоторые другие. Ниже по тексту мы еще вернемся к вопросам распараллеливания.
Точек синхронизации у потоков нет. По окончании перебора производится "голосование" за лучший поток:
237 bestThread = threads.get_best_thread()->worker.get()
Из под start_searching запускается функция перебора каждого из потоков по отдельности:
190 iterative_deepening()
2. Итеративное углубление
Функция итеративного углубления запускает перебор на каждом потоке со строки:
259 iterative_deepening()
Это старт перебора одного потока. Итеративный цикл запускается со строки:
322 while (++rootDepth < MAX_PLY && !threads.stop && !(limits.depth && mainThread && rootDepth > limits.depth))
Функция запускается в корневой позиции и увеличивает глубину rootDepth на один полуход за цикл, до тех пор, пока не достигнет конечного значения. Но чаще всего прерывание вызывается окончанием времени, выделенного на ход. Выделяемое время гибко регулируется с помощью специальных правил, отталкиваясь от заданного пользователем в оболочке "тарифного плана". Возможен также перебор на фиксированную глубину.
В начале перебора из корня производится спекулятивный выбор размера альфа-бета окна с помощью метода Aspiration windows (см. IV часть). При выходе функции search за пределы спекулятивных границ, значение оценки признается недостоверным (хотя и отображается на экране). После этого границы определяемые значениями альфы и беты немного расширяются или сдвигаются и производится повторный перебор на ту же глубину. До тех пор пока происходит выход за границы, цикл/перебор повторяется. Если количество повторов становится чрезмерным, глубина может быть даже временно снижена.
Многократно фигурирующий в функции параметр MultiPV - это запуск перебора в несколько линий. В целом он ослабляет программу и нужен для ручного анализа или запуска в режиме уменьшения силы игры. В полноценной партии для выбора хода он не используется. По умолчанию будем считать его всегда равным единице.
Под каждым циклом итеративного углубления запускается перебор на заданную глубину вызовом функции search:
375 bestValue = search<Root>(rootPos, ss, alpha, beta, adjustedDepth, false)
3. Основной перебор
В каждом цикле итеративного перебора запускается функция перебора на заданную глубину со строки:
615 search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode)
search - это основная функция поиска. Альфа и омега всего перебора. Источник силы всей программы. Если собираетесь проникнуть в самую ее суть, то обращайтесь сюда. В первую очередь к шагам (Step) с 7-го по 20-й, где сосредоточена основная логика выбора направления перебора - продлений, сокращений, отсечений и всего остального, о чем мы говорили во II части.
Эта функция слишком большая, чтобы ограничиться ее кратким обзором. Мы посвятим ей целиком следующую часть статьи.
Как только перебор функции search по какой-либо из веток достигает заданной глубины, то запускается форсированный вариант поиска:
622 // Dive into quiescence search when the depth reaches zero 623 if (depth <= 0) 624 return qsearch<PvNode ? PV : NonPV>(pos, ss, alpha, beta);
4. Форсированный перебор
Когда основной перебор в какой-либо ветке достигает определенной (заданной) глубины (depth = 0), он запускает перебор форсированных ходов - Quiescence Search:
1496 qsearch(Position& pos, Stack* ss, Value alpha, Value beta)
Далее в глубь допускается смотреть только взятия и отчасти шахи. Обоснование необходимости метода смотрите в концовке I части статьи.
Quiescence Search во многом похож на упрощенную версию основного поиска. Он повторяет многие методы, но расчет идет не до заданной глубины, а до исчерпания разменов. Есть в QS и оригинальные методы отсечений. Например, так называемый Stand pat:
1581 else 1582 { 1583 unadjustedStaticEval = evaluate(pos); 1584 ss->staticEval = bestValue = 1585 to_corrected_static_eval(unadjustedStaticEval, correctionValue); 1586 } 1588 // Stand pat. Return immediately if static value is at least beta 1589 if (bestValue >= beta) 1590 { 1591 if (!is_decisive(bestValue)) 1592 bestValue = (bestValue + beta) / 2; ... ... 1598 return bestValue; 1599 } 1601 if (bestValue > alpha) 1602 alpha = bestValue;
Здесь мы сначала вычисляем статическую оценку позиции и если она выше беты, то не считаем размены, а сразу производим отсечение и выходим из QS. Таким образом на ветке можно сберечь некоторое количество ресурсов компьютера, не считая бесполезные взятия.
Идея в том, что если бы даже с последующими разменами оценка и опустилась ниже беты, то мы можем отказаться от разменов, так как в шахматах рубка не обязательна, и выбрать тихий ход. Кроме того, поскольку оценка в позиции рассматривается с точки зрения стороны, чей сейчас ход, то этот ход почти наверняка не опустит нам оценку. Поэтому оценка должна превысить бету и отсечение состоится.
5. Оценка позиции
Когда и в Quiescence Search достигается предельная глубина, то есть окончание разменов, запускается определение оценки позиции, например из строки:
1583 evaluate(pos)
Это так называемая статическая оценка позиции, вычисляемая на основании только количества и взаимного расположения фигур на доске, без их передвижения. Здесь происходит обращение к файлу evaluate.cpp. Из него идет выход на оценочную функцию в виде нейросети через папку nnue.
Нейросетей используется две - основная и крошечная вспомогательная. Вспомогательная сеть предназначена для частных случаев с большой оценкой - такие позиции обычно не требуют качественной оценки, их выгоднее оценивать побыстрее.
(P.S. Совсем недавно малая вспомогательная сеть была все же удалена из Стокфиша.)
*****
Под конец хотелось бы еще раз коснуться вопросов распараллеливания. В настоящее время, когда количество ядер у центральных процессоров растет опережающими темпами, эта тема становится особенно актуальной.
Современные шахматные программы на классической базе используют для расчетов только мощности CPU, в том числе вектора для расчета матриц нейросетей. Видеокарты (GPU) для вычисления нейросеток не получается задействовать из-за очень большой задержки по передаче данных туда-обратно, что понизило бы скорость перебора в тысячи раз.
Напротив, для огромных сетей Лилы (Leela Chess Zero, Lc0) и прочих программ, созданных на базе Альфа Зеро, этот вопрос не актуален, поскольку у них скорость и так невелика. Но у таких программ тоже есть свои проблемы. Здесь в свою очередь простаивает центральный процессор, так как у него не очень много работы, вследствие того, что большие нейросетки требуют много времени на вычисления даже на видеокартах. А MCTS последовательный процесс, который должен получить с видеокарты оценки для предыдущего пакета позиций, прежде чем апгрейдить дерево перебора и собрать новый пакет.
Вопрос распараллеливания шахматных программ поднимался еще очень давно. Уже в конце 70-х пытались наладить работу программ на нескольких машинах вместе. Но долгое время он представлял больше академический интерес, за редким исключением в виде программ для Крей Блиц, Дип Блю и некоторых иных машин. Но с постепенным распространением многоядерных машин, проникновением их на потребительский рынок шахматных программ в начале 00-х, вопрос все больше переходил в практическую плоскость. В современном мире, когда количество ядер на процессорах все время растет - и часто это чуть ли не единственная метрика прогресса машин, тема распараллеливания стала такой же важной, как и прочие методы совершенствования шахматных программ.
Проблема с самого начала стояла исключительно остро, поскольку базовый метод обхода дерева на основе альфа-бета отсечений имеет последовательную природу. Выбор каждой следующей ветки для рассмотрения перебором, это результат отсечения (или не отсечения) предыдущей - куда направится перебор предсказать заранее нельзя.
При всем разнообразии изначальных схем распараллеливания, основная мысль повернула в направлении раздавать параллельным процессорам/ядрам/потокам те ветки дерева, которые будут вычисляться в любом случае. Примерно к концу 00-х на первое место по популярности вышел метод YBWC. Лежащий в его основе принцип распараллеливания заключался в том, что если первым ходом по сортировке отсечения не произошло, то и дальше его скорее всего не произойдет и остальные ходы по сортировке раздаются всем свободным потокам.
Очевидно, что большинство таких вариантов будут раздаваться из All-nodes. Предполагалось, что на подветках таких вариантов найдется работа для всех потоков. Но как оказалось, на системах с более чем 16 ядрами, потоки большей частью простаивали ожидая новых заданий и положительный эффект от распараллеливания сводился практически к нулю.
Если же делать потоки более независимыми, то "поднимает голову" избыточный перебор, то есть повторный перебор одних тех же веток несколькими потоками, или же напрасный перебор одними потоками веток, уже отсеченными другими потоками.
Более продвинутым с точки зрения эффективной загрузки потоков в те годы считался метод DTS, но он был настолько сложен в реализации, что его мало кто использовал. Со все большим распространением систем ПК с двузначным числом ядер, вопрос распараллеливания снова подвис в воздухе.
К счастью, около 2014 года был найден метод, который разрешил все проблемы. Он получил название LazySMP, но по сути оказался реинкарнацией старых методов с общим хешем.
Идея была известна уже давно. Нужно было пустить все потоки в "свободное плавание", сделав их абсолютно независимыми, без процессов синхронизации, а обмениваться информацией они должны только через общую для всех потоков хеш-таблицу. Все остальные таблицы (в первую очередь History) будут свои для каждого потока, и вследствие общей недетерминированности расчетов на каждом потоке, создадут естественную вариативность. Желательно было только принять дополнительные меры, чтобы потоки еще больше расходились по разным веткам естественным путем.
Но все равно получалось так, что избыточный - суть повторный перебор, у разных потоков зашкаливал. Поэтому ранее на системах с более чем двумя потоками такие методы эффективно не работали. А сейчас вдруг заработали…
Неожиданно системы с десятками и даже сотнями ядер стали увеличивать силу игры кратно их числу. По эффективности прибавки кратное увеличение числа ядер стало приближаться к эффективности аналогичного увеличения времени на обдумывание. Ясно было, что закон Амдала, накладывающий ограничения на эффективность параллельных систем удалось как-то обойти. Но как?
Достаточно быстро пришло понимание, что виной тому отсечения с потерями. Отсечения на побочных ветках имеют тот эффект, что часть важных ходов теряется. Очень селективный современный перебор иногда слишком уж отсекает побочные ветки, пусть и с положительным общим эффектом для силы движка. В свою очередь "расширяя" перебор, иногда можно их найти.
Даже при большой надежности методов отсечения, "поле" отсекаемых ходов слишком велико и количество преждевременно отсеченных вариантов в совокупности должно быть очень большим. В свою очередь в шахматах одна-две серьезные ошибки обычно решают партию. Поэтому отыскание таких "потерянных PV" является важным элементом шахматного поиска. Отсюда следует, что нахождение даже небольшого количества этих ходов может с лихвой скомпенсировать и солидные потери на распараллеливание, выраженные избыточным перебором.
Раньше, когда преимущественно использовались отсечения альфа-бетой, которая как известно отсекает без потерь, методы с общим хешем естественно не могли быть эффективными, так как искать на этом "поле" отсеченных вариантов было нечего.
Пока что описания конкретных механизмов отыскания ходов-кандидатов в преждевременно отсеченных ветках мне встречать не приходилось. Рискну взять на себя такую ответственность и предложить один из возможных вариантов. Но конечно все рассуждения ниже еще требуют своего подтверждения.
Начнем с того, что при обходе дерева, ошибки перебора обычно случаются, если тот не может досчитаться до глубины достаточной, чтобы увидеть последствия своих действий. То есть его вариантам недостает глубины. Если бы перебор мог просчитать все ветки дерева до конца партии, до конечного ее результата (их всего три - победа, ничья или поражение), то он бы не допускал ошибок и всегда выбирал бы лучший ход. Но поскольку дерево шахмат слишком велико, то часть веток приходится сокращать.
Таким образом - пусть эта граница и достаточно размыта, ветви перебора можно разделить на два вида. Одни из них, это варианты близкие к основному. Они считаются на полную (заданную) или почти полную глубину. Им может недоставать глубины из-за недостатка времени и скорости железа.
На побочных ветках основной ограничитель глубины, это отсечения и сокращения. От времени на обдумывание и скорости такие ветки получают гораздо меньше пользы, поскольку их глубина растет кратно медленнее. Следовательно, им нужны другие источники усиления.
Более селективный перебор, в понимании "сужения" дерева в результате отсечений, помогает увеличить глубину основных вариантов. Напротив, на пользу побочным вариантам идет "расширение" перебора, но это ослабляет программу в целом. Получается "конфликт интересов" обоих способов. Исторически, перебор почти всегда улучшался увеличением его селективности путем "сужения" дерева.
Старые методы распараллеливания перебора в основном помогали уменьшить время набора глубины, то есть помогали в первую очередь основным, а не побочным веткам. Современный метод распараллеливания LazySMP, тоже отчасти позволяет ускорить основной перебор через общую хеш-таблицу, но главная польза от него происходит на побочных вариантах. LazySMP помогает находить на таких ветках ходы-кандидаты в преждевременно отсеченных вариантах.
Как указано выше, таблицы истории (Histоry) у каждого потока свои. Вследствие естественной недетерминированности и отсутствия синхронизации потоков эти таблицы могут заполняться по разному на разных потоках. Значит одни и те же ходы в одних и тех же позициях на каждом потоке могут исследоваться на различную глубину, вследствие вариативности происходящей от сортировки для LMR каждого потока.
Как следует из эффективности тех же киллеров, на одной ветке может произойти сразу целая серия отсечений в группе похожих позиций и какие-то ходы могут резко подняться в таблице истории у отдельного потока. Отсюда, на этом потоке они будут исследоваться по LMR на гораздо большую глубину, чем на остальных. Значит такие продолжения получат более пристальное внимание, могут поднять альфу, а впоследствии еще и пройти верификацию повторным перебором уже на полную глубину. И тогда мы получим "потерянную альфу" - по сути ход-кандидат и в перспективе "потерянный основной вариант" для этого потока, а позже и для всех остальных. Таким образом, без слишком большого избыточного перебора и расширения дерева, из побочных ветвей могут извлекаться преждевременно отсеченные варианты, которые в состоянии перевернуть оценку.
*****
На этом прервемся. В следующей части мы подробно рассмотрим основной перебор, вызываемый функцией search.
Продолжение следует...
