4 угла хорошо, а 6 лучше: гексагональные шахматы в консоли и с ботом

Привет!

Мы учимся на первом курсе бакалавриата «Прикладная математика и информатика» в Питерской Вышке. Во время работы над семестровым командным проектом по С++ мы решили написать компьютерную версию Интеллектора с ботом — шахматную игру на гексагональной доске с особыми фигурами.

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

В нашей команде 3 человека: Юра Худяков, Валера Головин, Миша Саврасов. Для каждого из нас это первый командный проект, так что в процессе работы мы не только писали на плюсах, но ещё и учились работать в команде и пользоваться системами контроля версий (в нашем случае — git). В проекте есть некоторое количество странностей, в частности, велосипедов — есть хорошие готовые решения, которыми можно было бы воспользоваться. Однако цель нашего проекта заключалась в том, чтобы получить опыт, так что многое мы придумывали и реализовывали самостоятельно.

Что такое Интеллектор?

Для начала стоит объяснить, что за игру мы писали.

Игра «Интеллектор» появилась недавно и пока что набирает популярность. В этом году в Петербурге прошел первый открытый чемпионат.

Интеллектор отличается от шахмат структурой поля, правилами и набором фигур. Впрочем, многие элементы похожи: например, в игре есть фигура Прогрессор, которая выполняет роль Пешки. Она ходит только вперёд и может превратиться в другую фигуру, когда достигает крайнего ряда.

Королём здесь выступает фигура, которая называется Интеллектор. Цель игры — срубить эту фигуру, а не поставить ей мат (хотя это почти одно и то же).

Отличия в механике игры возникают из-за специфики поля. Поле Интеллектора симметрично, и это существенно отличает его от шахмат с их королевским и ферзёвым флангами.

Для понимания этой статьи знание правил и умение играть не потребуются.

Общая архитектура

Что мы хотели получить в нашем приложении?

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

Доску нужно вывести на экран и позволить пользователю играть. Этим занимается графическая составляющая игры — интерфейс. В удобном интерфейсе должны быть меню и настройки.

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

План приложения:

1. Логика игры
   • Модель гексагональной доски
     Хранится в виде двумерного массива гексагональных клеток
   • Правила перемещения фигур
     Проверка допустимости хода, получение всех доступных ходов для фигуры, для игрока
   • История ходов
     Отмена и повторение хода
2. Интерфейс
   Планировали 2 интерфейса: ncurses и Qt. В проекте реализован только ncurses, подробнее в разделе Интерфейс.
   • Вывод поля
     Отрисовка и обновление поля в консоли
   • Перемещение курсора клавишами клавиатуры, игра без мышки
   • Отображение текстовой истории ходов
   • Отображение главного меню
3. Бот
   • Случайный бот
   • Жадный бот
   • Альфа-бета бот
     Оптимизировано перебирает все ходы

Как это сделано?

Очень упрощенно архитектуру приложения описывает эта схема:

Раздел Game отвечает за всю игровую логику и хранит доску.

Когда включена игра с компьютером, Game взаимодействует с ботом из Bot

Controller берёт данные об игре из Game и передаёт их в Interface для отображения игрокам. Interface в свою очередь возвращает результат взаимодействия с пользователем обратно в Game через Controller.

Промежуточное звено в виде контроллера пригождается в том случае, когда интерфейсов несколько (изначально мы планировали сделать 2 интерфейса: консольный и графический). Все они единым образом общаются с игрой через контроллер, вместо того, чтобы каждый из них делал это по-своему.

Технические подробности

Модель игры

Гексагональная доска

Рассмотрим раздел Game из схемы выше. Он должен хранить доску и обрабатывать всю внутриигровую логику.

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

Всю доску мы будем хранить в двумерном массиве клеток, элементы которого индексируются парами координат (w,h) как показано на рисунке ниже. Такой выбор координат кажется естественным, но он неудобен для описания перемещения фигур (проследите, скажем, как меняются координаты при перемещении по диагонали).

^{Координаты клеток по горизонтальной оси w и вертикальной оси h}

Для удобства описания перемещения фигур мы будем использовать трехмерные координаты. Выберем некоторую клетку в качестве опорной с координатами {0,0,0} (для удобства она будет совпадать с клеткой (0, 0) массива).

^{Трехмерные координаты клеток относительно центральной клетки с координатами {0,0,0}}

Смещение вдоль диагонали «справа налево, снизу вверх» обозначим координатой x, смещение снизу вверх — координатой y и смещение вдоль диагонали «слева направо, снизу вверх» — координатой z. При переходе в соседнюю клетку соответствующая координата будет меняться на единицу. Таким образом, каждая клетка получает три координаты, как на рисунке выше.

При этом клетки нумеруются неоднозначно. Например, если из центральной клетки с координатами {0,0,0} мы сдвинемся влево вниз, а затем вверх, то получим координаты клетки {0,1,-1}. Но эта же клетка имеет координаты {1,0,0} если прийти в нее напрямую из центральной клетки, как видно на предыдущем рисунке.

^{Другой вариант задания координат клетки {1,0,0}.}

Обход любой клетки по циклу «влево-вниз» — «вверх» — «вправо вниз» приводит нас в ту же клетку, но добавляет к её координатам вектор {-1,1,-1}, сумма координат которого равна -1. Выполняя мысленно такой обход в ту же или в обратную сторону несколько раз, мы можем изменять координаты любой клетки на эквивалентные, которые будут отличаться на вектор, пропорциональный {-1,1,-1}. Чтобы избавиться от неоднозначности, в каждом классе эквивалентности выберем в качестве представителя тройку координат, сумма которых равна нулю. Такой выбор координат является единственным (докажите!).

Опишем далее алгоритм перевода из двумерных координат в трехмерные координаты и наоборот внутри класса Position.

Position(int w, int h) // конструктор из двумерных координат
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { // метод для получения первой координаты двумерного массива
    return -x_ + z_;
}

int posH() const { // метод для получения второй координаты двумерного массива
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

Обратите внимание, что конструктор выдает координаты (x,y,z), сумма которых равна нулю. При этом конвертация координат (x,y,z) в (w,h) работает корректно для любого набора координат (сумма не обязательно должна быть равна нулю).

Как мы нашли все эти формулы? Методом научного тыка: путем анализа изменения трёхмерных координат при сдвиге одной из двумерных координат на 1 (конструктор) и в обратную сторону (методы).

Пользуясь трехмерными координатами, мы легко можем проверить, что клетки лежат на одной прямой. Например, для проверки, что две клетки лежат на одной диагонали z, надо найти вектор, соединяющий эти клетки, и проверить, что в его классе эквивалентности есть вектор вида {0, 0, z}. Z может быть любым — это число дает расстояние между клетками. Очень просто будет реализовывать проверку хода на корректность и находить все клетки, доступные для хода.

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

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

Ходы для фигур

Мы сделали класс FigureMoveValidator, у которого 6 наследников для каждого типа фигуры (можно было обойтись и без наследников, если в каждом методе делать switch case на тип фигуры). Конструктор класса имеет 2 параметра: позиция и ссылка на доску. Также в классе есть два метода allMoves и checkMove.

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

Теперь checkMove. Мы помним, что умеем проверять, лежат ли фигуры на одной прямой. Если проверим, что на этой прямой нет других фигур, то получим готовый метод для Доминатора (аналог ладьи). Если фигуры лежат на одной прямой, то мы можем найти расстояние между ними, и получить методы для Прогрессора (пешка), Дефенсера (ходит как король), Интеллектора (король, только не может рубить) и Либератора (может ходить через одну клетку в любую сторону). Остался еще агрессор (аналог слона), который ходит в клетки по диагоналям в шесть направлений от текущей (из клетки {0, 0, 0} в {0, 1, 1}, в {0, 2, 2} и т.д.: см. серые клетки на картинке ниже). Для этой фигуры можно попробовать обнулить одну из координат и проверить, что оставшиеся 2 координаты равны по модулю (спасибо трёхмерным координатам).

^{Возможные ходы для агрессора}

Теперь надо придумать, что делать с ходами. Создадим класс Move, который будет хранить всю необходимую информацию для хода. Мы решили хранить 2 позиции и 4 фигуры: позицию, с которой ходит фигура, позицию, куда она придет, и информацию о том, какие фигуры стояли в каждой из этих клеток и какие будут стоять после применения хода. Это позволит легко реализовать систему истории ходов и откат ходов.

Интерфейс

Архитектура

Приложение написано на консольной библиотеке ncurses (вот туториал к ней). Эта библиотека позволяет создавать псевдографику в консоли. К примеру, на ней основаны Midnight Commander и Nano.

Выбор может показаться весьма странным: есть много других библиотек, более красивых, удобных и кроссплатформенных. Он связан с тем, что изначально мы планировали сделать 2 интерфейса: консольный и графический. Написать 2 интерфейса к моменту сдачи проекта мы не успели и вместо этого сделали больше фич в консольной версии. Хотя архитектурно приложение всё ещё рассчитано на различные интерфейсы.

Есть 2 основные сущности: отображение и контроллер. Отображения показывают картинку игрокам, а контроллер является посредником между разными отображениями и внутренней моделью игры.

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

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

Вот что происходит, если игрок захочет узнать доступные для хода поля:

1. Игрок перемещает курсор на поле с фигурой и нажимает пробел
2. Поле с фигурой помечается как выбранное
3. Интерфейс обращается к методу selectCell у контроллера
4. Метод selectCell обращается к методу allFigureMoves у модели
5. allFigureMoves создаёт FigureMoveValidator, который вычисляет все доступные ходы
6. allFigureMoves передаёт найденные ходы обратно контроллеру
7. Контроллер передаёт их интерфейсу
8. Интерфейс перерисовывает поле, подсветив доступные поля

^{Курсор находится в середине доски: на бледно-синей клетке. До того, как переместить его в это положение, пользователь выбрал фигуру. Доступные ей ходы подсвечиваются зеленым цветом, а сама выделенная клетка фиолетовым.}

Как рисуется поле?

Консольный интерфейс отрисовывается в прямоугольном окне со строчками текста. Если ставить символы в нужных местах и раскрашивать их, получается картинка:

^{(Злой Пакман, нарисованный буквами «о»)}

Функция move(int y, int x) в ncurses меняет текущую позицию, а функция addch(chtype c) добавляет символ и смещает текущую позицию на 1 вправо (x —> x+1).

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

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

Ncurses позволяет разработчику изменять атрибуты текста при выводе их в консоль (цвет, жирность, мерцание). Для этого в коде пишется:

attron( *attributes* );
addch(c);
attroff( *attributes* );

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

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

В нём хранится текстовая картинка, которую прочитает и выведет игра. Например, фигура, или надпись «White wins»/«Black wins», или кнопка меню. При этом иногда может понадобиться прозрачность, чтобы не перезатирать нарисованное ранее. Для этого можно в первую строчку добавить решётку # и после список «прозрачных» символов, которые будут проигнорированы при выводе.

Например, пусть у нас на экране нарисованы 3 прямоугольника:

Добавим в центр прямоугольник из такого файла:

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

И получим следующую картинку:

^{(жёлтым подсвечено для наглядности)}

Особенно этот формат пригодился при разработке меню.

Меню

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

Кнопки меню читаются из файлов *.btn. На этих кнопках должен быть крупный красивый текст. Красиво рисовать с помощью ASCII символов мы не умеем, зато умеет figlet — утилита для вывода ASCII-текста разными шрифтами:

Кнопки обрамляют надписи, прочитанные из файла:

Затем они центрируются и последовательно выводятся:

В некоторые менюшки можно провалиться и, например, настроить сложность и цвет бота:

Самая интересная часть разработки системы меню — это объединение её элементов в одну систему. Этим занимается отдельный элемент системы, который мы назвали мультиплексор. Название навеяно терминальными мультиплексорами.

Мультиплексор принимает нажатую пользователем клавишу и рассылает её во все отображаемые сейчас меню. Каждое меню само решает, что с клавишей делать: проигнорировать или как-то обработать. Результат обработки меню возвращает мультиплексору, который решает, что делать дальше: закрыть меню, создать новое, изменить настройки, закрыть приложение…

Такой подход оказался удобен для наших потребностей, хотя в общем случае его может не хватить: 2 разных меню могут реагировать на одну и ту же клавишу, и у пользователя должна быть возможность выбрать, какое именно меню должно реагировать. Решением могла бы быть специальная комбинация клавиш, которая бы позволяла переключаться между разными меню. Например, как в tmux. Но это overkill и он не потребовался.

Бот

Как уже упоминалось выше, в нашей игре есть бот. Мы постарались сделать так, чтобы интересно было и новичку, и опытному игроку.

Перед описанием ботов хотелось бы рассказать про некоторые детали реализации. Каждой фигуре мы назначили некоторый вес. Чем он больше, тем ценнее эта фигура. Мы определяем, насколько хорошим является положение на доске, по формуле (сумма весов белых фигур) — (сумма весов черных фигур). Белому игроку выгодно максимизировать это выражение, а черному минимизировать.

Полный просчет всего дерева ходов — слишком сложная задача, поэтому мы просчитывали только первые несколько ходов (забегая вперед, скажу, что получилось просчитать на 6 ходов вперед). Все состояния на доске на определенной глубине мы считали листьями дерева обхода.

Всего в игре есть три разных вида ботов:

• RandomBot — бот делает случайный возможный ход. Создавался для тестирования.
• GreedyBot — бьет самую «дорогую» фигуру противника, а если не может бить, ходит случайно.
• AlphaBetaBot — бот, который использует алгоритм альфа-бета отсечения для выбора лучшего хода в дереве игры.

Когда начали экспериментировать с оптимизациями, мы поняли, что без юнит-тестов для бота обойтись не получится, поэтому создали брата-близнеца для AlphaBetaBot’а, которого назвали OptimizedAlphaBetaBot. Все идеи для оптимизации мы испытывали именно на OptimizedAlphaBetaBot, а юнит-тесты помогали убедиться, что два брата-близнеца находят одинаковый по полезности ход. RandomBot сослужил нам хорошую службу, генерируя случайные расстановки фигур на доске. Для этого достаточно было попросить RandomBot’а сходить несколько десятков раз за обе стороны.

Всего в OptimizedAlphaBetaBot были реализованы 3 крупных оптимизации (здесь они представлены в порядке убывания полезности):

• Использование откатов ходов. После этой оптимизации больше не нужно было множество раз копировать доску, чтобы сделать какой-то ход.
• Написание нового класса с говорящим названием FigureKeeper, который хранит список фигур каждого цвета, которые сейчас есть на доске. Стало возможным обойти один std::vector вместо всей доски.
• Запоминание уже обработанных позиций с помощью std::unordered_map и Zobrish hashing.

Кроме крупных оптимизаций были и более мелкие. Например, если перед сортировкой просчитать все стоимости позиций на доске с учетом определенного хода, то сортировать уже нужно не сложные объекты Move, а просто int’ы.

Изначально планировалось реализовать несколько наборов оценочных функций: например, фигуру, которой угрожает враг, оценивать в половину стоимости. Но оказалось, что бот играет довольно «чисто», теряя мало фигур, поэтому простая сумма оказалась эффективнее.

Однако архитектура бота все еще поддерживает добавление новых оценочных функций. Для этого нужно определить всего три вещи:

1. Функцию, если нужно посчитать стоимость «с нуля» по данному расположению фигур
2. Дельта-функцию, которая должна по данному ходу быстро пересчитать стоимость.
3. Номер этого набора функций для конструктора специального класса FunctionSet.

Можно включить битву ботов и наблюдать за процессом.

^{Игра 2 ботов одинаковой сложности (4 уровень из 6 возможных). Курсор всю игру стоит по центру поля}

Заключение

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

Кроме того, есть разные фичи, которые мы изначально планировали, но к сдаче проекта реализовать не успели. Например, в этом приложении очень хотелось бы видеть сетевую игру. Также не помешал бы красивый кроссплатформенный интерфейс, например, на Qt.

Возможно, в ближайшее время всё или часть из этого появится. А пока что — спасибо за чтение!

Github-репозиторий