Sport programming
October 2009 3

Code Game Challenge

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

Среди таких соревнований я хочу остановиться на соревнованиях Code Game Challenge.


Соревнования формата Code Game Challenge это соревнования по написанию стратегии (грубо говоря, искусственного интеллекта) для некоторого предложенного мира.

Команде, состоящей из 3 человек, дается один компьютер, на который установлено следующее программное обеспечение:
  • среды разработки;
  • ПО для отправки решений и просмотра результатов;
  • шаблон проекта для стратегии.


Набор языков варьируется от олимпиады к олимпиаде, но в него всегда входят языки, являющиеся разрешёнными правилами ACM ICPC.

ПО для отправки решений и просмотра результатов позволяет отправлять на сервер своё решение и просматривать результаты симуляции.

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

Кроме того, за день-два участникам выдаются правила игрового мира, которые описывают физику игрового мира, в них определяются основные константы (например, максимальное ускорение) и, самое главное, в правилах приводится API по управлению юнитами и взаимодействию с внешним миром.

Время на разработку стратегии обычно составляет 4 часа. За это время участники могут отправлять решения на сервер сколько угодно раз. Штрафные очки не начисляются. Последнее решение, отосланное участниками, считается как окончательное.

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

Симуляция боя пошаговая. Т.е. время в игровом мире дискретно. Каждый ход симулятор опрашивает игровые стратегии (обычно в порядке игроков в списке участников боя), стратегия заполняет некоторую структуру, которая описывает «желания» активного юнита, после этого значения этой структуры подгоняются под ограничения, и после этого применяются.

Теперь, что бы стало попонятнее, разберём пример.

Классикой жанра стали соревнования с участием танков. Так что более подробно я буду рассматривать на их примере.

Итак, вам дается игровой мир, представляющий собой прямоугольник 2048 х 1536. Во время боя на поле могут появляться бонусы – объекты, радиусом 10, при наезде на который юнит получает прибавку к текущему уровню HP в 5 единиц.

В бою учувствует 4 юнита.

Каждый юнит представляет собой окружность радиусом 20 единиц. Юнит снабжён оружием, направленным по направлению движения. Перезарядка оружия происходит в течении 10 ходов. Снаряд летит со скоростью 3 ед/такт.

Бой состоит из 500 ходов.

Обычно, правила расписаны на 10-15 листах, но вот кратко суть.

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


Функция управления юнитом:
  • установить скорость движения
  • повернуться на заданный угол
  • выстрелить
  • получить информацию о состоянии орудия
  • получить информацию о местоположении юнита
  • получить информацию о состоянии юнита


Функции получения информации о вражеских юнитах:
  • получить информацию о состоянии юнита
  • получить информацию о местоположении юнита


Функции получения информации о бонусах:
  • получить информацию о местоположении бонуса
  • получить информацию о времени жизни бонуса


Вот собственно и все. Достаточно короткий API, но его хватает )

Все остальное вам необходимо реализовывать самим.

Вот кратко список тех задач, которые вам придется решить:
  • стратегия выбора типа юнитов (обычно, в начале боя вам предлагается сделать выбор типа юнита. Разные типы юнитов обладают различными характеристиками.)
  • объезд препятствий
  • прогнозирование местоположения объектов (например, для стрельбы с опережением)
  • расчёт траектории своего движения


Вот прошли эти 4 часа, после этого обычно бывает перерыв несколько часов, что бы участники немного отдохнули, перекусили и размялись. Вечером их снова собирают в зале с большим экраном, и наступает самая красочная стадия CGC – Code Game Show. Участников группируют в группы случайным образом, и начинается показ всех боёв. Как правило, из группы команда победитель проходит в следующий этап, проигравшие остаются за бортом. И так далее, пока не определится победитель.

Ну и на последок, несколько видео таких соревнований, не все видео в хорошем качестве, так что сильно не серчайте.

В общем CGC – это интересно, ACM ICPC – это интересно.

CGC проводившийся в 2007 году на олимпиаде ТТИ ЮФУ


CGC проводившийся в 2007 году на четверть финале в Саратове


CGC проводившийся в 2007 году в Волжском


CGC проводившийся в 2009 году в Волгограде


UPD.1 CGC проводившийся в 2009 году на четвертьфинале по южному региону в г.Саратов


Куда податься, если вас это заинтересовало (ссылки представляются as-is):
  1. http://antru.ru/crobots3d/
  2. http://robocode.sourceforge.net/
  3. http://www.pureai.com/tankai/default.aspx
+4
4.7k 7
Comments 13