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

Планирование

Идея проста. Дана шахматная позиция и несколько допустимых ходов, нужно отсортировать их от самого сильного до самого слабого и затем проверить, правы ли вы. Для реализации этой идеи нужны были данные, которые предоставляют шахматную позицию (по её FEN) и несколько допустимых ходов, которые можно сортировать. Нужен сервер, который будет обслуживать эти данные. И, конечно, интерфейс.

Подготовка данных

Ручное создание позиций и допустимых ходов для игры было бы трудоёмким, поэтому использовать случайный выбор было бы не лучшим вариантом. Вместо этого у нас была возможность воспользоваться открытой базой данных Lichess.org. База головоломок предоставляет 4,062,423 интересные позиции, которые уже были сгенерированы! Кроме того, мы получаем полезные метрики, такие как отклонение рейтинга, популярность и количество сыгранных партий. Они помогут нам отфильтровать результаты и выбрать наиболее интересные и проверенные позиции.

Мы решили использовать 4 хода в игре, так как это создаёт оптимальный баланс сложности — 2-3 хода не представляют особой сложности и не являются интересными, а 5 ходов — это уже слишком много. Также нам нужно было, чтобы в каждой позиции было хотя бы 4 допустимых хода, чтобы создать игру. Однако, если бы у нас было больше допустимых ходов, мы могли бы создать больше игр, так как могли бы выбрать любые 4 различных хода из набора. Мы решили использовать 50 лучших ходов для каждой позиции. Нас не интересуют ходы, которые выходят за рамки топ-50, так как они не представляют интерес для сортировки.

Следствием этих решений стало то, что для каждой позиции мы могли бы генерировать огромное количество игр. Используя формулу сочетаний, из одной головоломки можно создать 230,300 различных вариантов сортировки! Это означает, что нам не нужно обрабатывать большое количество головоломок из открытой базы данных Lichess, чтобы получить большой пул игр. Не каждая игра окажется интересной, конечно. Сортировка случайных ходов, таких как 33-й, 34-й и т.д., будет бессмысленной и неинтересной, поэтому мы будем опираться на хорошую стратегию генерации игр (подробнее об этом позже).

Данные головоломок включали только последовательность лучших ходов для каждой задачи. Это означало, что нам пришлось генерировать их самостоятельно. Мы решили использовали Stockfish — мощный открытый шахматный движок — по одной простой причине: он сочетает в себе два моих главных увлечения (акции и рыба). Stockfish поможет нам анализировать каждую позицию и генерировать до 50 сильнейших допустимых ходов, а также их оценку (насколько силён ход, если его сделать).

Stockfish чрезвычайно настраиваем. Изменение его параметров может привести к различным результатам для допустимых ходов. Мы решили сгенерировать данные заранее, так как реальная генерация занимает слишком много времени. Мы учли тот фактор, что в будущем нам возможно придётся обновить данные. И решили сделать это с возможностью контроля, чтобы легко переписывать строки в нашей базе данных и т. д. Наш подход заключался в том, чтобы преобразовать входные данные Lichess в данные Chessort в виде блоков — каждый блок представляет собой определённое количество обработанных строк из CSV данных Lichess. Мы решили использовать блоки по 1000 строк. Таким образом, независимо от количества отфильтрованных строк и параметров, каждый блок всегда представляет одинаковое количество строк. Вот как выглядят метаданные для примера блока:

{
    "stockfishVersion": "16.1",
    "offset": 1700000,
    "limit": 1000,
    "evaluationDepth": 25,
    "multipv": 50,
    "minimumMovesRequired": 4,
    "minPopularityRequired": 90,
    "minNumberPlaysRequired": 100,
    "maxRatingDeviation": 100,
    "inputLichessFileSha256": "a480b5c25389d653800889bcf223d32a622249bd3d6ba3e210b8c75bc8092300",
    "outputFileSha256": "a32d9fa120f36b32b9df1be018794af9c3384ca32d1c1305dc037fd6e53c1afb"
}

Примечания:

• Мы используем глубину оценки 25 для достаточно точного результата, подходящего для аналитических игр. Диапазон от 20 до 25 является здесь подходящим.

• Каждый блок размером 1000 строк занимает примерно 70 минут на моём компьютере (24 потока, 64 ГБ ОЗУ на процессоре Ryzen 3900X).

• SHA256 хеши сохраняются как метаданные, чтобы обеспечить воспроизводимость.

• Популярность 90+, более 100 сыгранных партий и максимальное отклонение рейтинга до 100 показали, что такие игры очень интересны и востребованы.

База данных

Наша база данных — это простой кластер MariaDB, который уже используется для других проектов. Мы используем скрипт для загрузки данных Chessort из CSV.

Единственное, на что стоит обратить внимание: мы преобразуем относительные оценки движка в глобальные в процессе загрузки данных. Например, если в нашем входном CSV оценка хода была #1, а ход был за чёрных, мы храним это как #-1. Таким образом, каждая оценка в базе данных отображает глобальное значение.

Бэкенд (сервер)

Для работы серверной части использовался Flask. Сервер отвечает за генерацию игр, их предоставление и проверку решений.

В этой части возникли две интересные проблемы:

• Генерация игр

• Оценка сложности для людей

Генерация игр

Генерация игр — ключевая часть проекта. Допустим, у нас есть 1 позиция и 50 ходов. Если мы просто выберем любые 4 разных хода, игра получится скучной. Скучные игры — это те, где все ходы исключительно плохи, поскольку в шахматах не полезно анализировать только ужасные ходы. В шахматах цель — постоянно находить лучший ход. Например, такие оценки: -1234, -1322, -1832, -2011.

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

Для создания интересной игры важно обеспечить разнообразие среди выбранных ходов. Нам нужно выбирать как сильные, так и слабые ходы. Некоторые ходы должны быть хороши для игрока на очереди, а некоторые — плохи и так далее. Конечно, можно настроить параметры выбора, чтобы генерировать игры различной сложности.

Эту игру можно сделать очень простой: #1, +500, -500, -1, где большинство игроков найдёт мат в 1 и затем сможет отсортировать оставшиеся 2 хода в зависимости от того, какой из них лучше для игрока на очереди.

Для решения задачи генерации игр мы создаём общий интерфейс MoveSelectionStrategy, который выглядит так:

class MoveSelectionStrategy:
    def select_moves(self, moves: list[Move], num_required_moves: int) -> list[Move]:
        raise NotImplementedError("This method should be implemented by subclasses.")

    def can_handle(self, moves: list[Move], num_required_moves: int) -> bool:
        if len(moves) == 0 or num_required_moves <= 0:
            return False
        if num_required_moves > len(moves):
            return False
        return True

Теперь мы можем создавать различные стратегии, которые принимают набор ходов и генерируют требуемое количество ходов в качестве результата. Каждая стратегия имеет метод can_handle, который определяет, сможет ли она произвести допустимый результат, и метод select_moves для создания результата.

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

Сейчас используются две стратегии:

• Стратегия Top Spread: выбирает лучший ход, а затем следующие 3 лучших хода с минимальной нормализованной разницей оценок.

• Стратегия случайной генерации: используется в качестве запасного варианта, если все остальные стратегии не подходят (эта стратегия гарантированно сработает).

Оценка сложности игры для человека

Ещё одна интересная задача — оценка сложности игры. Дана позиция и набор ходов, как оценить, насколько сложно человеку отсортировать эти ходы?

Предполагаем, что люди могут сортировать ходы, когда разница между ними очевидна. В шахматах человек должен отличать мат в 1 (#1) от мата в 2 (#-2), но различить +450 и +420 будет трудно. Поэтому важна разница в оценках силы ходов.

Вот как оценивается сложность сортировки разных типов ходов, от самого лёгкого до самого сложного:

• Мат и центипаун (например, #1 и +200)

• Мат и другой мат (одинаковая сторона) (например, #1 и #4)

• Центипаун и другой центипаун (например, +400, +50)

После консультаций с участниками сообществ Lichess и разработчиками Stockfish на Discord я смог разработать решение. Отметим, что решение ещё находится в разработке и будет улучшаться со временем.

Обзор решения

Решение состоит в преобразовании значений мата в диапазон [0, 0.5]. Для этого мы передаём значение мата (например, 1, 2, 3 и т. д.) в сигмоидную функцию. Сигмоидная функция принимает входные данные из диапазона [∞, -∞] и нормализует их в диапазон [1, 0]. Функция экспоненциальна, поэтому значения в середине (0.5) более разнообразны, чем значения на границах (1 и 0). После получения значений мата для белых и чёрных в диапазоне [0, 0.5], мы сдвигаем их: для белых — в диапазон [1.5, 0.5], для чёрных — в диапазон [0, -0.5].

Значения центипауна также пропускаем через сигмоидную функцию. Это преобразует все значения центипауна (положительные или отрицательные) в диапазон [1, 0].

• Ходы мата становятся экспоненциально ближе по мере удаления от мата в 1 (#1).

• Ходы с центипауном становятся экспоненциально ближе по мере удаления от нейтрального значения (0).

Мы объединяем эти списки, сначала добавляя маты для белых, затем центипауны, и в конце — маты для чёрных. Этот список затем нормализуется с помощью линейного масштабирования в диапазон [1, 0]. Это даёт нам нормализованные оценки силы каждого хода.

Сравнение сложности

Чтобы оценить, насколько сложно человеку отсортировать эти значения, мы находим соседние различия. Чем больше соседнее различие, тем легче сортировать (поскольку разница между оценками больше). Существует особый случай для соседних различий, равных 0. Значение 0 указывает на одинаковую силу хода, и такие случаи исключаются (поскольку в нашей игре, если два хода имеют одинаковую силу, мы принимаем любую их сортировку, что значительно упрощает игру).

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

Финальная шкала сложности

Затем мы берём этот результат и помещаем его в диапазон [0, 100], получая числовое значение, которое представляет собой сложность.

Важно отметить:

• Сравнение центипаунов будет ограничено диапазоном от 50 до 100.

• Сравнение центипауна с матом будет ограничено диапазоном от 25 до 100.

• Сравнение мата с матом одной стороны будет ограничено диапазоном от 75 до 100.

• Сравнение #1 и -#1 даёт минимальное значение — 0.

Таким образом, мы группируем итоговую сложность в экспоненциальные диапазоны:

def map_difficulty(difficulty):
    if not (0 <= difficulty <= 100):
        raise ValueError("Difficulty must be within the range of 0 to 100.")
    
    if difficulty < 50:
        return Difficulty.BEGINNER
    elif 50 <= difficulty < 75:
        return Difficulty.EASY
    elif 75 <= difficulty < 87.5:
        return Difficulty.MEDIUM
    elif 87.5 <= difficulty < 95:
        return Difficulty.HARD
    else:
        return Difficulty.MASTER

Это отображение помогает классифицировать уровень сложности игры для игроков, обеспечивая сбалансированный и увлекательный опыт.

Фронтенд (Приложение)

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

Как мы все знаем, Paint — это лидер в индустрии макетов дизайна. Также всем известно, что мои дизайнерские навыки непревзойденны, благодаря им и родился сей шедевр. Посмотрите на изящную окраску шахматной доски, на изысканное несовпадение карт. О боже, тут есть даже красные стрелки!

В любом случае, дизайн прост: адаптивный двухколоночный макет для игры, где шахматная доска расположена слева, а панель — справа. Панель будет содержать карты для сортировки, и сортировать карты вы будете методом перетаскивания (drag and drop). Как только вы отправите свой ответ, карты покажут, какие из них правильные, а какие — неправильные. Также будет показана такая важная информация, как оценка силы хода движком и общая позиция хода. Вот и всё!

Для разработки фронтенда мы выбрали React, Vite, SWC и TypeScript. Наша цель — создать легковесный и быстрый сайт, поскольку для этого не требовалось много ресурсов. Хотя, будучи перфекционистом, я потратил много времени на улучшение различных аспектов сайта.

Мы внесли несколько полезных изменений в дизайн и функциональность:

• Объединили кнопки отправки и следующего хода в одну.

• Добавили панель действий для полезных операций.

• Добавили поддержку клавиатуры для улучшения доступности.

• Добавили предварительный просмотр ходов (выбор карты отображает ход на шахматной доске).

• Добавили счётчики попаданий (сколько раз игра и позиция были сыграны).
  Поддержка полной отзывчивости (для каждого возможного размера экрана).

• Поддержка WebKit (да, у него своя категория).

Работа над фронтендом шла довольно гладко, за исключением поддержки WebKit. Я потратил много времени на отладку ошибки рендеринга SVG для WebKit, из-за которой фигуры становились чёрными при некоторых перерендерах. Вы можете увидеть воспроизведение этой ошибки в этом PoC на Codesandbox. Это оказалась старая ошибка в WebKit, которая проявлялась на единственном устройстве iOS, которое я использовал для тестирования — моём iPad. Обновление iPad до последней версии iOS решило проблему. Важный вывод здесь — всегда обновляйте свои тестовые устройства!

Заключительные мысли

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

Кроме того, если вам интересен код, лежащий в основе Chessort, вы можете ознакомиться с открытым проектом на GitHub. Chessort лицензирован по GPL, и вклад всегда приветствуется.

Если вы дочитали до этого места — вам, скорее всего, интересно, как устроены хорошие технические решения: от алгоритмов до архитектуры, от UX до реального кода. Возможно, вы сами сталкивались с похожими вызовами — как отсеять шум, как сделать продукт не только умным, но и удобным, как не утонуть в деталях при разработке. Если знакомо — вот три урока, которые могут попасть в точку.

• 1 июля — Шик, блеск, чистота: clean architecture в Python
  урок будет интересен любым инженерам в силу универсальности концепции

• 3 июля — Анализ сложности алгоритмов и сортировка на C#
  научитесь анализировать производительность кода и избегать неоптимальных решений

• 8 июля — Как быстро освоить Vue, если уже знаешь JavaScript
  разберём, как написать интерфейс, который реагирует на действия пользователя

Все открытые уроки на самые актуальные темы в IT можно посмотреть в календаре.