Для тестирования проекта используется программа 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, но это произойдет нескоро…

Вроде бы эвристика нулевого хода работает: после дебага мне удалось добиться улучшений. Пока она написана в форме null move reduction: мы не отсекаем ветку, а лишь сильно уменьшаем глубину. Но я продолжу эксперименты, и посмотрю насколько хорошо отработают другие варианты

Результаты против предыдущей версии пока что такие (200 игр, 500 мс на ход):

Wins: 91, Loses: 46, Draws: 63
Score: 122.5:77.5
Confidence interval:
  p = 0.90: First wins
  p = 0.95: First wins
  p = 0.97: First wins
  p = 0.99: First wins
Other stats:
LOS = 1.00
Elo difference = 79.53

Еще из интересного за сегодня: сделал так, чтобы информация о текущем коммите включалась в бинарник и отображалась в имени движка. Раньше оно было сделано не очень надежно: номер коммита в бинарнике не всегда соответствовал реальности. Сейчас эта инфа обновляется каждый раз, когда сдвигается HEAD

Чтобы этого добиться, я добавил add_custom_command(). Он конфигурирует файл с версией и зависит от файла .git/logs/HEAD. Когда этот файл обновляется (например, при коммите), то файл с версией обновляется

Впрочем, лучше посмотреть дифф, чем читать объяснение :)

После не очень продолжительного тестирования решил оставить null move reduction. Сравнивал силу игры против версии с null move pruning (т. е. когда мы полностью отсекаем ветку, а не понижаем глубину) и не получил значимых результатов. А поскольку они играют примерно на одинаковом уровне, я все-таки решил оставить null move reduction: он считает чуть больше позиций и относительно устойчив к цугцвангу

Сами изменения выглядят так: коммит. Кода не очень много, зато прирост большой :)

Я пока не тратил много времени на подбор коэффициентов. Сейчас лучше написать побольше эвристик и получить выгоду от всевозможных крупных улучшений, а потом уже заняться тонкой настройкой, от которой выгода меньше. К тому же, у меня не очень много времени на запуск большого числа партий, а без этого Battlefield не может задетектить пользу от небольших улучшений

Как-то давно я не занимался движком и не писал посты в канал. Пора бы исправить эту ошибку

Я как раз решил добавить одну довольно мощную эвристику — Late move reductions. Смысл примерно такой. Как известно, ходы обычно рассматриваются в отсортированном порядке: сначала те, которые могут улучшить текущий результат, потом те, которые с большой вероятностью его не улучшают. Мы берем те ходы, которые стоят далеко в порядке сортировки и считаем их на уменьшенной глубине. Если на уменьшенной глубине они дают какое-то улучшение, то пересчитываем заново — уже на полной глубине

Эвристика довольно мощная и дает хороший прирост — ~100 Эло при игре на 500 мс против старой версии. Но результат очень сильно зависит от контроля времени: при маленьком количестве времени на ход улучшения почти незаметны, а при очень маленьком — незаметны совсем

Я пытался настраивать параметры для Late move reductions. К сожалению, для проверки, насколько хорошо работают параметры, требуется большое время. Я заметил это, когда проводил ухудшающий эксперимент: стал уменьшать глубину в этой эвристике не на 1, а на 100. Интересно, что серьезное ухудшение игры я заметил, только когда движки тратили секунду на ход. То есть, чтобы проверить новые параметры, мне необходимо запустить 500 игр (поскольку изменения могут быть не очень значительными) при 1 секунде на ход. Такая проверка занимает на моем ноутбуке примерно 1.5-2 часа, что довольно долго

Возможно, поможет такой способ тестирования. Надо запускать Late move reductions, но не отсекаться в действительности, а смотреть число попаданий: насколько часто эта эвристика отсекает реальное улучшение. Затем можно пытаться настроить эвристику так, чтобы процент ложноположительных срабатываний был как можно меньше. Я еще не проверял, что из этого получится, но когда-нибудь точно стоит попробовать :)

А пока что я руководствуюсь стратегией «забрать самые крупные улучшения, а потом уже докручивать более мелкие». Поэтому решил сильно не напрягаться подбором параметров и просто вкатил изменения в код :)

Стоит полюбоваться на само изменение: коммит

Заметил, что в коде анализа часто встречаются такие строчки, чтобы сделать ход:
const Evaluator::Tag newTag = tag.updated(board_, move);
const MovePersistence persistence = moveMake(board_, move);
DGN_ASSERT(newTag.isValid(board_));

А после того, как мы закончили анализировать этот ход, надо бы его отменить:
moveUnmake(board_, move, persistence);

В коде много мест, где есть return и continue, и можно случайно забыть сделать отмену. Забывчивость, скорее всего, не пройдет бесследно: код провалит тесты в режиме диагностики. Тем не менее, можно сделать лучше и красивее. На помощь приходит RAII: ссылка

Пока я не испытывал никаких новых эвристик, расскажу про clang-tidy и про то, как он используется в SoFCheck'е

Что такое clang-tidy? Это статический анализатор, входящий в состав компилятора Clang. Он может отлавливать проблемные места в коде. Еще он может проверять код на соответствие хорошим практикам и кодстайлу (например, проверять, что имена переменных названы в camelCase). То есть, инструмент довольно мощный. clang-tidy помогает писать более чистый код и предотвращать потенциальные ошибки в коде

Чтобы его настроить, достаточно добавить файл .clang-tidy в корень проекта. В этом файле необходимо указать все используемые проверки

Как запускать проверку? Можно, например, найти нужный пункт меню в IDE (у меня в KDevelop это Code > Analyze Current Project With). Есть и интеграция с CMake: достаточно при конфигурировании проекта указать флаг -DCMAKE_CXX_CLANG_TIDY=<путь до clang-tidy>, и он будет запускаться вместе со сборкой проекта. Третий вариант — запустить скрипт run-clang-tidy из папки со сборкой. Этот скрипт просто пробежится по всем файлам проекта. Но для этого нужно наличие файла compile_commands.json, поэтому стоит прописать в CMake флаг -DCMAKE_EXPORT_COMPILE_COMMANDS=ON, чтобы этот файл создавался

Конечно, clang-tidy хорош, но у него есть и недостатки:

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

Во-вторых, скорость работы. Работает clang-tidy довольно медленно, точно в несколько раз медленнее, чем компилятор. В SoFCheck'е это не доставляет больших проблем (разве что пару лишних минут на сборку в CI), а в больших проектах может быть критично

В-третьих, он иногда плохо работает с используемыми библиотеками. Пару диагностик пришлось отключить, поскольку иначе возникали проблемы с тестами на Google Test и бенчмарками на Google Benchmark

В-четвертых, clang-tidy местами забагован. И это становится причиной многих отключенных диагностик и NOLINT. Бывают и довольно странные баги, например, такой. Или такая проблема. Или ложноположительные срабатывания с if constexpr

Тем не менее, для меня плюсы перевешивают минусы, поэтому clang-tidy успешно используется в SoFCheck'е

Из-за описанных выше проблем конфиг для clang-tidy получился довольно объемным: ссылка. Там же есть комментарии, которые объясняют, почему были отключены некоторые проверки

Решил попробовать и ради интереса переписать BattleField на Python (напоминаю, что это утилита для тестирования движков, подробнее здесь). Коротко расскажу о том, зачем это нужно и что получилось в итоге

Одно из направлений, в котором я хочу улучшить BattleField — это сделать его распределенным: чтобы часть партий проходили локально на ноутбуке, часть — в облаке на большом количестве ядер. Тестирование от этого станет значительно быстрее. А Pascal не очень хорошо дружит с сетевым программированием. Конечно, HTTP-клиент на нем написать можно, но гораздо приятнее это делать на других языках. Почему BattleField изначально написан на паскале, я уже объяснял здесь

Было решено переписать код на Python, потому что тогда 1) есть большие возможности по подключению в код всего, что угодно (например, всяких сетевых библиотек), 2) под него есть замечательная библиотека chess, которая реализует правила и взаимодействие с движками

BattleField — небольшой проект (~1200 строк, не считая часть из Chess256). После переписывания на Python бо́льшей части кода получилось примерно 700 строк. По этой причине работа много времени не заняла: всего-то 4-5 часов времени. Некоторые возможности, например, сохранение партий в PGN, пока не реализованы в версии на Python

Библиотека chess, хотя и написана на Python, реализована на битбоардах, а в BattleField используется наивная реализация правил. Я рассчитывал, что даже несмотря на медлительность Python'а, реализация в chess окажется быстрее моей