Про тесты в SoFCheck

Чтобы тестировать движок, я использую разные стратегии тестирования. Во-первых, юнит-тесты с помощью фреймворка Google Test: пример. Таким образом тестируется не весь код, а только часть, в надежности которой я не уверен, и не могу нормально протестировать другими методами. Мне лень писать юнит-тесты на весь код :)

В реализации правил, например, юнит-тестов нет вообще. Но корректность правил тоже проверяется, просто куда более мощным методом под названием selftest. Эта штука запускает генерацию ходов и проверки на шахи на куче разных позиций. Затем selftest сравнивает результаты генерации с тем, что выдает на тех же позициях мой более старый движок, Dodecahedron. В нем абсолютно другая реализация правил, и шансы дважды допустить одну и ту же ошибку стремятся к нулю :) Попутно на всех этих позициях SoFCheck проверяет разные инварианты: что отмена хода работает корректно, что если загрузить и сохранить доску из FEN, то получится тот же результат, и т.д. Такой набор проверок позволяет быть уверенным в том, что правила с большой вероятностью написаны без багов. Еще selftest сделан так, что на нем можно тестировать не только SoFCheck, а любую реализацию правил на C++. Есть даже гайд про это

(Насчет Dodecahedron: он в свое время проверялся похожим методом на еще более старой реализации правил, поэтому ошибка будет незамеченной, только если она допущена трижды в одном и том же месте)

Как генерируются позиции для selftest'а? Генератор выглядит вот так. Если кратко, то там 100 случайных игр, несколько добавленных вручную партий и несколько добавленных вручную позиций (всякие крайние случаи)

Есть тесты в static_assert, которые гоняются прямо во время компиляции: ссылка

Есть интеграционные тесты на UCI, которые вводят команды в фиктивный движок, а потом проверяют, что вывод этого движка совпал с тем, что ожидалось

Наконец, есть smoke-тест. Движок запускается на наборе позиций. Тест пройден, если движок думает 4 секунды над позицией и при этом не падает. Для этого теста код компилируется с дополнительными проверками, которые убеждаются, что никакие инварианты не нарушены (а если нарушены — программа падает). Поскольку эти проверки замедляют код, то они используются только в тестах, а в обычной сборке отключены

Конечно же, все эти запускаются в CI на каждый коммит. Самые долгие — selftest (около 4-5 минут) и smoke test (около 40 секунд), остальное работает быстрее

Как-то раз Антон (@Wind-Eagle) заметил, что у меня медленная реализация генератора ходов для пешек. Я решил сегодня взять и переписать

Запустил код на микробенчмарках. В позициях, где много пешек, генерация ходов ускорилась на 10-15%. Тем не менее, результаты оказались довольно шумными, и некоторые бенчмарки замедлились процентов на 5. Бенчмарки, которые имитируют рекурсивный анализ, практически не поменялись

А на реальном анализе получилось ускорение: на 9% в позиции с одними пешками, на 7% в околодебютных позициях, на 3-5% в глубоком миттельшпиле. Чем дальше от дебюта, тем меньше ускорение, поскольку там становится все меньше и меньше пешек; в эндшпиле старая и новая версии работают примерно одинаково быстро. Тем не менее, результат довольно неплохой :)

Коммит можно посмотреть здесь: ссылка

Еще я понял, что мои микробенчмарки не особо хороши и не отражают реальную скорость. Например бенчмарки, которые имитируют рекурсивный анализ, пытаются сделать все ходы в позициях, т.е. на них больше влияет скорость moveMake(), чем генерации ходов. В реальности из позиции делается в среднем 2-3 хода до отсечения, поэтому производительность moveMake() куда менее заметна, чем в бенчмарках

Вчера я улучшил оценку оставшегося времени в BattleField. Сейчас расскажу, как :)

Обычно BattleField выводит прогресс примерно в таком виде:
321/5000 games completed (7.99 min/2.07 hours), score = 153.0:168.0
Как оценить, сколько времени осталось (2.07 hours в строчке выше)? Раньше эта оценка производилась по очень простой формуле: total_time = time / count * total, где time — прошедшее время, count — количество сыгранных игр и total — общее количество игр

Несмотря на то, что эта формула очень простая, она не лишена недостатков. Она может выдавать сильно завышенные оценки на оставшееся время, когда прошло еще мало игр. Постепенно оценка сходится к реальному значению, но это происходит довольно медленно

Как можно сделать лучше? Построим такую модель. Пусть у нас время одной игры — случайная величина с математическим ожиданием 1. У нас есть jobs потоков. Каждый поток берет задачу, если задачи еще остались, и выполняет ее. Найдем математическое ожидание времени работы count игр — f(jobs, count). Тогда оценим время работы как total_time = time / f(jobs, count) * f(jobs, total). Здесь необязательно брать реальное значение f(jobs, count) — достаточно лишь довольно точной оценки (чем точнее, тем лучше)

Осталось научиться оценивать f(jobs, count). Здесь имеется две проблемы. Во-первых, я с ходу не придумал, как аналитически оценить это математическое ожидание. Во-вторых, мы не знаем распределение времени одной игры, а от этого зависит ответ. По этой причине будем подбирать оценку на f(jobs, count) эмпирически, считая, что время работы распределено нормально с некоторой дисперсией (я сейчас предполагаю, что дисперсия равна 0.25, хотя надо бы измерить, какова дисперсия времени работы на самом деле). Далее я написал симулятор, который находит требуемое матожидание с помощью метода Монте-Карло

Затем я немного поколдовал с симулятором и нашел довольно неплохую оценку для f(jobs, count). Ее можно увидеть в коммите, который улучшает оценку времени. Чтобы еще улучшить результаты, можно подбирать формулу не руками, а с помощью интерполяции или ML. Но это я сделаю как-нибудь потом

Я писал в прошлом посте, как я улучшил оценку оставшегося времени в BattleField. Сегодня оказалось, что я набагал в оценке и словил в BattleField'е деление на ноль, если jobs = 1. Попытался исправить функцию оценки и понял, что не так уж она и хороша. А это значит, что можно воспользоваться машинным обучением, чтобы ее улучшить :)

Не буду описывать здесь, как оно работает. Лучше смотрите в ноутбук, там все довольно хорошо описано. Есть еще коммит, в котором я как раз поправил функцию оценки

Теперь я полностью доволен тем, как работает оценивание времени работы :) Оно не завышает сильно оценку, если было сыграно малое количестве партий, как это происходило ранее

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

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

Потом надо было научить SoFCheck понимать новый формат. Для этого у меня есть небольшая библиотека для парсинга этого формата. Когда я ее писал, мне понадобился unique_ptr<T> с копированием: при копировании он должен копировать данные, на которые он указывает. Зачем это нужно? В коде повсеместно используются variant'ы, а один из вариантов содержит внутри себя доску и занимает из-за этого ~200 байт. Но тогда весь variant будет занимать неоправданно много места, что неприемлемо. Для решения такой проблемы как раз требуется спрятать доску за указатель. При этом хочется, чтобы копирование объектов по-прежнему работало. В итоге я написал что-то такое

После этого я реализовал фильтрацию в make_dataset, сгенерировал 100'000 партий движка с самим собой и обучил на 3 млн позиций из этих партий (из примерно 10 млн позиций). Выигрыша по сравнению с нефильтрованной выборкой, к сожалению, я не получил :(

Еще я написал классный скрипт owl.py, который упрощает мне жизнь. Например, раньше для утилиты apply_weights, которая записывает новые коэффициенты в features.json, надо было указывать путь до features.json. А owl сам знает путь до этого файла, и для обновления коэффициентов достаточно просто написать
./owl.py w a
В качестве приятного бонуса он сразу пересоберет движок с новыми коэффициентами :)

Еще owl может собрать несколько версий движка в одну команду. Это бывает очень полезно, чтобы сравнить разные версии по силе. Сборка нескольких версий реализована предельно просто: сохраняем незакоммиченные изменения, переходим на нужные коммиты, собираем с помощью CMake, возвращаем все обратно

А еще owl умеет рисовать маленькую сову ASCII-артом, которую я кидал в канал выше :)

Как owl узнает конфигурацию проекта и системы, чтобы все это делать? Все просто: нужные пути подставляются в скрипт CMake'ом: ссылка

Еще полезное улучшение: Battlefield теперь может показывать доверительный интервал для разницы в рейтинге Эло. Например, так:

Elo difference = -77.05/-55.00/-33.38 (low/avg/high, at p = 0.95)

Как вычисляется доверительный интервал? Как известно, рейтинг Эло можно представить как функцию elo(q), где q — вероятность победы первого игрока. Для q мы уже умеем считать среднеквадратичное отклонение σ и строить доверительный интервал [q - 1.96 * σ; q + 1.96 * σ]. Тогда доверительный интервал для рейтинга Эло будет равен [elo(q - 1.96 * σ); elo(q + 1.96 * σ)]

Я еще раз убедился в том, что для достижения высокой точности надо много игр. Если разница в силе игры невелика, то точность Battlefield примерно такая:
- для 100 игр: ±60 Эло
- для 1000 игр: ±25 Эло
- для 10000 игр: ±7 Эло
То есть, чтобы протестировать мелкое изменение, нужно от 1000 до 10000 игр, что довольно много

Нашел очередной странный баг в clang-tidy версии 11, который в CI проявился почему-то только на macOS. Он утверждает, что в коде есть деление на ноль:

/Users/runner/work/sofcheck/sofcheck/src/eval/feat/bin/make_dataset.cpp:140:5: note: 'size' initialized to 0
    const uint64_t size = *sampleSize_;
    ^
/Users/runner/work/sofcheck/sofcheck/src/eval/feat/bin/make_dataset.cpp:141:19: note: 'size' is < field 'count_'
    if (count_ <= size) {
                  ^
/Users/runner/work/sofcheck/sofcheck/src/eval/feat/bin/make_dataset.cpp:141:5: note: Taking false branch
    if (count_ <= size) {
    ^
/Users/runner/work/sofcheck/sofcheck/src/eval/feat/bin/make_dataset.cpp:145:9: note: Assuming the condition is true
    if (random_() % count_ < size) {
        ^
/Users/runner/work/sofcheck/sofcheck/src/eval/feat/bin/make_dataset.cpp:145:5: note: Taking true branch
    if (random_() % count_ < size) {
    ^
/Users/runner/work/sofcheck/sofcheck/src/eval/feat/bin/make_dataset.cpp:146:45: note: Division by zero
      sample_[static_cast<size_t>(random_() % size)] = board;

^
Сам код выглядит так. Т.е. clang-tidy почему-то утверждает, что size = 0, соглашается с тем, что count_ > 0, и при этом (random_() % count_ < size) по его мнению может быть true, хотя все типы здесь uint64_t

Обновление clang-tidy мне, к сожалению, не помогает: баг присутствует и в clang-tidy-13 :( Пришлось обходить проблему костылями

Еще одно серьезное улучшение — добавление в оценку позиции признаков для пешек: бонусы и штрафы за изолированные, двойные, проходные пешки

Скажу сразу: я разочаровался в пешках. Я ожидал, что после пешечных улучшений я получу минимум 60 Эло, а итоговые результаты (на 10000 играх) оказались такими:

Elo difference = 26.10/32.93/39.78 (low/avg/high, at p = 0.95)

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

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

Считать все пешечные признаки долго, поэтому их надо кэшировать: позиции пешек меняются относительно редко. Поэтому я написал такой код для кэширования. Подсчеты показали, что при анализе из начальной позиции получается примерно 7% промахов мимо этого кэша, но по ходу игры количество промахов постепенно снижается, и в миттельшпиле получается на более 2% промахов

Для кэширования необходимо как-то как-то считать хэш от всех пешек на доске. Здесь возможны два подхода. Первый — использовать zobrist hashing, как и для хэша доски в целом. Тогда нам надо вместе с хэшом для всей доски хранить еще хэш для пешек и постепенно пересчитывать его каждый ход. Второй подход — взять h(b1, b2), где b1 и b2 — это битбоарды белых и черных пешек соответственно, а h — некоторая хорошая хэш-функция общего назначения. Я попробовал в качестве такой хэш-функции FarmHash от Google и сделал коммит, который использует FarmHash для хэширования позиций пешек

Я решил сравнить, какой из этих двух подходов быстрее работает. Выяснилось, что все-таки пересчитывать zobrist hashing быстрее, хотя и статистически незначимо. Поэтому я решил реализовать первый вариант

Часть описанного выше улучшения — это улучшение самого процесса обучения. Во-первых, я изменил метрику с MAE (L1-метрика) на MSE (L2-метрика). Еще пробовал экспериментировать с L4-метрикой (чтобы больше штрафовать оценку за сильные ошибки и мало штрафовать за много мелких ошибок), но из этого ничего хорошего не получилось

Во-вторых, сделал нормализацию датасета и делю все признаки на (max - min), где min и max — минимальное и максимальное значения признака. Такой вот самописный MinMaxScaler :)

Обновленный ноутбук можно найти по ссылке

Пора рассказать, что нового появилось. Во-первых, я заметно ускорил утилиту make_dataset, которая по заданным партиям генерирует датасет для обучения. Раньше она писала выходной CSV-файл со скоростью примерно 20-30 МБ/с, что довольно медленно (датасет для нескольких миллионов позиций занимает пару гигабайт). Сейчас скорость достигает 200-300 МБ/с при записи в /dev/null, т.е. ускорение получилось примерно в 10 раз

Как я этого добился? Я решил попрофилировать make_dataset с помощью callgrind (часть valgrind). Посмотрел результаты и понял, что примерно 80% времени занимал вывод в std::cout. При этом, у меня уже тогда стоял std::ios_base::sync_with_stdio(false);, т.е. дело было не в синхронизации с stdio, а в том, что запись в потоки в C++ — штука не очень быстрая

Я переписал запись CSV таким образом: сделал у себя буферизацию и начал писать в свой буфер, а когда мой буфер заканчивается, то тогда я уже пишу в поток с помощью ostream::write(). Числа пишутся в буфер прямо на месте, при помощи std::to_chars(). Код получился таким. Буферизация дала ускорение в целых 4 раза!

Остальная часть ускорения вышла за счет многопоточности. Теперь make_dataset умеет обрабатывать позиции и писать куски CSV независимо в нескольких потоках, а затем уже выводить в файл. Устроено это так: в каждый поток прилетает набор позиций, по ним строится кусок CSV, который отправляется в поток вывода (поток в смысле thread, а не в смысле stream). А поток вывода уже выводит построенные куски CSV в файл

Вот коммит, в котором я все это сделал

Еще я провел матч на 100'000 партий:

...
99998/100000 games (6.15 hours/6.15 hours), score = 50241.0:49757.0, confidence = ?
99999/100000 games (6.15 hours/6.15 hours), score = 50241.0:49758.0, confidence = ?
100000/100000 games (6.15 hours/6.15 hours), score = 50241.5:49758.5, confidence = ?
Wins: 35515, Loses: 35032, Draws: 29453
Score: 50241.5:49758.5
Confidence interval:
  p = 0.90: Unclear
  p = 0.95: Unclear
  p = 0.97: Unclear
  p = 0.99: Unclear
Other stats:
LOS = 0.97
Elo difference = -0.48/1.68/3.83 (low/avg/high, at p = 0.95)

Точность потрясающая (±2 Эло), но работает долго и при маленьком контроле времени, так что всегда так запускать, увы, не получится

Недавно читал README движка Fruit. Там нашел такие строчки:

Some people find that Fruit is surprisingly "strong" given the above
(dull) description. The same persons are probably going to scrutinise
the source code looking for "magic tricks"; I wish them good luck. If
they find any, those are likely to be "bugs" that I have overlooked or
"features" I have forgotten to remove (please let me know). The main
search function is full_search() in search_full.cpp

I suggest instead that one ponders on what other "average amateur"
engines might be doing wrong ... Maybe trying too many heuristics
(they might be conflicting or choosing weights for them is too
difficult) or code that is too complex, maybe features that look
important but are actually performing no useful function ... Sorry I
do not know, and I don't think we will find the answer in Fruit ...

Я очень надеюсь, что аккуратная проверка каждой эвристики на игре движка с самим собой меня спасет от добавления плохих эвристик, и в итоге у меня получится быстрый и сильный движок :)

Во-вторых, я добавил оценку короля. Проверял следующее:
1) пешечный щит короля. Смотрим, какие есть пешки перед рокированным королем, и штрафуем, если там их не хватает. Дает до 20 Эло
2) близость вражеских фигур к королю. Раньше у меня такая эвристика была написана для ферзя, теперь я ее решил добавить для всех остальных фигур. Попытался обучить веса и обнаружил, что для других фигур они оказались близки к нулю, поэтому оставил близость только для ферзя и ладьи. Но попутно я обнаружил, что проверка на близость работала медленно (ссылка на код). После того, как я развернул цикл руками, я получил неплохое улучшение (около 40-50 Эло). Довольно неожиданно :)
3) прорыв пешечного щита вражескими пешками (он же pawn storm). Эта эвристика мне ничего не дала, а после обучения все только ухудшилось. Поэтому писать я ее не стал
В целом, за последнее время было больше неудачных экспериментов, чем удачных. Надеюсь, дальше улучшения пойдут лучше :)

И все-таки я добавил pawn storm в оценку позиции (см. пункт 3 из прошлого поста) и даже получил на нем ~20 Эло улучшения. Как я этого достиг, хотя раньше мне улучшить не удавалось? Все просто: я перегенерировал датасет. Если раньше там были партии старой версии движка с собой, то в новом датасете играет уже новая версия (тоже сама с собой). Вывод: для обучения лучше всего использовать партии того движка, в котором мы как собираемся подгонять веса. А еще лучше — актуальную его версию

Я порефакторил оценку позиции. Поэтому расскажу про то, как я тестировал код после рефакторинга и убедился, что ничего не поломалось

Подход довольно простой. У меня есть make_dataset, который умеет генерить коэффициенты для обучения. Он это делает, как раз запуская оценку позиции. Только вместо одного числа оценка позиции здесь возвращает вектор коэффициентов (это достигается с помощью шаблонной магии). Если я допустил баг, пока рефакторил, то это означает, что какие-то коэффициенты могли поменяться

Поэтому можно применить следующую простую идею: взять побольше позиций, запустить make_dataset на версии до и после рефакторинга, а затем убедиться, что хэш-суммы результата совпадают. К счастью, имеющиеся у меня датасеты насчитывают по несколько миллионов позиций, поэтому шанс ошибки очень мал. Такое вот baseline-тестирование :)

Еще make_dataset удобно использовать просто для дебага: можно вбить в него позицию (или еще лучше — целую партию) и посмотреть, какие признаки использовала оценка позиции. А потом проверить глазами, совпадает ли это с тем, что ожидалось

Раньше мой движок не мог нормально играть на короткий контроль времени в BattleField. Речь идет не про запуски с фиксированным временем обдумывания — в этом режиме уже давно проводятся все без исключения проверки, и можно считать, что здесь все нормально. Речь идет о контроле времени вида «1 минута на партию» или «1 минута на партию плюс одна секунда на ход». Или «1 минута на каждые 40 ходов»

Оказалось, что в таком случае движок часто проигрывает из-за того, что у него кончается время. Я пошел разбираться и выяснил следующее

Во-первых, Evaluator (класс, который отвечает за оценку позиции) хранит в себе кэш размером около 1 МБ. На выделение и очистку такого объема памяти явно потребуется время около 1 мс. Поэтому я решил кэшировать Evaluator'ы между запусками. Еще я сделал так, что замеры времени стали лучше отражать реальность, подвинув время старта ближе к реальному запуску анализа. Вот коммит, в котором это все произошло

Это не решило проблему полностью — движок все еще мог думать дольше, чем его попросили. Например, я его просил думать 2 мс — а он тратил 3 мс. Чтобы рассказать, как я решил эту проблему, немного поясню, как движок понимает, что пора заканчивать. Все просто: он время от времени зовет функцию mustStop(), которая замеряет время и проверяет, действительно ли пора остановиться. А чтобы не тратить много времени на замеры, мы делаем их не каждый запуск этой функции, а каждый 1024-й. Раньше там вместо 1024 стояло 4096, и было хуже: поскольку движок анализирует около 4 млн позиций в секунду, то раз в 4096 запусков означало проверки примерно раз в 1мс. Замена 4096 на 1024 улучшила ситуацию, но, к сожалению, полностью проблему не решила

Поэтому я переписал код, который решает, сколько времени должен думать движок (коммит). Здесь оказалось, что проблема не столько в моем движке, сколько в BattleField'е: из-за внутренних задержек в самом BattleField'е вместо 1мс на ход, на которые рассчитывал движок, могло получиться так, что реально прошло около 3мс. В итоге я вставил в код подпорки, чтобы движок не тратил время впритык и для учета подобных задержек оставлял немного времени. Таким образом, я исправил проблему, и просроченного времени больше не наблюдалось :)

Оказывается, есть еще большой простор для улучшений :) Например, я смог улучшить логику вытеснения элементов из хэш-таблицы (коммит). Казалось бы, изменение довольно скромное — а дает примерно 15 Эло — не сильно меньше, чем пешки, зато значительно проще в написании :)

Вот вывод BattleField'а:

Wins: 1940, Loses: 1723, Draws: 1337
Score: 2608.5:2391.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 = 6.85/15.09/23.35 (low/avg/high, at p = 0.95)

Что я понял из этого? Во-первых, очень важно вовремя удалять из хэш-таблицы старые записи. Если не удалять их вообще или удалять неэффективно, то время значительно проседает, и можно потерять до 100 Эло. Во-вторых, не стоит класть в хэш-таблицу позиции без известного лучшего хода. Оказывается, главная роль хэш-таблицы не в том, что она может вернуть точный результат, а в том, что она хранит хороший ход в позициях, и сильно помогает таким образом сортировке ходов. А от сортировки ходов уже напрямую зависит скорость альфа-бета поиска

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

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

Итак, для статической линковки нам, во-первых, понадобится убедиться, что все зависимые библиотеки линкуются статически. Во-вторых, нужно передать флаги компилятору:
- в случае GCC/Clang нам поможет -static (но есть еще нюансы, о которых ниже)
- в случае MSVC мы можем собрать со статическим рантаймом, используя флаг /MT (вместо /MD, если бы мы хотели собирать с динамическим рантаймом, т.е. зависеть от установленного msvcrt в качестве DLL)

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

Во-вторых, сборка под GCC с -static проходила успешно, но движок начинал падать. Это проблема pthreads и статической линковки, и ее решение объяняется здесь. Если коротко — при компиляции создаются слабые ссылки на символы из pthreads, поэтому pthreads не линкуется в итоговый бинарник, и вместо адресов функций в итоге оказываются нули, откуда и получаем падение. В качестве фикса можно дописать флаги -Wl,--whole-archive -lrt -lpthread -Wl,--no-whole-archive. Интересно, что если не дописать -lrt, то код упадет в самом начале, на вызове pthread_self(). Но pthread_self() объявлен не librt.a, а в libc.a! А его добавление лишь заставляет pthread_self() появиться в итоговом бинарнике, поскольку librt.a содержит ссылку на этот символ

Далее возникла проблема с MSVC: надо во флагах сборки заменить везде /MD на /MT. В самом SoFCheck'е это оказалось сделать нетрудно. Труднее оказалось проделать то же самое во всех зависимостях, поскольку я не могу просто так взять в них CMakeLists.txt и поменять там флаги. Пришлось написать файл перегрузок, и для каждой зависимости дописывать что-то вроде -DCMAKE_USER_MAKE_RULES_OVERRIDE=StaticLink.cmake

Еще проблема: CMake хочет искать динамические библиотеки, а не только статические. В частности, при сборке Google Benchmark он захотел зависимость от динамической библиотеки librt.so, что вызывало ошибку линкера. Пришлось в файле перегрузок запретить ему искать динамические библиотеки

Наконец, статическая сборка под macOS оказалась очень затруднительна, поэтому на этой платформе я не выставляю -static

Итого: статическая сборка с CMake — это ад, и требуется много работы руками, чтобы ее завести

Еще я добавил в движок эвристику под названием Razoring, и получил ~40-60 Эло на этом. Потом еще получил ~20 Эло на том, что поменял коэффициенты для Futility Pruning

Эти две эвристики довольно похожи. В альфа-бета поиске нам важно найти либо точную оценку позиции, если она лежит между значениями alpha и beta, либо сказать, что оценка меньше alpha, либо сказать, что она больше beta (в последних двух случаях нас не интересует точное значение). Так вот, в Razoring мы говорим, что если у нас сейчас все плохо (т.е. статическая оценка меньше alpha - margin), то мы считаем, что не можем ничего улучшить, и возвращаем alpha. Аналогично во Futility Pruning, только там мы проверяем beta + margin и возвращаем beta

Возникает закономерная идея, как можно подобрать коэффициенты для этих эвристик. Идея простая: не отсекаться на самом деле, а запускать вместо этого анализ дальше, чтобы проверить, вернул ли бы точный поиск значение, меньшее alpha в этой позиции. Затем записываем результат такой проверки вместе со значением alpha - value (здесь value — значение статической оценки, т.е. мы таким образом записываем минимальное значение margin, которое привело бы к отсечке). Далее мы обучаемся на записанных значениях, чтобы найти приемлемое значение margin. Его следует подбирать так, чтобы отсечение срабатывало достаточно часто, но при этом число ложных срабатываний было бы минимально. Выглядит как обучение классификатора, который выдает 0 или 1 в зависимости от правила value <= alpha - margin. Я пока эту идею не пробовал, но, возможно, когда-нибудь дойду до нее