Жаль, что я этот канал начал, когда уже много кода написано, но все же

Коротко опишу все, что уже существует в самом движке и в проектах вокруг него. Начну с самого движка:
- быстрые правила с использованием Magic Bitboards и PEXT Bitboards (для новых CPU)
- проверка правил на корректность путем сравнения их с моей более старой реализацией, Dodecahedron
- почти полноценная реализация протокола UCI со стороны движка
- альфа-бета поиск с PVS
- сортировка ходов с MVV/LVA, киллерами и эвристикой истории
- хэш-таблица
- простая многопоточность: потоки обмениваются информацией только через хэш-таблицу, т. е. если поток видит, что позиция уже была просчитана, то он просто берет результат
- поиск взятий в конце для устранения эффекта горизонта
- простой Futility Pruning
- проверки для рекурсивного поиска: проверяют, что все инварианты в коде соблюдены, включаются отдельным флагом
- простая оценка позиций на основе таблиц фигура-поле + немного дополнительных факторов
- автоматический подбор коэффициентов оценки (об этом позже)
- немного бенчмарков и тестов ко всему этому

Для тестирования проекта используется программа Battlefield, которая может гонять партии движков друг с другом и оценивать статистическую значимость результатов. Эта программа написана на языке Pascal, потому что использует куски кода из моего более старого проекта, Chess256. Здесь правила реализованы практически «в лоб», поэтому Battlefield работает не очень быстро, что может быть заметно на ультракоротких партиях, а в остальном проблем не доставляет (т.к. все равно большую часть времени CPU уходит на обдумывание ходов движками)

Эта штука используется для проверки гипотез и оценки качества: если новая версия может статистически значимо победить предыдущую, то мы ее принимаем. К сожалению, так можно обнаружить только большие изменения в силе игры (на ~30-70 Эло). Чтобы обнаружить небольшое изменение, придется гонять очень много партий, а это долго

Немного про идейную часть проекта. А идея заключается в том, чтобы как можно больше вещей объявить как constexpr, чтобы дать компилятору большой простор для оптимизаций. В то же время, неплохо было бы генерировать некоторые константы автоматически, в частности, «магические значения» для Magic Bitboards.

Поэтому сейчас сделано так: существуют генераторы, которые генерируют заголовочные файлы с константами (например, такой). Потом CMake запускает этот генератор (сама функция generate_file объявлена здесь), а сгенерированный заголовочный файл подключается в проект

Получается сложно во время компиляции, зато не несет никаких расходов в рантайме: константы вкомпилированы прямо в код :)

Про подбор весов:

В оценке позиции используется простая линейная модель. Из доски извлекаются некоторые признаки (к примеру, «сколько коней стоит на поле c6» или «сколько пешек на поле»). Признаки симметричны для обеих сторон, т. е. белый конь на c6 прибавляет 1 к признаку «сколько коней стоит на поле c6», а черный конь на этом поле — отнимает 1. Оценка равна скалярному произведению вектора весов на вектор признаков. Возникает вопрос, как подобрать вектор весов таким образом, чтобы движок играл как можно сильнее

Со стороны самого движка есть такие инструменты:
- файлик features.json, который содержит все веса и описание признаков
- шаблонная магия, которая позволяет одному и тому же коду извлекать признаки и их же применять (в зависимости от шаблонных параметров)
- вспомогательные утилиты, которые помогают извлекать коэффициенты из позиций и удобно применять новые веса
- генераторы, которые читают features.json и генерируют из него заголовочные файлы (про автогенерацию пост выше)

Теперь о том, как, собственно, происходит сам подбор весов. Метод описан в этом посте на Хабре, там же можно найти всякую теорию и формулы. Я больше расскажу, как именно происходит процесс в самом SoFCheck:
- сначала надо откуда-то взять датасет. Для этого можно запустить движок играть с самим собой огромное количество раз (к примеру, 30000) и извлечь позиции. Это делается с помощью Battlefield. Движки играли на моем Android-планшете в Termux, чтобы не нагружать ноутбук, но об этом, возможно, будет отдельный пост
- с помощью утилиты make_dataset удаляем неспокойные позиции (со взятиями и шахами), из оставшихся извлекает признаки. Получаем огромный csv-файл
- csv-файл скармливаем в Jupyter-ноутбук и получаем новые веса
- вставляем новые веса в features.json с помощью утилиты apply_weights
- проверяем, что получилось

Как можно видеть, кода вокруг подбора весов очень много, зато он хорошо автоматизирует процесс и облегчает его

Что дает подбор весов? У меня он улучшил результат где-то на 100 Эло по сравнению с предыдущей версией, где коэффициенты были вбиты вручную. Полезная штука :)

В целом, про уровень игры. Я точно не могу сказать, насколько мой движок силен, но могу оценить его примерно на уровне 2200-2300 Эло. Доказательством этому служит то, что SoFCheck уверенно побеждает MORA в режиме 1 секунда на ход. При этом MORA имеет рейтинг 2200 на CCRL. Battlefield мне выдал такие результаты на 100 играх:

Wins: 49, Loses: 26, Draws: 25
Score: 61.5:38.5
Confidence interval:
  p = 0.90: First wins
  p = 0.95: First wins
  p = 0.97: First wins
  p = 0.99: Unclear
Other stats:
LOS = 1.00
Elo difference = 81.37

Как видно из предыдущих постов, уже сделано много классных вещей. Но я на этом не собираюсь останавливаться :) Еще не все реализовано, и определенно есть куда расти

В следующих постах немного про то, чем я занимался в последнее время. Изменения больше касаются инфраструктуры вокруг проекта и не приносят никаких улучшений в силе игры, но я считаю, что рассказ про них будет интересным

Во-первых, такое изменение. Чтобы показать, что файл принадлежит проекту под лицензией GPL (а SoFCheck сейчас использует GPLv3), стоит в начало каждого файла добавить уведомление о лицензии. Мне было лень делать это вручную, поэтому я написал простой скрипт на питоне, который добавляет такие комментарии в начало каждого файла. Еще этот скрипт умеет обновлять даты изменения файлов (всякие Copyright (C) 2020-2021 кто-то там), глядя на git log

Во-вторых, я улучшил сборку в CI. Раньше использовался Travis для сборок только под GNU/Linux, сейчас я перешел на GitHub Actions и собираю проект сразу под Windows, GNU/Linux и Mac

Пайплайн там не очень сложный, но имеет некоторые особенности. Во-первых, я фиксирую версии компиляторов (сейчас используются gcc-8 и clang-9), чтобы гарантировать, что код точно соберется на этих версиях. Значит, придется устанавливать эти версии компиляторов вручную. Во-вторых, мне надо предварительно собрать и установить зависимости (Google Test и Google Benchmark). В-третьих, у меня есть много разных конфигураций с разными флагами под разные платформы

Все эти действия усложняют процесс. Я не смог просто и компактно описать процесс сборки в yml-файле для GitHub Actions, а готовые action'ы мне не подходили ввиду специфичных требований выше Поэтому весь код, связанный со сборкой, запускает скрипт на питоне, а сам пайпайн для GitHub Actions содержит лишь вызовы этого скрипта. Несомненный плюс подхода — можно легко сменить провайдера CI, не переписывая большую часть кода

Были и подводные камни:

Во-первых, отлаживать пайплайн у себя локально не получилось. Поэтому приходилось каждый раз коммитить, пушить на сервер и смотреть, что получится. После примерно 80 итераций сборка все же прошла успешно :)

Во-вторых, clang-tidy не работает под Windows. Причина такая: CMake для Windows убирает часть параметров в response-файлы, чтобы обойти ограничение на длину командной строки. К сожалению, clang-tidy ничего не знает про response-файлы и падает. По этой же причине не удалось завести clang под Windows

В-третьих, код, собранный с BMI2, падал на macOS с SIGILL, поэтому пришлось отключить этот режим сборки

Еще я добавил поддержку MSVC, чтобы убедиться, что мой код хорошо работает на разных компиляторах

Во-первых, в MSVC другой синтаксис флагов. Поэтому пришлось добавить кучу заглушек в CMakeLists.txt, а часть интересных возможностей — вообще отключить. Например, для MSVC недоступна сборка с санитайзерами

Во-вторых, пришлось поместить специфичный для GCC код под #ifdef. К счастью, такого кода немного: для битовых операций __builtin_popcount(), __builtin_ctz() и подобные. Сейчас там есть вариант для 64-х битного MSVC, а для более экзотичных компиляторов (и для 32-х битного MSVC) написан fallback с битов магией. Еще пострадали макросы в util/misc.h. В остальном проблем не возникало

В-третьих, MSVC очень агрессивно ругается, если неявно привести тип к меньшему (так называемый narrowing conversion). А поскольку я собираю с -Werror (или /WX для MSVC), то все предупреждения пришлось исправлять. Предупреждения оказались весьма полезными, поскольку я увидел пару потенциальных багов. В остальных местах пришлось поставить static_cast<>(). Получилось даже лучше: теперь больше преобразований стали явными

В-четвертых, ему не понравились constexpr-операторы в шаблонном классе BaseCoefs<Storage>. От параметра Storage зависит, можно ли использовать класс вместе с constexpr. С вектором constexpr не сделаешь (в C++20 можно, но SoFCheck сейчас использует C++17). А если Storage использует лишь массивы, то класс спокойно можно использовать во время компиляции

Так вот, MSVC мне выдал ошибку вида «смотрите, этот оператор никогда не может быть constexpr, потому что он в одной из перегрузок возвращает std::vector<>». Я не знаю, прав ли MSVC (мне все-таки кажется, что нет), но пришлось убрать constexpr с части операторов у BaseCoefs<Storage>

Еще надо было настроить сборку в CI с MSVC (как для 32 бит, так и для 64 бит), но на этом шаге трудностей не возникло. Просто пришлось добавить чуть-чуть кода в скрипт, и все завелось :)

Наконец, расскажу про include-what-you-use. Этот инструмент позволяет делать следующее:
- находить неиспользуемые include'ы
- находить include'ы, которые стоит добавить. Например, мы в файле b.h пишем #include "a.h". А в некотором cpp-файле делаем #include "b.h" и используем как функции из b.h, так и функции из a.h. Тогда include-what-you-use предложит заинклудить a.h
- предлагать добавить forward declaration'ы вместо того, чтобы инклудить заголовки. Таким образом можно уменьшить время компиляции

Звучит довольно полезно, поэтому я поставил его из репозиториев Debian и решил запустить:

$ cmake -DCMAKE_EXPORT_COMPILE_COMMANDS=ON ..
$ make -j
$ iwyu_tool -p . --

include-what-you-use интегрирован с CMake, поэтому его можно сразу запускать при сборке:

$ CC=clang CXX=clang++ cmake -DCMAKE_CXX_INCLUDE_WHAT_YOU_USE=iwyu ..
$ make -j

Теперь коротко о том, какие результаты я получил. Было много действительно корректных срабатываний, но были и случаи, когда он вел себя неправильно

Во-первых, он хотел выкинуть config.h. В этом файле содержатся всякие макросы, которые затем с #ifdef'ами используются в коде

Во-вторых, иногда он предлагал использовать какие-то странные include'ы вроде #include <ext/alloc_traits.h>

В-третьих, он предлагал очень странные вещи, когда я подключал gtest/gtest.h в Google-тестах: ссылка

В-четвертых, он много ругался на код Dodecahedron'а. Этот код я не хочу исправлять, а как отключить проверку для некоторых файлов, я не нашел

В общем, ложных срабатываний в результатах получилось довольно много, поэтому я не стал добавлять include-what-you-use в CI. Просто буду его запускать время от времени и смотреть

Ну и наконец, ссылка на коммит, в котором я все это исправил

Пока я настраиваю эвристику нулевого хода и проверяю ее работоспособность на Battlefield'е (про него был пост выше), немного расскажу про то, как я оптимизировал Battlefield

Как-то раз я заметил, что на коротких играх (порядка 10 мс на ход) Battlefield потребляет очень много процессорного времени. Чуть ли не треть времени, которую работал процесс движка. Решил разобраться, в чем же дело

Battlefield написал на Pascal. К счастью, у компилятора FPC, которым он собирается, есть поддержка Valgrind: надо лишь добавить флаг -gv при сборке. После этого можно попрофилировать код инструментом Callgrind, который позволяет отследить, сколько времени работает каждая функция. Для визуализации этих данных можно воспользоваться, например, замечательной программой KCacheGrind

В результате я выявил следующее. Во-первых, много времени занимала функция PutChecks, которая решала для каждого хода, является ли он шахом или матом. Такая возможность полезна для преобразования хода в строку, но абсолютно не нужна в остальных случаях

Во-вторых, очень много раз вызывается генерация всех ходов. Стоит отметить, что генератор ходов в Battlefield довольно медленный. Он писался для Chess256, где скорость была не так уж и важна

Иногда генерация ходов вызывалась вообще без особого смысла, просто потому что ходы генерировались при каждом изменении позиции. К счастью, такое поведение легко отключается. Но были и случаи, когда генерация вызывалась, чтобы можно было проверить корректность хода. Тогда можно генерировать не все ходы, а только ходы заданной фигуры. Для этого уже пришлось поменять функцию GenerateMoves, чтобы так можно было делать

Главной проблемой было применить все эти оптимизации, не сломав имеющийся код: я не залазил в код Chess256 уже пару лет, и до конца не уверен, что там творится. Тестов, к сожалению, я не писал, поэтому пришлось подойти к изменениям довольно аккуратно

Изменения получились такими. Через некоторое время я еще немного пооптимизировал

Какое ускорение это дало? Сам Battlefield стал работать минимум в 3-4 раза меньше. Но это не значит, что матчи стали завершаться в три раза быстрее: большую часть времени все равно работали движки, а не Battlefield. Тем не менее, прирост скорости получился довольно серьезным: время, за которое завершились игры, уменьшилось где-то 40% на коротких (~10мс на ход, уже точные цифры не помню) матчах. На более длинных (~100 мс на ход) время уменьшилось где-то на 10%. Довольно неплохо :)

Сейчас Battlefield занимает немного времени: примерно 2% от суммарного времени на матчах по 100мс на ход и примерно 6% времени — на матчах по 10мс на ход. Если запускать по 1мс на ход, то получится значительно больше — где-то 15% времени, но на таком времени я тестирую не очень много. По этой причине дальше оптимизировать не вижу особого смысла: ускорение получится небольшим, зато придется потратить больше времени и здо́рово увеличить вероятность багов. Есть и другая проблема, связанная со скоростью работы Battlefield'а: он ждет ответа от движка, засыпая на 1 миллисекунду в цикле и проверяя каждый раз ввод (код)

Можно, конечно, переписать Battlefield, но здесь стоит вспомнить знаменитый пост Джоэла Спольски про переписывание с нуля и успокоиться. Хотя, возможно, я когда-нибудь вернусь к теме оптимизации Battlefield, но это произойдет нескоро…