Спортивное программирование
Программирование
Блог компании Mail.Ru Group
13 декабря 2013

Russian AI Cup: технические детали

Всем привет!

Вот уже второй раз мы проводим (и уже практически провели) чемпионат Russian AI Cup. В этот раз участники соревновались в создании искусственного интеллекта для небольшого отряда бойцов. Фактически, участникам была предложена пошаговая стратегическая игра с формально определенными правилами и API для управления отрядом.

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

Основную техническую часть подготовки и проведения этого соревнования выполнила команда Центра олимпиадной подготовки программистов Саратовского государственного университета, может быть, кому-то из вас знакомая и по другим проектам: Codeforces, четвертьфиналы ACM-ICPC в Саратове, ICPC-challenge на финале ACM-ICPC 2013.

Железо
В системе задействованы два Linux-сервера и два небольших вычислительных Windows-кластера по 5 машин в каждом
Один из Linux-серверов хостит базу данных проекта (примерно 5GB в настоящее время). Мы используем MySQL 5.6, вся база в InnoDB. Второй сервер в основном нужен для web — на нем находятся сайт, форум и инфраструктурные приложения. Участники уже заметили, что родным языком для разработчиков системы является Java, — это правда, и для веба мы используем связку Nginx/Tomcat-7. В обоих серверах установлен процессор Intel® Xeon® E5-2620 и довольно скромные 16Гб оперативной памяти.

Компьютеры для тестирования работают под Windows 7 и расположены в Саратовском ГУ. Удалось задействовать недавно приобретенные i5-3470 с 32GB. Сначала были запущены 5 компьютеров, а незадолго до начала Раунда 1 были добавлены еще 5, что позволило уменьшить интервал тестирования боёв в Песочнице с 1 часа до 30 минут.

Компоненты системы
Система Russian AI Cup состоит из нескольких компонент, которые обеспечивают следующую функциональность (только самое главное):

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

Вот схема всей системы:



Стратегии участников компилируются в бинарники (или не компилируются, например, как для Python), которые при запуске читают описания мира по tcp и пишут ходы игрока.

Коротко о компонентах:
● Database — хранит состояние системы. Работает на выделенном database-сервере.
● Contester (контестер) — берет из базы необработанные стратегии и игры, отдает задания инвокерам и после ответа обновляет состояние стратегии/игры в базе. Запущен на web-сервере.
● Invoker (инвокер) — получает задание на компиляцию, верификацию стратегии или тестирование игры, обрабатывает задание, возвращает ответ контестеру. Инвокеры запущены на вычислительном кластере. Для симуляции боя инвокер запускает game server и игровые стратегии.
● Game Server — запускается инвокером для симуляции боя. Именно в этом приложении содержится логика игры.
● Invoker’s Cache — общий кэш для инвокеров, хранит скомпилированные бинарники.
● Boombox — хранилище для логов игр (по ним плеер показывает игры) и tcpdump-ов (по ним можно воспроизводить игры с помощью рипитера).
● Repeater — простая утилита, которая выкачивает tcpdump нужной игры для нужной стратегии и начинает отдавать его стратегии под видом состояния мира. Tcpdump содержит в точности всё то, что отсылалось стратегии при тестировании во время симуляции боя.

Теперь подробнее о некоторых компонентах.

Contester — специальное web-приложение, осуществляющее в базе данных все-все-все манипуляции с играми, попытками, рейтингом, этапами соревнования и многим другим в то время, как сайт используется по большей части для отображения информации (за исключением добавления пользовательских игр и попыток). Контестер создаёт новые игры по плану, зависящему от правил конкретного этапа соревнования, и аккумулирует в себе различные задания, такие как тестирование игр, компиляция и проверка стратегий, обновление рейтинга. Рейтинг контестер обновляет сам, когда считает это необходимым и для этого есть возможность. Задания на тестирование и компиляцию разбирают инвокеры.

Invoker-ы — главные труженики AI Cup. Как только у них выдаётся свободная минутка, они обращаются к контестеру с просьбой выдать им задание. Для обращений к Contester’у используется реализация протокола XML-RPC от Apache, по которому передаются объекты Google Protobuf. Такой подход, с одной стороны, позволяет заменить любой компонент системы на его реализацию на другом языке, а, с другой, позволяет удобно поддерживать различные версии объектов (message в терминологии Protobuf), добавлять новые поля и изменять существующие. В качестве примера такого объекта можно привести прототип задания на компиляцию:

message CompileRequest {
	required string id = 1;
	required File file = 2;
	optional string description = 3;
}


Здесь поля типа string являются аналогами строковых классов в различных языках и, в частности, класса java.lang.String в Java. Поле file является другим объектом Protobuf и имеет следующую структуру:

message File {
	required string name = 1;
	optional string type = 2;
	optional Blob content = 3;
	optional string uid = 4;
}


Объект файл является базовым для других объектов в нашем протоколе и используется также в других запросах, например, в запросе на тестирование игры. Если файл имеет небольшой размер (менее 32Кб), то его содержимое передаётся непосредственно в поле content, имеющее следующую структуру:

message Blob {
	required bytes compressed_bytes = 1;
	required bytes original_bytes_sha256 = 2;
}


Для больших файлов передаётся uid — уникальный идентификатор. Любой файл может быть найден по uid в Invoker’s Cache. В случае отсутствия файла в кэше, инвокер запрашивает файл у контестера и помещает его в кэш. В качестве движка для кэша использовалась GridFS, которая работает поверх MongoDB.

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

Запуск игровых стратегий осуществляется в песочнице, которая получается запуском из-под пользователя с ограниченными правами, перехватом некоторых функций (примерно как написано вот здесь), системой безопасности виртуальной машины (если программа исполняется в vm, как Java или C#).

Game server — он же игровой симулятор, он же игровой движок. Каждый участник может скачать себе Local runner, являющийся версией Game server’а с ограниченной функциональностью. Game server содержит всю логику игры и отвечает за симуляцию каждого конкретного сражения, запуская указанные ему инвокером стратегии в определённом порядке и с заданными дескрипторами подключения (порт локальной машины для подключения и секретный ключ для авторизации стратегии).

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

Стратегии также доступны для участников в виде набора CGDK (CodeGame DevKit) для разных языков. Сразу после запуска стратегия устанавливает связь с сервером по указанному ей TCP-порту и начинает общаться. Общение состоит из множества серий типа вопрос-ответ. Game server передаёт стратегии «слепок» игрового мира, адаптированный под конкретного игрока, в качестве вопроса, ответом же является желание стратегии совершить какое-либо действие в этом мире.

После окончания тестирования игры её лог и TCP-дампы данных, отправленных Game server’ом каждой из стратегий, сохраняются в Boombox.

Boombox — специальное хранилище бинарных данных, работающее через http. Инвокер и game server пишут в него данные, которые потом Boombox отдает участникам прямо в браузер или в Repeater. Написано с использованием асинхронных возможностей Servlet API 3. В перспективе может работать в режиме, когда данные в него одновременно пишутся и эти же данные читаются. Такой режим может быть полезен для реализации возможности просмотра боя в процессе его тестирования. Boombox умеет отдавать данные сжатыми по чанкам для экономии трафика.

Website — сайт проекта. Написан с помощью тех же технологий, что и Codeforces и некоторые другие наши проекты. Мы использовали наш собственный небольшой фреймворк Nocturne, основная полезность которого здесь состоит в том, что он умеет налету по F5 в браузере перекомпилировать и редеплоить веб-приложение, что делает разработку на статически-типизированной Java по скорости похожей на то, как можно писать на динамических языках. При этом сохраняются все прелести статической типизации, что нам очень нравится. Похожую функциональность позиционирует как киллер-фичу фреймворк Play!, но мы используем свои разработки.

Player — написан на JavaScript, отображает на Canvas ход игры. При старте делает запрос в Boombox, получает лог игры (в виде набора строк, каждая в JSON) и отрисовывает происходящее. В прошлом году была поддержка отрисовки спрайтов как на Canvas, так и с помощью DOM, но в течение года реализации Canvas в браузерах улучшились — второй вариант поддерживать перестали. Кстати, лог игр пришлось сжимать трюками в стиле «не передавать объект, если он не изменился». Итерация по подобным улучшениям позволила сократить размер трафика примерно на порядок.

Итог
Разработанная система за время чемпионата показала себя с хорошей стороны, всё работало четко и шустро. В этом году удалось успевать реализовывать большинство «хотелок» со стороны сообщества, — так появились друзья, подробные отчеты о причинах падения стратегий и другие фишки.

Суммарно было написано только на Java около 2 мегабайт кода, что составило около 60 тысяч строк или ~500 классов. Пропускная способность системы тестирования в Финале составила около 43-х боев в минуту и упиралась исключительно в работу стратегий участников.

Судя по отзывам участников, наши силы были потрачены не зря. С интересом ознакомимся с вашими отзывами о чемпионате.
+37
9,2k 50
Комментарии 2
Похожие публикации
Популярное за сутки