company_banner

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
    • 2

    Mail.Ru Group

    863,00

    Строим Интернет

    Поделиться публикацией

    Похожие публикации

    Комментарии 2
      +1
      Хотелось бы в следующем году увидеть javascript в списке поддерживаемых языков и собственно пакет для nodejs.
        0
        Мухтар постарается (с)

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

      Самое читаемое