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
    Поделиться публикацией

    Комментарии 13

      +1
      А как обеспечивается безопасность?
      PS Лично я все подобные (с задачей не имеющей точного решения) соревнования называю марафонами, чтобы не плодить слишком много терминов.
        0
        безопастность чего? я года два назад принимал участие в разработке такой системы, поэтмоу много технических деталей могу осветить
          0
          Что она программа не может испортить код или данные другой. В java и .NET это делается стандартными срествами, а как в С/С++?
            0
            *одна программа
              0
              во-первых, на серверной стороне отсутствуют «лишние» библиотеки,
              во-вторых, способов существует много — например поставить хуку на вызов и блокировать его…

                0
                Ну ntdll.dll и kernel32.dll есть всегда, а больше и не надо. Ну и чужие данные можно испортить без использования системных вызовов, если программы участников загружаются как dll'ки в один процесс.

                Еще вопрос. Как вы загружаете java-программы и С++-программы одновременно? Используйте JNI?
                  0
                  стратегии не обязательно компилируются в dll, хотя это и является одним из вариантов
                  второй вариант является компиляция в exe (соотвествено стратегии на сервере дополняются необходимым кодом), а взаимодействие между процессами и модулем симмулятора осуществляется, например, через стандартный ввод / вывод, или с помощью сокетов…

                  насчёт dll — такое тоже часто встречается, но надо сказать, что люди понимают — за нарушение правил им грозит дисквалификация не только с CGC, но и основного соревнования, так тчо на моей памяти таких инцидентов не было
          0
          А школьники к участию допускается? В частности, в Саратовской области, напимер?
            0
            нет, школьаня олимпиада проходит ненмого раньше, и поэтому в Саратове они не учавствуют… хотя я умаю если руководители команд поговорят с организаторами, то может быть пустят

            а вот в Таганроге школьники учавствуют на ровне со всеми…
              0
              Мне больше понравился CGC 2008 года проводившийся в Волжском. Жаль, что здесь его нет
                0
                Да, это было гораздо интереснее предыдущих и вариантов выигрышных стратегий было много больше.

                Для тех кто не в курсе: в распоряжении каждого игрока была база и 6 типов юнитов (4 вида наземных боевых юнитов, сборщик ресурсов и вертолет), побежденным считался игрок у которого уничтожили базу и всех юнитов.
                0
                Самый веселый вариант подобных соревнований был на моей памяти в 2006 году на Всесибирской олимпиаде. Там участникам было необходимо написать ботов, которые тупо выкидывают число (от 1 до бесконечности). Соответственно, боты соперников (одновременно запускали по несколько ботов), не имея никаких сведений о соперниках, должны были выкидывать числа. Побеждал тот, у кого было самое маленькое число. (При этом если два и более ботов выкинули одинаковое число, они все проигрывали). Насколько я помню, эта идея произвела настоящий фуррор =)))
                  0
                  сурово, но напомнило мне о их CGC последующих лет…
                  кажется в были ещё лабиринты, летающие тарелки и гонки )

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

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