IT дуэль 2017: "Битва ботов - Гексагон" создание игры - Часть 1 - Правила

IT duel 2017, Minsk

Итак, мероприятие прошло вполне успешно - драйв, радость побед, горечь поражений, бодрые after-party! Данное соревнование стало очередным вызовом для компании Anadea - год назад мы учились организовывать изолированные турниры по городам, в этот раз провели единовременный турнир в трёх городах, с общим финалом. Смею полагать, вызов был принят достойно :)

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

Любишь программировать? Хочешь работать над интересными проектами в дружном коллективе? Пиши нам на jobs@anadea.info!

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

На самом деле, архитектура игрового движка была создана с нуля год назад, при подготовке Minsk IT duel 2016. Для нынешнего мероприятия, в рамках экспресс курса web разработчиков, интерны реализовали новую игровую механику. Я же - лишь добавил поддержку нескольких песочниц с выходом в финал, возможность играть с собственным ботом онлайн, обновил зависимости (Dokku, заготовки ботов), обновил текст правил, запустил и протестировал песочницы, что-то ещё по мелочи.

В целом, техническая подготовка турнира 2017 была скучна и монотонна, без надрыва - куча времени, скромный объем работ, активная помощь интернов и сотрудников - описывать особо нечего. То ли дело - ...

Cоздание игрового движка год назад!

Всё началось, как водится, с постановки задачи:

Провести бы что-то наподобие хакатона... Кстати, площадка для мероприятия уже забронирована, через месяц...

Что ж, посмотрим, что можно успеть сделать за месяц в одиночку, с эпизодическим привлечением frontend/QA/DevOps специалистов. Задача решалась в привычном режиме "умри, но выполни!" - на кону репутация компании при проведении публичного мероприятия, лажать нельзя.

Commits

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

Правила игры

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

Начало игры

Доступны два типа ходов.

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

Типы ходов - размножение

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

Типы ходов - прыжок

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

Количество доступных прыжков

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

Замена фишки

Игроки ходят по очереди. Если в свою очередь игрок не может походить, не нарушив правила игры - он пропускает ход. Игра заканчивается, когда ни один из игроков не может походить в соответствии с правилами. Побеждает тот игрок, который имеет больше фишек на доске.

Победитель

Чтобы попробовать игру "на вкус", попробуйте сыграть онлайн. В онлайн режиме ходы осуществляются с помощью "перетягивания" мышкой своей фишки на целевую ячейку (Drag&Drop).

Как организовано соревнование

Игрокам предлагается написать бота, умеющего играть (и выигрывать) в описанную игру. Бот представляет собой JSON API веб-сервис. Игровой сервер генерирует карты, сводит ботов в боях друг с другом, следит за соблюдением игровых правил во время боя, и начисляет призовые очки.

Турнир разбит на раунды. В рамках раунда каждая команда сыграет по одному матчу с каждой командой песочницы.

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

Количество очков, которое в результате матча получает бот, зависит от положения соперника в ладдере (сводном рейтинге ботов):

  • 4 очка за победу над соперником выше по ладдеру,
  • 2 очка за победу над соперником ниже по ладдеру,
  • 1 очко за ничью с соперником выше по ладдеру.

Затем, эти очки умножаются на коэффициент, зависящий от размера доски - чем доска больше, тем больше коэффициент.

Как видно, догоняющая команда набирает очки в два раза быстрее, чем команда, уходящая в отрыв.

Каждый из городов (Гродно, Днепр, Минск) будет сражаться в своей собственной игровой песочнице. Призы получат сильнейшие 3 команды в каждом городе.

Также, в конце турнира TOP-3 команды по городам будут помещены в финальную песочницу, где сразятся за супер приз.

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

Как написать бота

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

В запросах POST, PUT и DELETE помимо id в самом урле в теле запроса будет приходить JSON.

Отвечать нужно также JSON-ом, с заголовком Content-Type: application/json.

POST /games – начало игры

В теле запроса придёт JSON с ключами:

  • id [string] – идентификатор текущей игры, например, "asdyhjk43566h".

  • first_turn [boolean] - будет ли бот ходить первым?

  • training [boolean] - прийдёт со значением true, если вы играете со своим ботом онлайн.

  • jumps [object] - количество доступных прыжков. Например,

       {
         "1": 4,
         "2": 5
       }
     
    

    означает, что команда цвета 1 может прыгнуть 4 раза, команда цвета 2 - 5 раз.

  • board [object] – собственно, игровое поле. Например,

        {
          "size": 3,
          "cells": [
            [-1, 1, 0, 2, -1],
            [0, -1, 0, 0, -1],
            [2, 0, 0, 0, 1],
            [0, 0, 0, -1, -1],
            [-1, 1, 0, 2, -1]
          ]
          }
      
    

    Это соответствует такому полю:

Пример игрового поля

Элементы массива cells соответствуют "строкам" игрового поля. Обратите внимание, что каждая вторая строка игрового поля сдвинута вправо на половину гекса. Также, здесь и далее - индексация массивов начинается с 0.

cells[i][j] == N означает, что ячейка i-той строки j-того столбца:

  • является камнем при N == -1,
  • является пустой при N == 0,
  • содержит фишку цвета 1 при N == 1,
  • содержит фишку цвета 2 при N == 2.

Первым всегда ходит цвет 1.

Ответить нужно {"status":"ok"}.

Пример запроса:

$ curl -H "Content-Type: application/json" -X POST -d '{"id":"asdyhjk43566h","first_turn":"true","training":"true","jumps":{"1":1,"2":1},"board":{"size":3,"cells":[[-1,1,0,2,-1],[0,-1,0,0,-1],[2,0,0,0,1],[0,0,0,-1,-1],[-1,1,0,2,-1]]}}' http://localhost:3000/games

GET /games/:id – запрос вашего хода

Кроме id в урле, в качестве GET-параметра придёт:

  • color – цвет, которым вам предлагается походить.

Сервер автоматически пропустит ваш ход, если для вас нет допустимых ходов (вы не получите GET /games/:id в таком случае). Таким образом, если вы получили этот запрос, то на поле есть хотя бы один допустимый ход текущим цветом, и вы обязаны ходить.

Ответить нужно {"status":"ok","move_from":[i1,j1],"move_to":[i2,j2]}, где i1 и j1 – координаты ячейки из которой вы ходите, i2 и j2 - координаты ячейки, в которую ходите. Напоминаем, что индексация массивов начинается с 0.

Вы не должны считать, что ваш ход принят только на том основании, что вы ответили на этот запрос. То есть, не нужно менять состояние игрового поля внутри данного endpoint-а.

Пример запроса:

$ curl -X GET http://localhost:3000/games/asdyhjk43566h?color=1

PUT /games/:id – уведомление о изменении состояния игрового поля, вследствие вашего хода или хода вашего противника

Кроме id в урле, в теле запроса придёт JSON с ключами:

  • jumps [object] - обновлённое количество доступных прыжков в том же формате, что и в POST запросе.
  • changes [array] - список изменений игрового поля. Например,
        [
          [i1, j1, old_color1, new_color1],
          [i2, j2, old_color2, new_color2]
        ]
      
    
    означает, что ячейка [i1][j1] изменила цвет с old_color1 на new_color1, ячейка [i2][j2] изменила цвет с old_color2 на new_color2, и т.д.

Ответить нужно {"status":"ok"}.

Пример запроса:

$ curl -H "Content-Type: application/json" -X PUT -d '{"jumps":{"1":2,"2":3},"changes":[[0,5,2,0],[0,3,0,2]]}' http://localhost:3000/games/asdyhjk43566h

DELETE /games/:id – игра окончена

Ответить нужно {"status":"ok"}.

Пример запроса:

$ curl -H "Content-Type: application/json" -X DELETE http://localhost:3000/games/asdyhjk43566h

Пример очерёдности запросов со стороны игрового сервера

Допустим, что игровой сервер сводит в матче команды Team1 и Team2. В этот момент генерируется случайная доска, и выбирается случайная команда, делающая первый ход. Допустим, первый ход делает команда Team1. Очерёдность запросов со стороны игрового сервера будет следующей:

  • POST -> Team1
  • POST -> Team2
  • GET -> Team1
  • PUT -> Team1
  • PUT -> Team2
  • GET -> Team2
  • PUT -> Team2
  • PUT -> Team1
  • ...
  • DELETE -> Team1
  • DELETE -> Team2

Затем, игровой сервер просчитывает игру на той же карте, но с первым ходом второй команды:

  • POST -> Team2
  • POST -> Team1
  • GET -> Team2
  • PUT -> Team2
  • PUT -> Team1
  • GET -> Team1
  • PUT -> Team1
  • PUT -> Team2
  • ...
  • DELETE -> Team2
  • DELETE -> Team1

Дополнения

Время ответа бота на запрос ограничено одной секундой.

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

Любой некорректный ответ бота на запрос (недопустимый ход, неверный формат ответа, превышение таймаута) - немедленно приводит к поражению в текущей игре.

Игровой сервер не оповещает бота о некорректности его ответа. Вместо этого он засчитывает боту поражение, немедленно заканчивает просчёт игры, и рассылает обоим соперникам DELETE запрос. Это поведение можно использовать, к примеру, как косвенный признак недопустимости хода - в этом случае после GET запроса бот немедленно получает DELETE, а не ожидаемый PUT.

Игровой WEB интерфейс

Прежде всего, необходимо выбрать игровую песочницу. Команда открытого турнира найдёт своё название в одной из песочниц "ГРОДНО, ДНЕПР, МИНСК". Команды, состоящие из сотрудников Anadea, найдут себя в "INTERNAL" песочнице. TOP3 команд из открытого турнира будут перенесены в песочницу "ФИНАЛ" в конце игры, чтобы сразиться за супер приз.

Выбор песочницы

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

Счётчик

Ведущий выдаст каждой команде карточки с токенами входа в систему. Выбрав песочницу, в которой вы участвуете, введите токен в форму. У вас появится новый элемент меню "МОЯ КОМАНДА", на странице которой будут инструкции по деплою вашего бота. Держите в секрете ваш токен входа и IP адрес вашего дроплета - во избежание, к примеру, DDoS атаки на вашего бота во время турнира.

Присоединиться к команде

Чтобы попробовать игру "на вкус", поиграйте онлайн с тренировочным ботом:

Играть онлайн

Если вы уже ввели токен команды, у вас появится возможность поиграть онлайн со своим ботом. Это может быть полезно для отладки его поведения. В логах бота онлайн игры можно различить по параметру training: true в POST запросе.

Играть онлайн со своим ботом

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

Ходы типа прыжок ограничены

На странице ладдера можно следить за текущим положением команд в турнирной таблице.

Ладдер

Кликнув на название команды в ладдере, переходим на страницу команды. Здесь можно в реальном времени следить за динамикой набора очков, а также проследить за результатами матчей в текущем раунде.

Статистика игры

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

Результаты игр в матче

В случае, когда игра была остановлена из-за некорректного ответа - в результатах игры указывается причина остановки игры. Приведённый ниже пример надо понимать как команда "222" победила в обоих играх матча потому, что команда "test2" в каждой игре попыталась сделать недопустимый с точки зрения правил ход.

Причина остановки игры

Очки всем командам начисляются одновременно, по завершению раунда.

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

Просмотр реплеев

Как выложить бота

Заготовки

Для популярных языков и платформ мы сделали несколько heroku-ready заготовок ботов. Смело забирайте любую из них из специального репозитория:

  $ git clone https://github.com/Anadea/hexogon-templates.git
  $ cp -r hexogon-templates/your-language your-language
  $ cd your-language
  $ git init
  $ git add .
  $ git commit -m "Initial import"

Если вам не подходит ни одна из заготовок – вам нужно приложение на вашем языке и платформе сделать heroku-ready. Мы готовы вам помочь с теми проблемами, с которыми вам не помог Google и Stack Overflow =)

Первый деплой

Мы рекомендуем попробовать задеплоиться немедленно, не пытаясь пока писать логику игры. Заготовки дают корректные http-ответы на все API вызовы сервера, и вы сразу начнёте зарабатывать очки за счёт тех команд, которые ещё не отвечают ничего =)

Обязательно добавьте публичную часть вашего ssh-ключа в форму на странице команды:

  $ cat ~/.ssh/id_rsa.pub

Теперь в корне репозитория с приложением выполните:

  $ git remote add origin dokku@DROPLET_IP:app

И можете смело деплоить посредством git push origin master. Работайте с origin как с обычным удаленным репозиторием. В том числе, если понадобится, используйте ключ --force. Push в ветку master выкладывает новую версию вашего бота. Любые другие ветки можете использовать для совместной работы.

Есть несколько полезных говорящих команд, которые могут пригодиться:

  $ # следить за логами вашего бота.
  $ # Чтобы вывести что-нибудь в лог, достаточно отправить это что-то в STDOUT.
  $ # В заготовках ботов можно посмотреть примеры вывода в лог.
  $ ssh -t dokku@DROPLET_IP logs app -t
  $
  $ # Запустить команду в каталоге вашего бота.
  $ ssh -t dokku@DROPLET_IP run app rake db:migrate
  $ ssh -t dokku@DROPLET_IP run app rails c
  $
  $ # Войти в контейнер с ботом.
  $ ssh -t dokku@DROPLET_IP enter app

Вероятно, вам понадобится хранить данные между запросами. В вашем дроплете уже запущены и настроены несколько хранилищ, на выбор. Данные для подключения к базе данных (Postgres) доступны из переменной окружения DATABASE_URL, к Редису – REDIS_URL, к Memcached – MEMCACHED_URL.

В следующей статье мы расскажем про дроплеты DigitalOcean и настройку Dokku приложений.

Связаться