В этой части мы рассмотрим вторую важную составляющую шахматных программ - оценочную функцию. Долгие годы она находилась в роли "пасынка" для процесса разработки. Но на то существовали объективные причины.
После того как в первые десятилетия истории компьютерных шахмат программисты реализовали в оценочной функции простейшие и легко вычисляемые признаки позиции, дальнейшие улучшения столкнулись с трудностями. Даже периодически приглашаемые шахматисты самой высокой квалификации оказались бессильны помочь. Несмотря на многократные попытки, они не смогли предложить какие-либо важные признаки позиции, которые давали бы больше пользы, чем требовали вычислений.
Используемая программами "рукописная" оценочная функция на основе выделенных параметров состояла из материальной и позиционной составляющей. Первая заключается в подсчете количества фигур на доске, своих и соперника. Вторая учитывает их взаимное расположение.
С годами уровень оценочной функции все же постепенно возрастал. Понемногу увеличивалось количество определяемых признаков позиции. Оценка была разбита на две части - миттельшпильную и эндшпильную, которые смешивались пропорционально перехода позиции в партии от одной стадии к другой. Были найдены методы автоматического тюнинга "весов" параметров, путем наигрывания большого количества партий программы с самой собой. Но все равно улучшения были плавными и относительно небольшими.
Уровень оценки резко подрос в недавние годы с появлением нейросети NNUE, которая заменила "ручную" оценочную функцию. Новая структура оценки была заимствована из японской игры сеги, где разработчики программ наткнулись на идею принципиально иной архитектуры на базе нейросети, тонко адаптированной к текущим возможностям программ и железа.
Тем не менее и в настоящее время, в основном из-за аппаратных ограничений, не удается задействовать все вычислительные ресурсы доступные программам, а значит и все возможности нейросетей. В частности, по-прежнему нельзя производить вычисления на видеокартах. Поэтому уровень оценочной функции все еще остается недостаточным. Но это в свою очередь оставляет огромный запас для дальнейших улучшений, все предпосылки для которого уже существуют. Есть вычислительные мощности, известны лучшие архитектуры сетей и методы их обучения. Если только ключевые препятствия будут сняты, сила оценочной функции может возрасти многократно.
*****
Начнем мы с краткого обзора классической "ручной" функции оценки. В наше время многие программисты, начиная писать свой движок с нуля, все еще предпочитают ставить ее в качестве "заглушки", занимаясь в первую очередь написанием и отладкой базовой части программы с битбордами, генератором ходов и классическим поиском.
Как уже сказано выше, оценочная функция состоит из материальной и позиционной составляющей. В материальной части каждой фигуре присутствующей на доске назначена определенная цена, выраженная обычно в сантипешках. Разница ценности фигур своих и соперника дает материальную оценку.
При подсчете позиционных факторов наиболее важными являются таблицы ценности полей (Piece-Square Tables, PST, PSQ, PSQT). Они назначают бонус или штраф к цене фигуры в зависимости от ее положения. Для примера, конь на краю доски получает минус к оценке позиции. В простейших программах PST, это обычно несколько таблиц, с коэффициентами на определенных координатах, для каждого типа фигуры.
Другие значимые факторы, которые считает ручная оценочная функция, это обычно защита короля, различные виды оценок для пешечной структуры - проходные, сдвоенные, изолированные пешки и т. д. Программа определяет так же открытые линии для ладей, мобильность слонов (количеством доступных им полей). Кроме того учитываются очередность хода, пара слонов и. т. д. В более продвинутых версиях оценки могут вводиться нелинейные корректировки для дисбалансного материального соотношения. Каким образом учитываются эти факторы, можно посмотреть в старых программах, в том числе той, которая рекомендуется в конце IV части.
Реализацию классической оценочной функции в предыдущих версиях Стокфиша можно посмотреть на странице:
https://hxim.github.io/Stockfish-Evaluation-Guide/
Как мы видим, оценка в ней состояла из двух частей, соответствующих стадиям середины и конца партии. Вклад каждой стадии в общую оценку вносился пропорционально, в зависимости от количества материала оставшегося на доске. По мере перехода от миттельшпиля к эндшпилю "вес" первой составляющей в общей оценке постепенно уменьшался, а второй соответственно возрастал. Оценка каждой стадии вычислялась путем суммирования примерно десятка отдельно вычисляемых позиционных факторов, в основном тех, что указаны выше.
Оценочная функция тюнинговалась вручную или с помощью метода SPSA (Simultaneous Perturbation Stochastic Approximation), путем проведения множества партий программы с самой собой и постепенного подтягивания весов каждого параметра к оптимальным значениям. Для оптимизации параметров поиска этот метод используется и сейчас.
*****
В настоящее время во всех ведущих программах на классической базе для оценки позиции используется нейросеть на основе оригинальной архитектуры NNUE. Ее впервые предложили японские разработчики. Изначально она применялась для программ игры сеги и представляла собой линейную функцию из одного гигантского слоя. Позднее авторы программ сеги добавили на его выходе нелинейные преобразования и пару небольших дополнительных полносвязных слоев, поверх первого, что превратило эту систему в нейросеть. После сокращения размерности первого слоя, в таком виде она перекочевала в обычные шахматные программы летом 2020 года.
Эта архитектура превосходно адаптирована к вычислениям на современных CPU. К сожалению, программы на классической базе не в состоянии использовать гораздо большие мощности GPU. Как уже упоминалось ранее, этому скорее всего препятствует слишком большая задержка при передаче данных между центральным процессором и видеокартой.
Первоначально архитектура шахматной нейросети NNUE, заимствованная из сеги, выглядела так, как показано на изображении ниже.
Такая нейросеть имеет достаточно простую структуру. Она состоит всего из четырех полносвязных слоев, три из которых очень невелики. На вход сети слева подается позиция, которую требуется оценить, и после преобразований на каждом слое на выходе справа мы получаем ее оценку, которую можно использовать в программе.
На схеме вход нейросети изображен в виде круглых ячеек слева. В них заносится позиция, сообразно с расположением фигур на доске. Упрощенно говоря, единицы соответствуют наличию, а нули отсутствию фигур по соответствующим координатам.
Далее единицы и нули со входа перемножаются на линиях на коэффициенты (веса) нейросети, а результаты суммируются по сходящимся направлениям во втором столбце ячеек. Каждой линии соответствует одно число нейросети. Таким образом из 80 тысяч ячеек с закодированной позицией слева мы получаем группу вычисленных параметров в 512 ячейках справа. Соединяющая их группа линий представляет собой входной слой нейросети.
После небольшого преобразования чисел во втором столбце ячеек, мы аналогичным образом производим вычисления на линиях следующего слоя нейросети и на выходе из него получаем 32 числа в третьем столбце ячеек (из 512 во втором). Этот слой называется первым скрытым слоем.
Аналогичным образом производятся вычисления во втором скрытом слое - из 32 чисел в третьем столбце мы получаем 32 числа в четвертом.
На выходном (четвертом по счету) слое все 32 числа аналогичным образом сводятся в единую оценку. На схеме она обозначена круглой ячейкой справа. После небольшого преобразования этого числа мы получаем "готовую к употреблению" оценку позиции. Эта оценка идет в дерево перебора, где применяется, как результат вычислений функции оценки позиции - evaluate(pos). О том, каким образом она используется в процессе поиска по дереву вариантов, рассказывается в предыдущих и следующих частях статьи.
*****
Успеху NNUE способствовала очень тщательная адаптация к архитектуре современных CPU. Для того чтобы подобные сети работали быстро требуется использовать специальные технические решения. NNUE "играет" на некоторых нюансах в отношении тонкостей кодирования и преобразования данных, которые предоставляют значительные преимущества и экономят вычислительные ресурсы для данной архитектуры.
Большая часть оптимизаций NNUE сосредоточена на входном слое. Давайте на базе приведенной выше схемы рассмотрим подробнее, как они приносят выгоду нейросети такого формата.
В нейросеть архитектуры NNUE позиция подается на вход (на схеме с левой стороны) не так, как это обычно принято. В отличие от записи позиции стандартной строкой FEN, здесь напротив ценится не компактность, а разреженность.
Ячейки на входе, в которые заносится позиция, представлены для всех возможных сочетаний координат и типов фигур. В упрощенном представлении, для каждого из шести типов фигур двух цветов существует по 64 возможных расстановки на доске. То есть, для всех возможных положений фигур всего будет 2х6х64 = 768 ячеек. Единица в каждой из них будет свидетельствовать, что данная фигура находиться на данном поле, а ноль, что отсутствует.
В реальной сети NNUE идут еще дальше. Здесь ячейки свидетельствует о наличии по определенным координатам двух фигур - короля одного из цветов и какой-то другой фигуры, любого цвета. То есть каждая ячейка является "именной" и привязана к определенной координате и типу фигур. Таким образом, когда на входе позиция заносится в ячейки, всего доступно (2х64) х (5х2х64) = 80 000 ячеек - для двух королей, при 64-х возможных координат позиции короля на доске, и 5 типов других фигур, черных и белых, с 64 возможными положениями на доске каждой.
В ячейку проставляется единица, только если обе фигуры находятся на координатах ячейки. Например (см. на схеме) если в позиции черный король находится на поле e8, а ферзь на поле d8, то в ячейке будет единица, а все ячейки для иных их расположений, где хотя бы одна из фигур отсутствует, заполняются нулями. Такое бинарное (0 или 1) представление позиции на входных ячейках имеет свои преимущества, о чем будет рассказано ниже.
На входном слое расчеты производятся по двум путям. Каждый из них вычисляется раздельно - один путь предназначен для связей черного короля относительно других фигур любого цвета (на схеме он расположен выше), а второй путь аналогично вычисляется для белого короля.
Понятно, что в большинстве входных ячеек находятся нули, поскольку либо одна, либо вторая фигура по координатам ячейки отсутствуют. Король и фигура находятся вместе для каждого возможного сочетания координат в очень редких случаях. По факту заполняются единицами максимум 2х30 входных ячеек - это наиболее возможное количество фигур на доске по обоим путям, за вычетом королей. Таким образом, количество "единичных" сочетаний король-фигура будет равно количеству фигур на доске.
Соответственно, при таком способе ввода позиции, подавляющее большинство связей (линий) на входном слое не используются, так как на них должны происходить перемножения на ноль, с очевидным итогом. Поскольку конечный результат таких "умножений" заведомо нулевой, то к сумме результатов во втором столбце ячеек они ничего не добавят. Поэтому такие входные ячейки вычисляться не будут.
У подобного разреженного представления есть свои преимущества. Для каждой вводимой позиции единицы и нули будут в разных ячейках, то есть всякий раз для вычислений будет использоваться свое уникальное сочетание активных ячеек, отличное от других позиций и соответственно свое сочетание используемых коэффициентов. Таким образом, любая позиция на входном слое будет вычисляться по собственному пути.
Получается, сеть сильно сэкономит вычислительные ресурсы и в то же время у каждой позиции будет свой оригинальный набор вычисляемых параметров. Это обеспечит, в некотором смысле, разную "нейросеть" на входном слое для каждой позиции. Имея 80 000 входных условий, сеть может гибко подстроиться под каждую позицию, оперативно адаптируя, таким образом, свою "базу знаний".
Избыточное количество знаний (коэффициентов) позволяет отчасти компенсировать малое количество вычислений, которое критично для относительно слабосильных, в сравнении с видеокартами, векторов центральных процессоров.
Кроме всего прочего, используя связки король-фигура, мы как бы "подсказываем" нейросети важные сочетания фигур, которые сеть вследствие своей небольшой глубины не успевает/не имеет возможности вычислить самостоятельно. В каком-то смысле здесь мы заранее "вычислили" для нее важные признаки позиции.
Такое представление позиции называется оверпараметризированным. По сути избыточным для крупных нейросетей, но выгодным для архитектуры NNUE. Можно сказать, что NNUE работает по принципу энциклопедии. Содержит большой объем информации (коэффициентов), но использует только небольшую ее часть для получения оценки позиции в каждом отдельном случае.
На каждой линии выходящей из входной ячейки находится один множитель/коэффициент нейросети, поэтому всего существует 10 млн. коэффициентов или 2х40000х256 = 20 млн. возможных вычислений (верхний и нижний путь используют одинаковые коэффициенты). В то же время, реальное количество вычислений для подаваемой на вход позиции на "линиях" входного слоя нейросети не превысит 2х30х256 = 15 000 умножений и столько же сложений полученных результатов. Конечно, при сокращении количества фигур на доске в процессе игры, количество "единиц" и соответственно вычислений станет еще меньше.
По большому счету, на входном слое не обязательно производить любые умножения. Задавая на входе позицию лишь нулями и единицами, можно избежать операции умножения на 1, поскольку она ничего не даст кроме самого числа. Соответственно на входном слое можно выполнять лишь операции суммирования в ячейки второго столбца по сходящимся линиям от "единичных" коэффициентов нейросети.
Еще одна оптимизация заключается в том, что когда перебор скользит по дереву вверх-вниз, производя и откатывая ходы, то при каждом отдельном ходе меняется лишь положение одной фигуры. Для остальных фигур активные ячейки останутся прежними, а значит и вычисляемые значения будут те же самые. В таком случае можно сохранить вычисления предыдущей позиции и лишь прибавить-вычесть пару значений во всех ячейках второго столбца для ходившей фигуры. Поэтому если только не ходил король, начинать расчет с нуля не обязательно.
То есть нужно из сумм в ячейках второго столбца (аккумулятора) вычесть веса предыдущего положения фигуры и прибавить веса ее нового положения. В некоторых случаях, например при взятиях, придется еще удалить значения по линиям от снятой фигуры, так как в ее ячейке теперь ноль. И только при движении короля изменится положение каждой "единичной" связи, поэтому придется пересчитать все суммы, но только по одному пути, то есть 30х256 коэффициентов.
Это основные оптимизации на входном слое, делающие архитектуру NNUE такой удачной, при ее в общем-то небольшом размере и простоте.
В конечном итоге, сохраняя в некотором отношении гибкость большой нейросети, NNUE имеет объем вычислений в тысячи раз меньше. Разумеется не без последствий, но тем не менее со своей выгодой.
*****
Давайте перейдем к более предметному описанию нейросети NNUE в том виде, в котором она была первоначально реализована в Стокфише.
За входной слой отвечает Feature Transformer. С приложением всех оптимизаций, вычисления на нем сводятся к простому суммированию во второй столбец ячеек (accumulator) "активированных" весов сети (weights), т.е. весов с линий из ячеек с единицами (features).
Как уже отмечалось выше, такие вычисления можно проводить двумя способами - полное (refresh), с пересчетом для всех активных линий или частичное (update), только для изменившей свое положение фигуры. Во втором случае используются сохраненные ранее состояния аккумулятора из стека предыдущих позиций. Примерный код реализации можно посмотреть здесь:
https://github.com/official-stockfish/nnue-pytorch/blob/master/docs/nnue.md#feature-transformer-2
Полученные значения во всех ячейках складываются с еще одним отдельным числом для каждой ячейки (Bias). Если итоговый результат в ячейке выходит за пределы допустимого диапазона значений, то есть итог вычислений перейдет через верхний или нижний предел, то он "подрезается" до ближайшего разрешенного значения с помощью Clipped ReLU.
Далее вектор во втором столбце ячеек из 256 чисел белого короля, и аналогичный вектор из 256 чисел для черного, стыкуются в единый вектор из 512 чисел в порядке очереди хода (с каждым ходом обе части меняются местами). Попутно производится преобразование (quantisation) целых чисел входного слоя из 16-битного формата int16 к более простому 8-битному представлению int8. Он будет использоваться для остальных слоев.
Таким образом, на входном слое вычисления производятся над 16-битными целыми числами. На других слоях можно использовать меньшую точность, поэтому размерность чисел снижают до 8 бит с помощью квантизации. Это еще одна оптимизация, среди прочих.
Далее вычисления подхватывает первый скрытый слой (Linear layer 1). Входной вектор из 512-ти чисел для этого слоя (второй столбец ячеек на схеме) перемножают на матрицу первого скрытого слоя нейросети (таблица чисел) с помощью аффинного преобразования. Оно заключается в ротации (повороте) блоков чисел для более удобного вычисления и позволяет быстро и эффективно выполнять умножение вектора на матрицу, то есть перемножать строки чисел на столбцы таблицы чисел.
https://github.com/official-stockfish/nnue-pytorch/blob/master/docs/nnue.md#linear-layer-4
Аналогично, на выходе слоя к суммам в ячейках добавляют bias и производится обрезка полученных значений с помощью Clipped ReLU.
https://github.com/official-stockfish/nnue-pytorch/blob/master/docs/nnue.md#clippedrelu-2
Пройдя по всем оставшимся слоям подобным образом, мы получаем оценку позиции.
https://github.com/official-stockfish/nnue-pytorch/blob/master/docs/nnue.md#putting-it-together
В целом, большинство из оптимизаций входного слоя не применимы на скрытых слоях. Поэтому объем вычислений на них мог бы многократно возрасти. Чтобы удержать его в разумных пределах размерность таких слоев приходится сильно уменьшать. Сокращение числа вычисляемых параметров необходимо еще потому, что вычислительные мощности векторных блоков процессоров гораздо скромнее, чем у тензорных ядер видеокарт. А перемножать приходится в полносвязных сетях, что дополнительно увеличивает объем вычислений.
На первом скрытом слое количество вычисляемых параметров уменьшается с 512-ти до всего 32-х чисел. На втором скрытом слое их количество остается таким же небольшим.
Соответственно, на первом скрытом слое производится 512 х 32 = 16 384 умножений чисел и затем столько же сложений полученных результатов. Плюс указанные выше преобразования. На втором скрытом слое производится 32 х 32 = 1024 умножений и столько же сложений. Выходной слой содержит еще меньше вычислений.
Для перемножения и сложения этих чисел используются специальные блоки центральных процессоров. В отличие от тех же ALU, они перемножают сразу группы чисел, собранных в определенном порядке - так называемые вектора. Поэтому каждое перемножение пары 256-битных векторов AVX2 позволяет производить за один такт сразу 32 умножения 8-битных целых чисел. При использовании FMA в тот же единственный такт укладывается еще и сложение полученных результатов. А учитывая, что в ядре процессора содержится сразу несколько векторных блоков, то соответственно каждое ядро процессора производит за такт еще кратно больше вычислений.
В конечном итоге, наиболее вычислительно требовательными остаются входной и первый скрытый слои. Хотя входной слой содержит гораздо больше коэффициентов (весов) нейросети, он является разреженным и по объему вычислений обычно не превосходит первый скрытый слой. В свою очередь второй скрытый и выходной слои вычисляются уже гораздо быстрее.
*****
Приведенная выше схема вычисления оценки позиции примерно соответствует тому виду, в котором она была перенесена в шахматную программу Стокфиш из сеги в августе 2020 года. Первый официальный релиз Стокфиша 12 с нейросетью, состоялся в сентябре и не слишком отличается от рабочих версий программы.
Исходный код для структуры нейросети, которой посвящена эта часть статьи, можно найти в папке nnue программы Стокфиш 12. В современном Стокфише 18 общая структура нейросети изрядно усложнилась. Тем не менее, базовая архитектура и общее количество слоев (то есть глубина сети), введенная когда-то в сеги, остались прежними. Это все еще полносвязная нейросеть "мелкого заложения".
Более подробный обзор ранней и современной реализации структуры нейросети NNUE, применительно к практике, можно найти на отдельной страничке Стокфиша на гитхабе. На нее уже делались отсылки выше:
https://github.com/official-stockfish/nnue-pytorch/blob/master/docs/nnue.md
В целом, с момента появления в шахматных программах, нейросети NNUE претерпели множество изменений. Часть из них были вынуждены для адаптации к реалиям шахмат, но в основном они касались увеличения размеров сети "в ширину" и усложнения ее общей структуры.
С течением времени в Стокфише было увеличено количество вычисляемых параметров (размеры) входного и первого скрытого слоя нейросети. На входе помимо информации о координатах фигур, добавлена информация о фигурах атакующих другие фигуры (угрозах). Она позволила "обратить внимание" нейросети на соответствующие важные факторы позиции.
Помимо этого, в некоторых слоях вычисления были разбиты на несколько этапов. Добавлены так же различные остаточные (residual) связи.
На выходых слоях нейросети появилось несколько путей вычислений (buckets), из которых выбирается только один, в зависимости от количества материала на доске. Такая "развилка" вычислений позволяет до некоторой степени адаптировать оценку к позициям из разных стадий партии.
Кроме исходных текстов самой программы Стокфиш 18, за подробной информацией по всем вопросам связанным с общей архитектурой, получением данных для обучения и режимах тренировки сети следует обращаться к wiki Стокфиша на гитхабе. Здесь все расписано гораздо подробнее и применительно к реальной программе, в том числе по всем темам, которых мы лишь кратко касались выше.
https://github.com/official-stockfish/nnue-pytorch/wiki
На этом мы закончим общий обзор типов оценочных функций, применяемых в шахматных программах на классической базе. В следующей части вернемся обратно к перебору и рассмотрим исходный код поиска шахматной программы Стокфиш. Кому не интересны вопросы непосредственной реализации логики перебора на примерах кода, могут сразу перейти к заключению в последней части статьи.
Продолжение следует...