Как мы учили нейросеть играть в шашки для Damka.uz

В первой версии Damka в репозитории лежал файл TODO.md, и первым пунктом там было написано примерно следующее: бот использует минимакс, глубина поиска стоит 3, потому что Python медленный, и это не сильный соперник. Дальше шли два варианта решения: взять готовый движок на C или Go, или сделать ИИ, который учится сам.

Мы в итоге сделали оба. Только на это ушло два года и три архитектуры.

Зачем студии свои шашки

Шашки в Узбекистане играют везде: во дворах, в чайханах, в Telegram-группах. Русские шашки на доске 8×8 с обязательным взятием и «дамкой», которая ходит на любое расстояние. При этом нормальной онлайн-площадки на узбекском у нас не было. Мы решили сделать Damka.uz как свой продукт: играть онлайн, против друга по ссылке и против бота.

Для студии это ещё и полигон. На клиентских проектах экспериментировать с WebSocket-нагрузкой и Rust никто не разрешит. На своём можно.

Три версии за два года

Версия 1: работает, но бот слабый

Первая версия была честной MVP. Партия шла по WebSocket, библиотека pydraughts проверяла правила, бот перебирал ходы минимаксом. Глубина 3 означает, что бот смотрит на полтора хода вперёд с каждой стороны. Любой, кто играет хотя бы во дворе, его обыгрывал. Поднять глубину до 5–6 на Python означало ждать ответа бота по несколько секунд.

Версия 2: свой движок и первая нагрузка

Во второй версии мы выяснили неприятную вещь: встроенный движок библиотеки на русской доске 8×8 работал неправильно. Пришлось писать поиск с нуля: negamax с альфа-бета-отсечением, битборды для оценки, таблица транспозиций, итеративное углубление с бюджетом времени. Всё это выполнялось в пуле процессов, чтобы одна партия с ботом не блокировала остальные.

Заодно появились матчмейкинг на отсортированном множестве в Redis, рейтинг ELO и режим наблюдателя с живой полосой оценки, как на chess.com.

А потом мы запустили нагрузочный тест, и случился главный урок этой версии.

Где на самом деле было медленно

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

Первая мысль была: Python медленный, переписываем. Но процессор при этом был загружен на 50%. Сервер не был занят, он стоял в очереди.

Профилирование нашло три причины. Один процесс Python упирался в GIL и занимал одно ядро из двух. ORM-запросы выполнялись по одному в одном потоке. И соединения с базой открывались заново на каждый запрос, плюс матчмейкинг сканировал ключи Redis через блокирующий KEYS.

Несколько воркеров uvicorn, конкурентный доступ к базе и постоянные соединения дали задержку в 17 мс без единой строчки на другом языке. Если бы мы тогда сразу ушли в Rust, мы бы так и не узнали, что проблема была не в языке.

Почему всё-таки Rust

Если Python справился с нагрузкой, зачем было переписывать? Из-за бота.

Сервер игр на Python нормально перекладывает сообщения. Но поиск по дереву ходов — это миллионы позиций в секунду, и здесь интерпретатор проигрывает компилируемому языку в десятки раз. Вариант «движок на Rust, сервер на Python через FFI» мы обсуждали. Получалось два языка, два деплоя и граница между ними, через которую каждый ход нужно сериализовать.

Мы решили, что движок и сервер будут в одном Rust-бинарнике. Сервер подключает движок как обычный Cargo-крейт, и проверка хода стоит как вызов функции. Тот же движок компилируется в WebAssembly, и браузер может сам показывать допустимые ходы, не спрашивая сервер.

Доска в движке занимает 16 байт: два u64. В них помещаются очередь хода, 32 игровые клетки по 3 бита и счётчик ходов одними дамками для правила ничьей.

Нейросеть вместо ручной оценки

В версии 2 оценка позиции была написана руками: столько-то очков за шашку, столько-то за дамку, бонусы за центр и за продвижение. Такие функции быстро упираются в потолок, потому что человек не может описать всё, что делает позицию хорошей.

В v3 позицию оценивает небольшая полносвязная нейросеть. Она обучалась отдельно, в движке на Go, а в Rust мы перенесли уже готовые веса.

// Вход: 32 клетки, на каждой значение от -K до +K
// (шашка = ±1, дамка = ±K, пусто = 0).
// Скрытые слои с tanh, на последний слой
// добавляется простая сумма материала.
pub const LAYERS: [u16; 4] = [32, 40, 10, 1];
pub const WEIGHTS_LEN: usize = 1280 + 400 + 10;

Сеть маленькая намеренно. Её вызывают на каждом листе дерева поиска, и большая сеть съела бы всю выигранную скорость. В движок вшито десять обученных вариантов сети, всего около 140 КБ. Разные варианты дают разный характер игры, и это удобно для уровней сложности.

В эндшпиле, когда на доске остались только дамки, до пяти штук, движок не думает вообще: он смотрит ответ в заранее посчитанной таблице. Одна запись занимает один байт.

Как мы проверяли, что ничего не сломали

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

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

Шашки в Telegram

Отдельная история — бот @DamkaUzBot. Мы заметили, что люди не хотят «заходить на сайт поиграть». Они сидят в групповом чате и хотят сыграть прямо там. Бот позволяет начать партию в группе и проводить групповые турниры по правилам IDF: жеребьёвка пар, туры, тай-брейки по Бухгольцу. Такие боты мы делаем и для клиентов, подробнее на странице разработки Telegram-ботов.

Что бы я сделал иначе

Первое: профилировал бы раньше. Мы потеряли несколько недель на разговоры о том, что «Python не тянет», хотя он тянул. Проблема была в одном процессе и в одном потоке к базе.

Второе: сразу написал бы набор эталонных позиций. Сначала мы сверяли движки на глаз, играя против них, и это было медленно и ненадёжно.

Третье, и тут я до сих пор сомневаюсь: возможно, не стоило переписывать на Rust весь сервер, а только движок. Сейчас у нас один бинарник и его удобно деплоить, это плюс. Но команде, которая годами пишет на Django, порог входа в Rust-сервер высокий. Если бы Damka был клиентским проектом с поддержкой на годы, я бы оставил сервер на Python. Подробнее о том, как мы вообще выбираем стек, я писал в статье про Nuxt, Next.js и Rust.

Для своего продукта мы могли себе это позволить. И бот теперь обыгрывает меня, чего не мог ни один из его предшественников.