Эпопея шахматных движков: мой опыт в разработке шахматной программы
Введение
Шахматами я начал заниматься около 3 лет назад, во время громкого матча на первенство мира между Магнусом Карлсеном и Яном Непомнящим. Начиная играть на личесс, а позднее перейдя в игру на живых турнирах — я постепенно погружался в шахматную культуру, изучал стратегии и тактики, анализировал свои партии и стремился к повышению своего уровня игры. В результате я достиг уровня первого разряда и нашел в шахматах не только отдых, но и хобби, которое помогает развивать сосредоточенность и аналитическое мышление.
Будучи около-миддлом в бэкенде — я решил объединить свое увлечение шахматами с навыками программирования и создать движок, который стал бы конкурентоспособной моделью таким движкам как StockFish и Komodo.
Выбор языка
В качестве основного языка программирования — я решил взять TypeScript, это единственный язык с которым я работал на протяжении последних 2 лет.
Дабы усложнить задачу, чтобы этот движок не был для меня очередным пет-проектом (который я заброшу в мусорку через неделю), я решил полностью отказаться от использования внешних зависимостей)
План разработки
Прочитав множество статей на форумах, и изучив код некоторых шахматных движков. Я пришёл к выводу — что поиск лучшего хода в шахматной позиции разбит на несколько этапов:
Оценка позиции
Генерация возможных ходов
Рекурсивный алгоритм поиска ходов, путём перебора самых лучших
Оценка позиции
На этом этапе я начал искать пути реализации метода для оценки текущей позиции и наткнулся на акроним NNUE (Efficiently updatable neural network). Данная нейросеть обучается на огромном количестве сыгранных партий и используется для получения актуальной оценки позиции.
Однако на первых этапах моего проекта я решил обойтись более простыми методами, использовав эвристические данные для оценки позиций. Выглядит это примерно так
const knightScore = [
[-5, -4, -3, -3, -3, -3, -4, -5],
[-4, -2, 0, 5, 5, 0, -2, -4],
[-3, 5, 10, 10, 10, 10, 5, -3],
[-3, 0, 15, 20, 20, 15, 0, -3],
[-3, 5, 15, 20, 20, 15, 5, -3],
[-3, 0, 10, 10, 10, 10, 0, -3],
[-4, -2, 0, 0, 0, 0, -2, -4],
[-5, -4, -3, -3, -3, -3, -4, -5]
]Здесь все просто. Каждый элемент двумерного массива представляет собой клетку доски в формате «h4», т.е в формате обычной шахматной нотации.
В зависимости от расположения коня — к оценке позиции по умолчанию прибавляется значение из эвристических данных. Например если конь находится в центре — к оценке позиции прибавляется »+20». Если же конь стоит в углу доски, то соответственно »-5»
Эвристический подход подразумевает использование набора правил и оценочных функций, которые помогают движку быстро оценивать позиции без необходимости в сложных вычислениях. Это позволило мне сосредоточиться на базовых функциональных возможностях движка.
Генерация возможных ходов
1. Определение цвета стороны. В первую очередь методов должен определить, чья очередь ходить (белые или черные). В зависимости от этого потребуется генерировать только легальные ходы для текущей стороны.
2. Генерация ходов для каждой фигуры. Для каждого типа фигуры (пешка, конь, слон, ладья, ферзь и король) необходимо реализовать свой алгоритм генерации ходов. Каждая фигура имеет свои правила перемещения:
Пешки: осуществляют различные ходы в зависимости от положения (например, движение на одну вперед, преображение в любую другую фигуру, взятие по диагонали, взятие на проходе и возможность хода на две клетки в начале игры)
Кони: двигаются в форме буквы «Г» и могут перепрыгивать через другие фигуры.
Слоны, ладьи и ферзи: перемещаются по линиям (горизонтально, вертикально или диагонально) и могут двигаться на любое количество клеток.
Короли: могут перемещаться на одну клетку в любом направлении и, при необходимости, выполнять рокировку.
Метод так же обязан учитывать также ситуации атаки на короля, шахи, маты и специальные ходы.
Алгоритм поиска ходов
На данном этапе я столкнулся с проблемой, т.к после второй пары ходов (4 полухода) возможно 197 742 различных комбинаций за каждую из сторон — пересчитывать абсолютно все возможные ходы было бы бессмысленно — иначе поиск, даже на самой маленькой глубине, затягивался бы на несколько часов, а то и дней.
Как раз для таких случаев был разработан алгоритм Минимакс с Альфа-бета отсечением.
Алгоритм Минимакс основан на концепции, что игроки действуют в противостоянии (каждый из игроков пытается перетянуть оценку позиции в свою сторону). Основная идея состоит в том, чтобы исследовать дерево ходов, где каждый уровень представляет возможные ходы и реакции противника.
Альфа-бета отсечение — это оптимизация алгоритма Минимакс, позволяющая значительно сокращать количество узлов, которые нужно анализировать в дереве поиска. Она работает следующим образом:
Альфа: самое высокое значение, которое минимизирующий игрок гарантированно сможет получить
Бета: самое низкое значение, которое максимизирующий игрок гарантированно сможет получить
Если во время оценки ходов становится очевидно, что текущий ход не может повлиять на окончательное решение (то есть, оценка не может улучшить альфа или бета), дальнейший анализ этой ветки прекращается, и алгоритм переходит к следующей ветке.
Итог
После корявой реализации всех пунктов, главная функция стала выглядеть так:
const bestMove = findBestMoveFromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", 4);
console.log(bestMove); // { E2: 'E4' } || { D2: 'D4' }.В итоге — мой движок сходу выдал лучший ход первоначальной позиции). В сложных позициях он по прежнему путается (из за неточности эвристик) и выдает некорректные жертвы. Но думаю в дальнейшем это можно пофиксить интеграцией NNUE в метод оценки позиции
В следующей части статьи будут описаны пошаговые действия для внедрения NNUE в мой движок
Надеюсь, вам понравилась эта статья. Буду рад звездам на Github). Всем удачи
