Еще хотел показать, как я красиво порефакторил модуль 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 :)

Включил комментарии в канале :)

Скоро выложу и пару новых постов

Немного расскажу про то, как мне удалось запустить своего бота на Lichess

Часть информации про это можно найти в посте от создателей Lichess. Если коротко, то есть два варианта:
- либо самому ходить в API Lichess и написать для этого код
- либо воспользоваться готовой прослойкой на питоне, к которой можно подключить движок на XBoard/UCI, немного поправить конфиг и позволить ему таким образом играть на Lichess

Но сперва надо создать аккаунт. Для этого надо зарегистрироваться как обычный игрок, а затем вызовом API сконвертировать свой аккаунт в бота. Забавно что при регистрации написано «Создание учётных записей для ботов запрещено» :)

Дальше нужно найти ненужный компьютер (или виртуалку в облаке), чтобы запустить бота. Конкретно SoFCheck работает в облаке на 2 CPU и 2 ГБ памяти. А это значит, что он может играть до двух игр одновременно, с хэш-таблицей на 512 МБ (больше я не стал ставить, чтобы был резерв по памяти)

После этого достаточно сгенерировать себе токен для доступа к API Lichess, сконфигурировать прослойку и смотреть за игрой :)

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

Сейчас у движка такие настройки:
- не более двух игр одновременно
- однопоточный режим (я пробовал ставить его в два потока и не более одну игру одновременно, но это не усилило игру)
- принимает любые игры с не более чем 15 минутами на партию и не более чем 30 секундами добавления (т.е. умеет играть в Bullet, Blitz и Rapid)
- время от времени предлагает партию случайным ботам (с контролем 5 минут + 3 секунды на ход). При этом подбирает лишь ботов с рейтингом от 1800 до 2400, чтобы игры получались интереснее

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

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

Еще одна проблема — selftest полагается на функцию наподобие is_cell_attacked, которая проверяет, правда ли поле пробивается противником. В крейте chess такой функции не оказалось (там есть только проверка на шах королю), поэтому пришлось дописать ее руками, а также добавить возможность собрать selftest без использования этой функции

Как я писал выше в канале, selftest позволяет запускать произвольный код для каждой доски, чтобы можно было проверять всякие внутренние инварианты. Эта возможность теперь есть и в owlchess :)

Еще один шаг: добавил запуск selftest'ов в CI, чтобы при коммитах убеждаться, что я не поломал реализацию. В CI все работает просто: я скачиваю репозиторий chess_bench (в котором и реализован selftest), подменяю пакет owlchess на локальный и запускаю тесты. Правда, selftest'ы бегут примерно 12 минут (в SoFCheck'е, напомню, они работали примерно 5 минут). И дело не в том, что Rust принципиально медленнее: просто owlchess проверяет больше инвариантов. Например, он пробует сконвертировать все ходы в SAN и обратно, чтобы убедиться, что чтение и запись SAN — взаимообратные операции

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

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

Увы, я обнаружил, что в 15 августа SoFCheck на Lichess'е ничего не играл, потому что lichess-bot упал. Я его переподнял и настроил себе алерты, чтобы в следующий раз узнать о падении более оперативно

UPD: завел баг-репорт по мотивам прошлого падения

Интересный факт: GitHub умеет парсить Cargo.toml для Rust и понимать, кто использует какие репозитории в качестве зависимостей. Так я узнал, что у моего owlchess появились пользователи, кроме меня :) Первому пользователю я вручил pull request с исправлениями, которые делают использование owlchess более простым и идиоматичным

Пока с SoFCheck не происходит ничего нового. Но у меня появился второй канал @gepardchan, в котором я рассказываю про все остальное

Подписывайтесь :)

Я временно остановил бота на Lichess. Возможно, я через какое-то время найду ему новую виртуалку и запущу опять, но пока что будет так.

За все время работы (около 5.5 месяцев) SoFCheck наиграл 11'000 игр. Все эти партии сохранились, поэтому будет на что смотреть и на чем обучаться :)

Потратил несколько дней на оптимизацию правил. В итоге практически никакого улучшения в силе игры не вышло: все улучшения либо ничего не давали, либо усиливали игру только на очень низком контроле времени (50мс на ход)

Оптимизации было три:
1) написать отдельный генератор для случая, когда мы под шахом. Идея в том, что в этом случае генерится очень много нелегальных ходов, и их количество хочется уменьшить. Это дает профит на маленьком контроле времени, поэтому я решил оставить
2) сейчас мы сначала делаем ход, а потом проверяем, что король не оказался под боем, и откатываем, если это не так. Получается, что на невалидный ход мы потратили много времени, потому что провернули moveMake() и moveUnmake(). Хотелось сначала проверять, не окажется ли король под шахом, а после этого делать ход. Эта оптимизация тоже не полетела, и я ее решил не вливать. Хотя на бенчмарках результаты такие же, как и без нее
3) при проверке на шах можно сразу проверить, что слона, ладьи или ферзя нет на одной линии с королем и не делать более дорогостоящие проверки. Это хорошо ведет себя на бенчмарках и на играх с контролем в 50мс на ход, но на большем контроле ничего не заметно

Параллельно оптимизации 2) и 3) поехали в owlchess (шахматную библиотеку на Rust). Правда, там они показали себя на бенчмарках странно: на части позиций вышло улучшение, на части — ухудшение :(

В общем, оптимизация генератора ходов — это не то место, где можно выбить большой плюс к рейтингу