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

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

Во-первых, такое изменение. Чтобы показать, что файл принадлежит проекту под лицензией 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 окажется быстрее моей

В итоге получилось так. В однопоточном режиме обе реализации работают примерно одинаково. А в многопоточном режиме из-за GIL производительность проседает очень сильно. Скорее всего, эта проблема поправима: потоки практически не пишут в общую память, поэтому их получится разнести по разным процессам. Но стоит учитывать, что у оригинального Battlefield гораздо бо́льший потенциал ускорения, поскольку там правила написаны неоптимально. А шансов исправить существующую, довольно неплохо написанную библиотеку у меня меньше, чем переписать свой явно неоптимальный код

Вторая проблема с реализацией на Python заключается в следующем. Сейчас BattleField — это один бинарник без всяких зависимостей, который запустится везде. А вариант на Python требует установки зависимостей. Я сейчас не уверен, что следует усложнять процесс установки BattleField'а

В общем, мне следует тщательно обдумать, какую из версий развивать в дальнейшем (или же рассмотреть какие-то еще другие языки?) А пока что можно посмотреть, как выглядит BattleField на Python: ссылка

Давно здесь не было новостей, поэтому расскажу о том, что я сделал сегодня. А сегодня я выкатил новый релиз Battlefield'а: ссылка. Теперь можно выставить не только фиксированное количество времени на ход, но и полноценный контроль времени, например: "одна минута на игру" или "15 минут на 40 ходов плюс 5 секунд каждый ход"

Еще попробовал поиграть с ifrit'ом. У этого движка ~2400 рейтинга. Раньше с ним не удавалось сыграть по простой причине: ifrit нормально не поддерживал фиксированное время на ход. Если его попросить думать определенное количество времени, то он воспринимает этот лимит как нижнюю границу, и может начать думать больше. Battlefield'у это, естественно, не нравится; в таком случае он просто убивает процесс и засчитывает поражение. А с контролем времени ifrit играет как раз хорошо. Вот результаты на 100 играх, при 60 секундах на игру:

Wins: 31, Loses: 59, Draws: 10
Score: 36.0:64.0
Confidence interval:
  p = 0.90: Second wins
  p = 0.95: Second wins
  p = 0.97: Second wins
  p = 0.99: Second wins
Other stats:
LOS = 0.00
Elo difference = -99.95

Т.е. SoFCheck сливает ~100 Эло, что соотносится с моим представлением о его рейтинге примерно в 2300 Эло

Небольшое замечание. Я иногда сам поглядываю в код ifrit'а, чтобы посмотреть, как реализована та или иная эвристика. Этот движок, как и мой, написан на C++. Код там во многом довольно понятный и хорошо прокомментирован. Но я бы не назвал код ifrit'а хорошим, поскольку в нем много дублирующегося кода. Анализ для белых и для черных написан в двух отдельных функциях, которые очень похожи друг на друга. Интересно, конечно, почему автор не воспользовался NegaMax'ом

Еще во время сегодняшнего тестирования на Battlefield'е я обнаружил, что на маленьком контроле времени (менее 60 секунд на игру) SoFCheck может проиграть из-за просрочки по времени. Надо разбираться, почему так

Что-то я очень долго не писал ничего в код SoFCheck'а и в этот канал. Сегодня у меня наконец-то появилось немного свободного времени, чтобы всем этим заняться

Я решил по-нормальному парсить командную строку во всяких разных утилитах, написанных на C++. Сейчас там написана какая-то кастомная логика, которая смотрит на argc и argv напрямую. Я скоро собираюсь улучшать утилиту для сборки датасетов и добавить в нее больше флагов командной строки, но тогда кастомная логика станет довольно сложной

По этой причине мне понадобилась библиотека для парсинга командной строки. Требования примерно такие:
- легко встроить в проект, не должно быть внешних зависимостей
- нормальная работа при сборке с флагом -fno-exceptions (предполагается, что SoFCheck должен с ним нормально собираться)
- красивое отображение справки: если описание параметра или программы слишком длинное, его надо разбивать по строкам

Я посмотрел на имеющиеся библиотеки на awesome-cpp и выбрал для себя три:
1) https://github.com/bfgroup/Lyra: довольно неплохо работает, вообще не использует исключений, но не умеет переносить строки (см. issue)
2) https://github.com/taywee/args: хоть там и есть опция ARGS_NOEXCEPT, но библиотека работает с багами при ее использовании. Завел им issue по этому поводу
3) https://github.com/jarro2783/cxxopts: работает, умеет собираться без исключений (в этом случае при ошибке в параметрах командной строки программа просто завершается), но не умеет переносить описание программы, если оно слишком длинное (завел issue про это)

В итоге я выбрал 3), а проблему с переносом строк решил уже своими костылями и обертками. После этого осталось только убрать кастомную логику и немного пропатчить код

Наконец, покажу реализацию функции wordWrap() для разбиения длинных строк: ссылка. Код, конечно, не самый тривиальный, зато оптимальный и работает всегда за O(n)

У меня развалился GitHub Actions со странной ошибкой на git clone, которая проявляется время от времени:
$ git clone --branch v1.5.5 https://github.com/google/benchmark/
Cloning into 'benchmark'...
error: RPC failed; curl 56 OpenSSL SSL_read: Connection was reset, errno 10054
error: 5898 bytes of body are still expected
fetch-pack: unexpected disconnect while reading sideband packet
fatal: early EOF
fatal: fetch-pack: invalid index-pack output
Вот еще одно падение, на этот раз при клонировании Google Test:

$ git clone --branch release-1.10.0 https://github.com/google/googletest/
Cloning into 'googletest'...
error: RPC failed; curl 56 OpenSSL SSL_read: Connection was reset, errno 10054
error: 1885 bytes of body are still expected
fetch-pack: unexpected disconnect while reading sideband packet
fatal: early EOF
fatal: fetch-pack: invalid index-pack output

Надеюсь, что GitHub скоро поправит эту проблему, а то у меня весь CI сегодня красный :(