И все-таки я добавил 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. Я пока эту идею не пробовал, но, возможно, когда-нибудь дойду до нее

Сделал первый релиз движка:
https://github.com/alex65536/sofcheck/releases/tag/v0.9-beta

Потестировал SoFCheck против других движков в режиме «200 партий, контроль времени — 5 минут на 40 ходов». Результаты оказались такие:

Против Ifrit (2413 Эло по версии CCRL):

Wins: 93, Loses: 44, Draws: 63
Score: 124.5:75.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 = 47.35/86.89/128.78 (low/avg/high, at p = 0.95)

Против GreKo 2015 (2608 Эло по версии CCRL):

Wins: 50, Loses: 91, Draws: 59
Score: 79.5:120.5
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 = -114.39/-72.25/-32.11 (low/avg/high, at p = 0.95)

Отсюда получаем, что рейтинг SoFCheck'а на CCRL должен быть примерно равен 2500 Эло. Каков он на самом деле — мы узнаем только тогда, когда его протестируют на CCRL и добавят в рейтинги, а это может произойти не очень скоро

Не так давно я отправил SoFCheck на CCRL — это сайт, посвященный тестированию различных шахматных движков. Пора рассказать в связи с этим несколько новостей

Во-первых, SoFCheck получил рейтинг в блице (контроль времени — 2 минуты на 40 ходов). По результатам 411 партий рейтинг составил 2437 Эло (таблица). Получилось близко к тому, что я ожидал :)

Во-вторых, сегодня на CCRL начался турнир, в котором участвует SoFCheck. Это первый турнир с участием моего движка. Вот ссылка на список партий, которые будут сыграны в турнире. Есть еще ссылка на трансляцию, куда можно заходить и смотреть :)

Недавно завершился первый турнир с участием SoFCheck'а, и мой движок выиграл в нем :)

Турнир проходил между десятью движками, каждый сыграл с каждым по четыре партии: две белыми и две черными. Итого 36 партий для каждого движка. За победу присуждалось 1 очко, за ничью — 0.5, за поражение — 0

Результаты такие:
26.0 - SoFCheck 0.9-beta 64-bit
22.5 - Isa 2.0.83 64-bit
20.0 - EveAnn 1.72
20.0 - Prophet 4.1 64-bit
18.0 - FireFly 2.7.2 64-bit
17.5 - Barbarossa 0.6.0 64-bit
16.5 - Tantabus 1.0.2 64-bit
14.5 - Admete 1.3.1 64-bit
14.0 - Matilde 2008 64-bit
11.0 - Absolute Zero 3.3.2.0 64-bit

Еще хотел показать, как я красиво порефакторил модуль search. Вся его публичная часть теперь состоит из одного заголовочного файла search/search.h (ссылка), в котором находится одна-единственная функция:
std::unique_ptr<SoFBotApi::Client> makeEngine();
А все детали реализации скрыты за интерфейсом SoFBotApi::Client, который просто содержит команды UCI в виде функций

Выпустил следующий релиз, поправил пару багов, проделал пару рефакторингов:
https://github.com/alex65536/sofcheck/releases/tag/v0.9.1-beta
В новом релизе только исправления проблем, без улучшения силы игры

Начался следующий турнир с участием SoFCheck. Правила почти такие же, как и в прошлом: каждая программа играет с каждой по два раза, контроль времени — 15 минут на 40 ходов. Смотреть за ходом игры можно по ссылке

Пока сам SoFCheck не развивается, но вокруг него происходят интересные вещи

Я планирую переписать battlefield — это программа для запуска игр движков друг с другом и сбора всяких разных статистик, чтобы определить, какая из них сильнее. Текущая версия написана на Pascal с не очень быстрой реализацией правил, а ожидание ответа от движка в ней выглядит как Sleep(1); до тех пор, пока на пайп не поступит что-то полезное. Не очень хорошо

Я решил, что программа на замену battlefield будет написана на Rust. Первым делом я поискал крейты (так называются пакеты в Rust), которые реализуют правила шахмат и основную шахматную функциональность. Выбор пал на два крейта: chess и shakmaty. Оба крейта в целом работают, а shakmaty даже реализует много разных вариантов шахмат. Хотя, chess мне не подходит тем, что он не умеет выводить ход в виде SAN, что требуется для экспорта в PGN. Но оба крейта не очень хорошо позволяют понять причину конца игры: т.е. я могу из крейта просто получить, что на доске стоит ничья, но не могу понять, была ли это ничья из-за правила 50 ходов или из-за пата. А еще shakmaty хранит только саму доску без истории ходов, и поэтому проверку на троекратные повторения пришлось бы писать в отдельной обертке над этим крейтом

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

Как я уже упоминал выше, в основе owlchess лежит реализация правил из SoFCheck. Есть, конечно, и отличия, в первую очередь в плане безопасности. В SoFCheck реализация правил полагается, как принято в мире C++, на прямые руки программиста: ты должен сам убедиться, что сделал все правильно, иначе словишь UB. В Rust идеология радикально иная: необходимо писать API так, чтобы их нельзя было использовать неправильно. Поэтому в owlchess довольно много интересных оберток: примитивы cell_t, coord_t и bitboard_t из SoFCheck превратились в структуры Cell, Coord и Bitboard, которые не дадут присвоить в них невалидное значение. Еще добавились дополнительные гарантии:

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

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

Еще в owlchess есть типы, очень полезные для переписывания battlefield. Например, MoveChain, который может держать список всех ходов партии, экспортировать его в строку (как в виде ходов для передачи движку по UCI, так и в виде PGN) и проверять на ничью путем повторения ходов. Или Outcome, который исчерпывающе описывает, как закончилась партия

Что насчет производительности? Если использовать unsafe в owlchess, то он по скорости примерно равен реализации правил в SoFCheck (а применение хода почему-то получилось даже чуть быстрее). Если использовать safe, то все чуть хуже: валидация хода перед его применением замедляет все в 1.5-2 раза. Но в остальном можно смело утверждать, что Rust не уступает по производительности C++

Теперь расскажу про то, как я тестировал свой крейт и сравнивал его с остальными

У автора chess есть бенчмарки, на которых он с помощью perft (т.е. подсчета числа позиций при рекурсивном запуске на фиксированную глубину) на разных позициях сравнивает скорость chess и shakmaty и заявляет, что у него реализация быстрее. При этом сами бенчмарки написаны ужасно: там 27 позиций и 27 × 2 бенчмарка, причем для каждой из реализаций бенчмарк почти полностью повторяется. Таким образом, чтобы в этот бенчмарк добавить новую реализацию для сравнения, мне надо скопировать 27 функций и немного из поменять. Неудобно :(

И здесь я написал свои бенчмарки, в которых все устроено проще: отдельно описаны таблицы с позициями и правильными ответами, а отдельно одна функция гоняет эти бенчмарки аж по пяти реализациям (включая chess, owlchess и shakmaty). К счастью, крейт criterion для бенчмарков не требует, чтобы каждый отдельный бенчмарк был функцией, поэтому все получилось очень кратко и красиво

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

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

Как в движках, так и в шахматных оболочках такая отложенная валидация проблемы не должна представлять: невалидные ходы встречаются редко, и их применение не сильно ухудшает время работы. Зато сам псевдолегальный генератор быстрее и проще, чем легальный. Но на бенчмарке с perft'ом легальный генератор работает быстрее, потому что там на последней глубине можно просто сгенерировать список всех легальных ходов, а не пытаться применять все ходы по одному. Поэтому полностью легальные генераторы из chess и shakmaty победили у owlchess с большим отрывом

Лечения проблемы здесь оказалось два:

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

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

Во-вторых, я придумал и добавил бенчмарк hperft (honest perft, hash perft), который позволяет псевдолегальным генераторам соревноваться на равных. А именно, в hperft надо не только вычислить количество позиций на заданной глубине, но и учесть некоторую сумму хэшей от этих всех позиций. Точные формулы можно посмотреть в коде. Нетрудно видеть, что hperft не дает срезать количество действий на последней глубине, а заставляет честно применять и отменять ходы

На hperft результаты owlchess и chess сравнялись, а вот shakmaty оказался быстрее их всех. Скорее всего дело в том, что у там лучше написан make_move, и в том, что в shakmaty по умолчанию не пересчитывается zobrist-хэш (а для этого существует отдельная обертка. Тем не менее гипотеза подтвердилась: псевдолегальный генератор действительно смог себя хорошо показать :)

Правда, hperft очень сильно перекошен в сторону make_move, и больше отражает время работы этой функции, а не собственно генерации ходов. По этой причине у меня в планах добавить приближенный к действиям реального движка бенчмарк: у каждой доски из всего множества ходов детерминированно и вне зависимости от их порядка выбираем 4-5 из них, и делаем рекурсивный спуск только с этими ходами

Сейчас проходит очередной турнир с участием SoFCheck, можно заходить и смотреть :)

Есть также текущие результаты и расписание игр

UPD: итоговые результаты турнира

Хорошая новость: теперь с SoFCheck'ом можно сразиться на Lichess :)