Правила Google AI Challenge Осень 2011

Правила турнира

• Результаты турнира определяются с помощью ПО написанного организаторами. Опубликованные результаты являются окончательными. Текущий рейтинг игроков не является официальным и может отличаться от опубликованных окончательных результатов.
• Каждый участник турнира может иметь единственную учетную запись. При выявлении участника управляющего несколькими учетными записями, и несмотря на то, что эти учетные записи зарегистрированы на других людей, нарушитель будет дисквалифицирован.
• Участники (или их программы), которые нарушают дух правил и спорта (вероятно не нарушая официального текста правил), отстраняются от участия в турнире, без возможности обжалования. В частности: сканирование памяти, умышленный проигрыш и изменение поведения в зависимости от имени оппонента — запрещены.
• Производить запись в файлы запрещено. Разрешено производить чтение из файлов которые вы высылаете для участия. Файлы располагаются в текущей директории.
• Использование нескольких процессов или потоков запрещено.
• Любая попытка нарушить нормальную работу программного обеспечения турнира или серверов приведет к немедленному привлечению сотрудников правоохранительных органов. Наш принцип — всегда преследовать нарушителей в судебном порядке.
• Организатор оставляет за собой право, изменить эти правила в любой момент, без предварительного уведомления участников турнира.

Расписание турнира
Текущий этап, на котором происходит прием программ от участников, продлится до 0 часов 59 минут понедельника 19 декабря 2011 года (время Московское). После чего начнется финальная часть турнира. Продолжительность финальной части на данный момент не определена, но ожидается, что она продлится менее одной недели. По ее окончании будет объявлен победитель и опубликованы окончательные результаты турнира.

Спецификация игры «Муравьи».
Структура хода:
Подготовка:
Каждый бот получает начальную информацию об игре, которая включает в себя размер карты, ограничение на количество ходов и лимиты времени на подготовку и на каждый ход. После того, как бот обработал эти данные, он должен сообщить ситеме о готовности ('ready'). После того как все участники сообщат о готовности начинается игра.

Ходы
После того, как все боты закончат подготовку и сообщат о готовности движок игры (далее сервер) циклически выполняет следующие действия:

1. Отправка состояния игры участникам.
2. Получение команд от участников.
3. Исполнение фаз хода и обновление игровой карты.
4. Проверка условий окончания игры.

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

Фазы хода
После получения всех приказов от игроков, сервер обновляет состояние игры, для перехода к следующему ходу. Исполнение хода происходит в 5 фаз:

• перемещение
• сражение
• разрушение
• сбор (еды)
• рождение (новых муравьев)

Игрок выбывает из битвы если:

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

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

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

Распределение очков:
Целью игры является набор максимального количества очков, которые начисляются за атаку и защиту муравейников.

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

Это означает, что если вы потеряли все свои муравейники и не разрушили ни одного чужого, вы закончите битву с 0 очков.

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

Досрочное окончание игры
Для сокращения незначащих игр или продолжений игр, введены правила досрочного прекращения игры.

Муравьи не собирают еду.
Если сервер решает, что боты не в состоянии собирать еду, игра прерывается. Считается, что это начальные или очень глупые боты. Прерывание происходит, если в течении 150 ходов на карте остается 90% еды.

Муравьи не уничтожают муравейники.
Прерывание происходит при доминировании одного игрока, который при этом не уничтожает других игроков. Считается, что бот, вероятно, не потеряет лидерство, просто он недостаточно обучен разрушению муравейников. Игра прерывается, когда общее число муравьев одного игрока составляет 90% от количества еды на протяжении 150 ходов.

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

Результат не изменится.
Если не осталось игроков с муравейниками, которые могут изменить свое место в результате игры, игра прерывается. Даже если остались игроки без муравейников, которые могут улучшить свое место они не учитываются. Для каждого оставшегося игрока с муравейником подсчитывается максимально возможное количество очков, которые он может набрать (если он разрушит все вражеские муравейники) и сравнивается с минимальным значением, которые могут набрать остальные игроки (если они потеряют все свои муравейники). Если разница позволит игроку изменить позицию или разбить ничейный результат, то игра продолжается. Если нет ботов подходящих под это условие, тогда игра прерывается.
(Например. В игре 4 игрока. Если бот A уничтожил муравейники ботов B и C, очки будут распределены так: A=5, B=0, C=0, D=1. Даже если бот D уничтожит муравейник бота A, то очки будут распределены так: A=4, D=3, B=0, C=0, таким образом у D нет возможности подняться выше второго места и игра прерывается.)
(Другой пример. В игре 4 игрока. Если бот A уничтожил муравейник бота B, и у B еще остались муравьи, он может попытаться набрать очки. Но если бот A уничтожит муравейник бота C, то возможность повысить место в игре у бота B пропадает, потому что Даже если бот B уничтожит муравейник бота A, то очки будут распределены так: A=4, B=2, C=0, D=0.)

Достигнут лимит на количество ходов.
Для каждой карты задается максимальное число ходов. Он сообщается каждому боту. По его достижению игра заканчивается. Организаторы расчитывают так настроить количество ходов, чтобы таким образом заканчивалось 90% — 95% всех игр.

Рождение муравьев.

После сбора еда попадает в муравейник, где рождается новый муравей. Каждый кусочек еды порождает одного муравья. Муравьи рождаются только в муравейниках. При этом

• муравейник не должен быть разрушен
• муравейник должен быть свободен от муравьев

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

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

• В начале игры в поле зрения каждого бота будет несколько кусочков еды (от двух до пяти).
• Начальная еда размещается на карте случайно, при этом симметрично.
• У каждой карты есть параметр появления еды, неизвестный игрокам. Количество появляющейся еды делится без остатка на количество игроков и появляется симметрично.
• Места появления еды на карте задаются симметричными шаблонами, шаблоны перебираются при появлении еды. Когда шаблоны заканчиваются, они перемешиваются.
• Перед повторным использованием шаблона должна закончится очередь шаблонов. Это означает что после сбора еды на одном поле может пройти немало времени, прежде чем там вновь появится еда. Кроме случая, когда этот шаблон был последним в наборе шаблонов и после перемешивания он попал в начало очереди.
• Иногда места появления еды равно удалены от двух ботов. Это означает укороченную очередь шаблонов появления еды. Это учитывается параметром появления еды.
• На зеркально симметричных картах рядом с осью симметрии появление еды уменьшено. Не стоит ожидать там ее появления часто.

Лучший способ собрать много еды — исследовать карту и занять большую территорию.

Исход битвы.

Муравьи находящиеся на расстоянии атаки друг от друга убивают друг друга (иногда).
Если в битве ваших муравьев больше, чем муравьев другого игрока, вы выживаете (обычно).
Исход битвы локально предопределен:

• Достаточно знать только соседних муравьев
• И сервер легко справляется с этой задачей

Исход битвы:

• Забавен!
• Означает уничтожение врагов без потерь с вашей стороны
• Позволяет защищать муравейник несколькими муравьями вызывая огромные потери у противника (Спарта!)
• Позволяет выстраивать невиданные боевые порядки
• Становится действительно не предсказуемым при участии трех или более противников. (может, дать им возможность перебить друг друга?)
• Вас не волнует, когда вы стремитесь закончить игру уничтожением всех муравейников.
• Это самая веселая часть игры!

Тут есть более точная спецификация битвы.

Входные данные для бота
Описание параметров:
В начале игры каждый бот получает начальные параметры о игре. Их список начинается с отдельной строки содержащей «turn 0». После которой в отдельных строках идут параметры в формате

параметр значение

Тип значения определен именем параметра. На данный момент все параметры, кроме player_seed, 32-х битные целые числа со знаком. player_seed 64-х битное целое число со знаком. Если бот получает незнакомый параметр он должен считать его строкой и не пытаться его разобрать.
Набор параметров может быть расширен в будущем, но если параметр попал в список удаляться он не будет.
На данный момент ботам передаются следующие параметры:

"loadtime"       # время на подготовку, в миллисекундах
"turntime"       # время на ход, в миллисекундах
"rows"           # количество строк карты
"cols"           # количество столбцов карты
"turns"          # максимальное количество ходов на карте
"viewradius2"    # квадрат радиуса видимости
"attackradius2"  # квадрат радиуса атаки
"spawnradius2"   # квадрат радиуса рождения
"player_seed"    # начальное значение для генератора случайных чисел, полезно при воспроизведении игры

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

Информация о ходе:
Каждый ход начинается одной из следующих строк

turn turnNo
end

«end» означает окончание игры. Победитель игры получает информацию о финальном состоянии игры, если он желает использовать её для локальных тестов.
Если игра закончена, ботам передается 2 строки с информацией о количестве участников и их финальных очках в виде:

players noPlayers
score p1Score ... pnScore

При продолжении игры вам передается информация о карте, которую видят ваши муравьи в следующем формате:

w row col                            # Вода строка столбец
f row col                            # еда строка столбец
h row col owner                      # муравейник строка столбец владелец
a row col owner                      # живой муравей строка столбец владелец
d row col owner                      # мертвый муравей строка столбец владелец

Окончание передачи информации отмечается отдельной строкой, содержащей «go».
Вы всегда считаетесь игроком под номером 0. Первый враг, которого вы увидите будет обозначаться единицей, второй двойкой и так далее. Таким образом вы не знаете точное количество участников игры.

Информация о полях с водой передается только когда ваши муравьи видят ее в первый раз (для уменьшения нагрузки).

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

Пример входных данных:

Ниже приведен пример данных которые получит игрок A для представленного состояния:

turn 0
loadtime 3000  
turntime 1000  
rows 20  
cols 20  
turns 500  
viewradius2 55  
attackradius2 5  
spawnradius2 1  
player_seed 42
ready

turn 1
f 6 5
w 7 6
a 7 9 1 
a 10 8 0
a 10 9 0
h 7 12 1
go

end
players 2
score 1 0
f 6 5
d 7 8 1 
a 9 8 0
a 9 9 0
go

Теперь приведем данные, которые получит игрок B, начиная с первого хода.

turn 1
f 6 5
w 7 6
a 7 9 0 
a 10 8 1
a 10 9 1
go

end
players 2
score 1 0
go

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

Расстояние.
Расстояния используются для радиусов обзора, атаки и рождения. Мы использовали квадраты этих величин, чтобы избежать работы с числами с плавающей точкой и использовать целые числа.
Расстояния подчиняются Евклидовой геометрии т. е. квадрат гипотенузы равен сумме квадратов катетов. Для двух точек a и b расстояние рассчитывается так:

Расстояние между точками a и b не превышает r если

Выходные данные.
После того, как бот получил начальные параметры и закончил подготовку к игре, он сообщает серверу о готовности отсылая строку «go».
Каждый бот может сделать ход любым количеством своих муравьев в одном из направлений: на север ('N'), на восток ('E'), на юг ('S') или на запад ('W'), которое будет исполнено, если поле назначения не содержит воду. Каждый ход должен передаваться в отдельной строке в следующем формате:

o row col direction	# о строка столбец направление

Нумерация строк и столбцов начинается с 0, а направления передаются как символы 'N', 'E', 'S' или 'W'. В конце каждого хода бот отсылает строку «go» для сообщения серверу, что он закончил отдавать приказы.

Пример

Ниже приведен пример команд от игрока A для игры на рисунке:

go  
o 10 8 N 
o 10 9 N
go

Пример команд от игрока B для игры на рисунке:

go  
o 7 9 W 
go

Блокирование
Движение блокируется только водой. Муравьи могут видеть и атаковать через воду. Если бот отдает команду муравью двигаться в воду, такой ход считается ошибочным и игнорируется.
Еда также может блокировать движение. Это происходит, когда еда появляется прямо перед муравьем. Не двигайте этого муравья и он соберет еду следующим ходом.

Столкновения
Если два муравья идут на одну и ту же клетку. Они умирают. Но, ваш муравей может быть с вражеским на одной клетке, если ваш муравей только родился (Похоже ваш муравейник скоро уничтожат!)

Дальше идет описание формата карт и описание генератора карт, которое не имеет прямого отношения к написанию бота, поэтому будет опущено.

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