Это первая часть цикла статей про написание своего шахматного сервера на Go.
В следующих частях будет подробно рассказано про внутреннее устройство сервера: структура кода, работа с базой, инфраструктура.
Сегодня мы порассуждаем об одной из самых древних и знаменитых настолок — шахматах. Что вообще нужно для комфортной игры двух человек по сети?
База данных, где будет храниться информация об играх? Удобный и понятный интерфейс? Движок, подсказывающий возможные ходы? Прежде чем хвататься за код, нужно понять, что (кроме возможности играть на расстоянии в тысячи километров) может дать игрокам вычислительная техника оснащённая соответствующим софтом.
В первую очередь это мгновенный (для человека) анализ ситуации на доске и регистрация состояния игры. Все, кто играл шахматы на реальной доске, знают, что легко бывает (особенно когда игра на время) не заметить шах или даже мат. Но специальная программа делает такого рода ошибки невозможными. Она просто не даст совершить неправильный ход, а результат корректного хода мгновенно зафиксирует.
Предлагаю с этого и начать
Какими основными инструментами для анализа игры нужно вооружить шахматный сервер?
Определимся с тем минимумом, без которого невозможно начать рассуждать об игре. У нас есть шахматная доска и набор фигур двух цветов. Доску мы представим как двумерный массив. То есть каждое поле на доске и, соответственно, каждая фигура будут обладать в каждый момент времени координатами x и y.
Всего в игре 6 разных фигур — пешка, конь, слон, ладья, ферзь и король. Начнём с их общих свойств:
У каждой фигуры есть своё поле на доске (в нашем случае координаты)
У каждой фигуры есть тип (пешка, конь, слон, ладья, ферзь и король)
У каждой фигуры есть цвет (принадлежность конкретному игроку)
Каждая фигура может передвигаться по доске и это передвижение подчиняется одним и тем же правилам вне зависимости от положения фигуры на доске (у этого свойства есть масса оговорок и уточнений, но об этом позже)
Каждая фигура может быть удалена с доски (за исключением короля) или появиться на доске (за исключением короля и пешки)
Фигуры одного типа и цвета одинаковы (за исключением ладьи)
Итак, мы набросали общий набор свойств для любой фигуры, что поможет нам в дальнейшем их грамотно запрограммировать. Теперь рассмотрим нюансы.
Одна из основных задач нашего шахматного сервера — это определить корректность запрашиваемого игроком хода. Ход это всегда перемещение фигуры (в некоторых случаях сразу двух фигур) с поля А на поле Б. Тут для проверки корректности хода нам поможет уже составленный список свойств фигур.
Однако наибольший интерес представляют четвёртый и шестой пункты.
Опишем алгоритмы, которые позволят нам в любой момент времени определить, куда может пойти фигура. Разобьём эту задачу на две.
Поиск возможных ходов без учёта, что в конце этого хода ходящему будет объявлен шах
Проверка возможного хода на состояние шаха игроку, который совершает этот ход
Интересный момент — при игре в шахматы (особенно если играть очень быстро на время) легче всего не заметить возможный ход коня. Он ходит не по прямой, во все стороны, да ещё и не блокируется другими фигурами. Пешка напротив — у неё в моменте, как правило, очень ограниченные возможности и, глядя на доску, сразу понимаешь, какая из них представляет угрозу, а какая нет. Но как только мы попытаемся придумать алгоритм, позволяющий найти возможные поля, куда может пойти фигура, то сразу всё переворачивается с ног на голову.
Как ходят фигуры?
Конь. В этом плане самая простая фигура для анализа. С любой позиции он всегда может пойти на одни и те же 8 полей (относительно положения коня) — нужно лишь прибавить к его координатам 8 констант ( +/- 2 по одной координате и +/- 1 по второй).
Ограничений тут всего два — есть ли такое поле на доске и, если оно есть, не стоит ли на этом поле фигура того же цвета, что и сам конь.
Ферзь. Тут тоже ничего сложного. Есть 8 направлений, по которым может двигаться эта фигура (по горизонтали, вертикали и диагонали). Выбираем направление, и поле за полем проверяем:
1) Есть ли поле на доске. Если нет — переходим к анализу следующего направления
2) Есть ли на поле фигура. Если нет — запоминаем поле, как возможное для хода, и продолжаем двигаться в этом же направлении дальше
3) Если фигура есть и она противоположного цвета (и не король!) — запоминаем поле, как возможное для хода, и переходим к анализу следующего направления
4) Если фигура есть и она одного с ферзём цвета — переходим к анализу следующего направления
Слон. Аналогичен ферзю, но перемещается только по диагонали.
Ладья. Аналогична ферзю, но перемещается только по вертикали и горизонтали. Ещё ладья может участвовать в рокировке, однако это ход короля и проблемы, возникающие с рокировкой, связаны больше с шестым свойством фигур.
Пешка. Вот тут начинается интересное. В моменте пешка очень сильно ограничена по функционалу. Но по суммарному количеству и необычности ходов эта фигура превосходит любую другую.
Прежде чем начинать анализ пешки, мы должны проверить несколько вещей:
— Где пешка находится— Какого пешка цвета
— Последний ход противника
Пешка единственная фигура, у которой перемещение и «атака» происходят по‑разному. Перемещаться можно только по вертикали, только в одну (в зависимости от цвета) сторону, только на одно поле и только если оно (поле) свободно. Но если пешка стоит на своей стартовой позиции, то она может сразу переместиться и два поля (если оба свободны). Это первая причина, по которой мы должны проверять координаты пешки.
Атакует пешка по диагоналям на одно поле в сторону своего движения и только если там есть вражеская фигура.
Если пешка дошла до противоположного края доски (поле в последнем ряду), то она сразу заменяется (на выбор игрока) на слона/ладью/коня/ферзя. Это вторая причина, по которой надо проверять местоположение пешки.
Ну и совсем уже уникальная механика — «взятие на проходе». Тут мы впервые сталкиваемся с необходимостью сохранять информацию о ходе игры. Пешка может «съесть» вражескую, если та предыдущим ходом совершила ход (на две клетки со своей стартовой позиции) через поле, которое бьёт наша (та чей сейчас ход) пешка. О том как и где хранить информацию о состоянии игры и истории ходов, мы поговорим позже, а пока просто отметим для себя этот факт.
Тут же всплывает и ещё одна проблема. До этого любой ход фигуры и возникающие в связи с этим изменения на доске касались только двух полей — откуда был совершён ход и куда. Но при взятии на проходе нам необходимо учитывать ещё и поле, на котором стоит «съедаемая» пешка.
И, наконец-то, Его Величество Король. Неожиданно, но ходит он практически как конь. Тоже всего 8 вариантов куда переместиться, только не буквой «Г», а всего на одну клетку в любую сторону.
Но есть рокировка. И тут мы сталкиваемся с проблемами, которые уже подмечали у пешки. Рокировку можно совершить только королём и ладьёй, которые не двигались до этого, только если между ними нет фигур и только если эти поля (и сам король) не под боем. Сам шах и поля под боем мы рассмотрим потом, а пока отметим пару важных моментов:
— Мы должны как-то запоминать, ходил ли король и ладьи— Ладьи становятся уникальными. Почему? Да потому что если на месте одной не ходившей ладьи окажется другая (ходившая), то её возможности будут отличаться — она не сможет участвовать в рокировке.
Поле под боем или нет?
Теперь поговорим о шахе — состоянии игры, при котором король одного игрока находится на поле, куда может переместиться фигура второго игрока за один ход. Нельзя совершить такой ход результатом которого было бы состояние игры с объявленным тебе же шахом.
Предположим, что мы хотим пойти какой-то фигурой и смогли найти все её возможные ходы. Как нам понять, находится ли под боем король?
Для этого мы находим на доске короля (проверяем, что он нужного цвета). Мы уже знаем, как ходит каждая фигура, а значит нам достаточно проверить каждое из 8 направлений от короля (по вертикали, горизонтали и диагонали). Если фигура, на которую мы наткнёмся на хотя бы одном из направлений, вражеская и может атаковать по этому направлению (например ладья по вертикали), то это состояние шаха — ход невозможен. Аналогично для коня, чьи возможные ходы мы просто накладываем как трафарет на короля и проверяем не находится на одном из получившихся полей вражеский конь.
Ровно всё то же самое мы можем сделать с любым полем — это нам понадобится для рокировки.
Чего же более?
Комбинируя эти алгоритмы мы можем выявить состояния пата или мата — то есть одного из условий окончания игры. Впрочем, возможность сдаться досрочно мы тоже реализуем.
Также нужно отметить, что для полноценной реализации шахматных правил нужно сохранять информацию о повторении позиции на доске (повторилась три раза — ничья) и количестве ходов подряд без взятия фигур (50 ходов — ничья).
Подведём итоги:
У всех фигур есть базовый набор из 6 свойств
Для каждого типа фигуры есть свой уникальный алгоритм поиска её возможных ходов
Есть алгоритм с помощью которого мы можем определить, находится ли поле под боем
Есть некий минимум информации о ходе игры, который мы должны где-то сохранять и к которому должны иметь доступ при анализе ситуации на доске
Всё, теперь мы обладаем необходимой информацией для начала работы. Разумеется, шахматный сервер будет обладать куда большей функциональностью. Однако, его основа — это определение корректности хода.
В следующей части мы коснёмся реализации вышеописанного на Golang.
Ссылки
Проект находится в разработке, буду рад новым идеям и тем, кому было бы интересно заняться фронтовой частью.
В данный момент я ищу работу Golang разработчиком, очень жду ваших сообщений мне в тг: t.me/Gekko_Moria