На хабре уже имеется много информации по этому состязанию, однако вся она освещает отдельные моменты реализации, но не картину в целом. Постараюсь исправить это положение как можно более кратко, но в целом.
Данное описание предназначено для тех, кто что-то слышал о данном мероприятии, но всё желание что-то сделать отбила необходимость разбираться в тонкостях реализации. Пост состоит частично из перевода материалов с официального сайта, частично из анализа стратегий других ботов и чистой логики. Также в конце поста будет ссылочка на PHP-бота (чуть сложнее чем из starter-pack), который позволит вам попробовать собственные силы дописав имеющийся код. Официальный сайт состязания: aichallenge.org
Основные компоненты стратегии муравьиной колонии:
1. Пассивные
1.1. Сбор еды (food) и пополнение колонии (spawn)
- Еда появляется симметрично и одновременно для каждой колонии, так что условия для всех ботов всегда равноценные (карты также генерируются симметричными).
- Каждая собранная еда добавляется в «хранилище» колонии и при первой же возможности превратится в нового муравья.
- Существует параметр spawnradius, который всегда равен 1, то есть муравей появляется в клетке, где расположен муравейник.
- Чтобы собрать еду, необходимо подвести муравья на соседнюю ортогональную клетку с ней (не диагональ).
- Сама клетка с едой не является проходимой, то есть если муравей стоит на месте и рядом с ним появляется еда, он не может сходить на эту клетку. Необходимо просто оставить его на этой клетке на один ход, и тогда еда будет собрана.
- Только 1 муравей за 1 ход в 1 муравейнике может появиться. Если было собрано больше еды за предыдущий ход чем есть свободных муравейников, то новый муравей появится с задержкой.
- Если на клетке муравейника остался свой муравей с предыдущего хода, тогда он считается заблокированным и новые муравьи не появляются.
- Если два враждующих муравья пытаются взять еду одновременно, то она исчезает (не достается никому).
- Если муравейников несколько и собрано достаточно еды, то появляется по одному муравью в каждом муравейнике. Если еды недостаточно, приоритет появления у муравейников где дольше всего не появлялись муравьи, потом не заблокированные муравейники, и потом рандом.
- В начале каждой игры рядом с муравейниками в пределах видимости всегда появляется 2-5 еды.
- Количество появляющейся еды постепенно растет (данный параметр недоступен боту) и зависит от количества оставшихся ботов(соответственно появляется она тоже симметрично).
1.2. Защита муравейника (hill)
- Выход из муравейника для нового муравья всегда может быть только в 4-х направлениях, соответственно, муравьев, защищающих муравейник лучше всего располагать в диагональных клетках.
- Муравейник считается разрушенным, если на его клетку успешно сходит один из вражеских муравьев.
- Одними из основных элементов стратегии (об этом ниже), является как раз уничтожение вражеских муравейников, поэтому фактор защиты муравейника очень важен. Он отсутствует почти во всех ботах (даже топовых).
1.3. Разведка и контроль территории
Так как по условиям реализован механизм области видимости (см. ниже), то бот не знает какая именно карта перед ним, и получает информацию только об объектах, которые попадают в область видимости его муравьев. В большинстве случаев контролировать территорию не требуется, за исключением приближения врагов к муравейникам. Идеальным вариантом расположения муравьев является алгоритм при котором они открывают максимальную область видимости, а все незадействованные муравьи отправляются на «задание» по уничтожению вражеских муравейников (push). Соответственно, поддержание открытой карты имеет под собой главную цель в сборе разведчиками всей еды, которая попадается в области видимости.
2. Активные
2.1. Истребление вражеских муравьев
Расчет «атаки» происходит в целом по простому правилу:
Считается разница силы врагов и своих, если равны — гибнут все, иначе гибнет кто слабее, а сильный выживает.
Под «силой» подразумевается сколько муравьев имеют эту клетку (где расположен муравей) в радиусе своей атаки. Еще проще говоря, если один муравей в радиусе атаки двух, то он погибает, а они нет. 2х2 — погибают все, и так далее. Подразумевается, что муравей атакует сразу всех муравьев во всех клетках в радиусе атаки.
Внимание: хотя вода и не является проходимой клеткой, атака через нее также считается, то есть два муравья с разных сторон от клетки воды друг друга убьют.
Техническая сторона:
Информация о вражеских муравьяв передается боту каждый ход, однако исчезновение вражеского муравья из входных данных может означать ситуацию смерти равно как и ситуацию исчезновения из области видимости. Первая ситуация иногда отслеживается анализом данных о мертвых (dead), однако, муравей мог умереть от другого муравья и на границе области видимости. Это усложняет реализацию отслеживания действий каждого отдельного вражеского муравья, и хотя она может дать определенную выгоду при расчете примерных действий врага, ее реализация не столь приоритетна.
2.2. Истребление вражеских муравейников
Является одним из основных способов достижения победы. Без муравейника колония не производит новых муравьев, но те кто еще жив, продолжают вести битву.
Техническая сторона:
Равно как и информация о вражеских муравьях, информация о всех (в том числе и ваших) муравейниках передается каждый ход. То есть вы также можете не получить информацию о том или ином муравейнике если он исчез из области видимости или был стерт. Однако муравейники не могут двигаться и не отражаются в dead логах. Так что имеет смысл хранить информацию об обнаруженных муравейниках, однако если в очередном логе они не были найдены, но находятся в зоне видимости, то помечать их как разрушенные.
Соответственно, это позволяет направлять муравьев на вражеский муравейник, даже если он изчез из области видимости.
В большинстве ботов не реализована защита муравейника, по-этому не редки случаи, когда «залетный» муравей по сути приводит к поражению просто уничтожив беззащитный муравейник и тем самым оставив бота без подкрепления.
Фазы хода (шага)
Все расчеты производятся в следующем порядке:
- Движение (move)
- Атака (attack)
- Разрушение муравейников (raze)
- Сбор еды (gather)
- Появление новых муравьев и еды (spawn)
Небольшие замечания исходя из этой логики:
- Еда и муравьи всегда появляются последними, то есть нельзя собрать только что появившуюся еду (только на след. ход).
- Расчет атаки происходит всегда после совершения движений текущего хода, а не на основе положения в прошлом ходе.
- Новые муравьи появляются только если муравейник не был разрушен в этом ходу.
С каждом ходом в бот передается следующая информация (вода, муравьи, муравейники, мертвые муравьи, еда, номер хода). Всё это вы можете найти во входных логах бота.
Область видимости и отслеживание ситуации
Сам муравейник не имеет области видимости, то есть если рядом с ним нет не одного вашего муравья, то появление врага над вашим муравейником будет для вас неприятным сюрпризом.
При старте бота передается конфигурация текущей карты, где также указаны область видимости, атаки и spawn'a. Она представляет из себя квадрат гиппотенузы между двумя клетками (квадрат выбран с целью сохранения целого значения).
Стандартные параметры:
видимость — 55 (радиус примерно 7 клеток),
атака — 5 (радиус примерно 2 клетки).
spawn — 1 (текущая клетка).
Так как поступающие данные отображают только ситуацию (изменения) на данный ход, то за практику взят следующий подход:
- Изначально вся карта заполняется землей, а при появлении в логах «воды», карта корректируется.
- Все остальные данные считаются динамическими, однако и их можно контролировать. Про подход к контролю муравейников и вражеских муравьев было описано выше.
- Своих муравьев отслеживать значительно проще:
- Следить за тем, чтобы муравей не ходил в с другим своим же муравьем в одну и ту же клетку (это приводит к смерти обоих).
- С каждым ходом обновлять список своих муравьев на основе лога «мертвых муравьев».
- Обновление объектов муравьев (их координат) легко реализуется на основе хранения в объекте координат клетки, куда было приказано идти муравью, соответственно он или там умер, или двинулся в эту клетку.
- Учитывать, чтобы не был отдан ход в блокированную клетку (с едой или водой).
- Карта является циклически замкнутой по сторонам, что важно учитывать при расчете координат и областей видимости.
- Если во входном списке своих муравьев найден тот, кто не был «обновлен» с предыдущего хода, значит это новый муравей.
Условия поражения
- Все муравьи бота мертвы.
- Бот «вылетел» (crashed).
- Бот завис (timeout).
- Бот пытается выполнить код, который запрещен правилами проведения состязания.
Еще раз отмечу, что потеря всех муравейников не является поражением, бот продолжает воевать до потери всех муравьев.
Важный момент:
Если вражеский бот вылетел или завис, его муравьи остаются на поле боя, но не получают команд. Об этом никак не сообщается другим игрокам, которым сведения продолжают поступать в прежнем виде. В связи с этим, возможно даже реализовывать алгоритм, который отслеживает «рухнувших» игроков (такое редко, но случается), чтобы не тратить собственную армию на них или же «выносить» их с учетом того, что они обездвижены, что очень легко сделать.
Расчет очков за игру
Каждый бот начинает с 1-м очком за каждый муравейник.
Уничтожение вражеского муравейника +2 очка.
Потеря муравейника -1 очков.
Если остался только один бот и не все вражеские муравейники уничтожены (но убиты все вражеские муравьи или другие боты «зависли» или «упали»), то за каждый оставшийся вражеский муравейник бот получает очки, как будто он его уничтожил, то есть +2 себе и по -1 владельцам муравейников.
Составные элементы стратегий
1. Движение, поиск пути до точки, выбор целей
Обычный приоритет целей: сперва еда, потом вражеские муравейники, потом враги.
Самый простой алгоритм поиска пути это поиск в ширину, или чуть сложнее А*. Самым примитивным и быстрым способом можно считать выбор направления для движения на основе сокращения разницы координат (такой механизм реализован в starter-pack'ах), но конечно он дает много сбоев (например если цель на другом берегу).
Поиск путей является одной из самой ресурсоемких операций при расчете хода (даже анализ действий в среднем бывает проще), поэтому выбор и реализация алгоритма сильно влияет на конечный результат работы бота. Соответственно, больше возможностей у тех ботов, чья производительность выше (вы правильно поняли, весь топ написан на C, C++ и Java).
Основным приоритетом при отсутствии целей поблизости лучше всего считать область вне зоны видимости, это лучше всего заставляет муравьев «расползаться» по карте. Как только будет обнаружен вражеский муравейник, всех новых муравьев (или их процент) можно цепочкой отправлять на его штурм, а дальше снова на разведку. Контроль за областью видимости и движение к неоткрытым областям позволит муравьям равномерно распределяться по пространству карты не устраивая сборищ, которые нужны только при push'е врага.
Из полезных приемов является блокирование для хода клеток, у которых с 3-х сторон вода (нет почти практического смысла в таких клетках), что можно делать при анализе карты и хранить такие клетки в памяти.
Тоже самое касается и тупиковых «одноклеточных» туннелей, но для них делать исключение в случае нахождения там цели (например еды).
Полезным элементом иногда является сохранение «последнего приоритетного направления» когда он предпочитается двигаться в одну из сторон при первой же возможности, чтобы бота не разворачивало каждое препятствие, тогда он будет поддерживать курс.
3. Защита и нападение
В целом механизм нападения достаточно очевиден. Просчитываются примерные ходы противника (например с учетом того, что его приоритетные цели такие же как у вас: еда, другие муравейники, враги), далее расчитывается «карта сил» противника, и после уже расчитываются ходы ваших муравьев с учетом карты сил противника и приоритетности целей, то есть какой ход обеспечивает вашему муравью максимально близкую клетку к цели с перевесом «сил» в клетке в вашу сторону. Это достаточно сложный алгоритм, так как приходится расчитывать различные комбинации движения одновременно нескольких муравьев, но он вполне реализуем, так как большие «фронты» достаточно редки, чаще всего это отдельные столкновения.
В результате муравьи будут двигаться к цели (муравейнику или врагу) как-бы «максимально осторожно», тем самым уничтожая противника как только могут.
Идеального решения не существует, потому как большинство случаев неоднозначны и даже «рандомны», однако уже этого достаточно для минимизации ваших потерь.
Также, как уже говорилось, не стоит забывать и о защите собственного муравейника, где можно оставлять рядом 2-4 «охранника» в диагональных клетках, которые также будут собирать еду рядом с собой.
Примеры подобных стратегий можно найти в топе состязания
GreenTea
MomoBot
FlagCapper
Некоторые игры достаточно интересно посмотреть, особенно зная что это боты.
PHP-бот для затравки
Бот почти переписан с нуля в ООП формат. Гораздо удобнее пробуются различные стратегии поведения (например каждый свой муравей хранится в отдельном объекте), так что можно делать просто $ant->stay() или $ant->doMove(). Комментариев в коде мало, остались куски неиспользуемых тестовых функций, но вполне читабельно.
Общая стратегия бота: просто бродить по карте, собирать еду, избегать врагов, и при первой возможности трусливо рушить вражеские муравейники. Хватает чтобы держаться в рейтинге примерно в 50-60 позициях (max skill 49). Соответственно ботов из starter-pack он обыгрывает легко. Дальше уже на ваше усмотрение. Just for fun.
Скачать бота с Яндекса
Отладка бота
На официальном сайте не расписано как именно лучше производить отладку бота.
В стандартном pack'е (tools) для просмотра игр бота используется файл play_one_game_live.sh,
в котором необходимо указать адрес до вашего бота. Это подробно расписано в топике Пишем своего бота для Google AI Challenge. Быстрый старт. . К этому лишь стоит добавить, что в консоль и логи не будет выводиться каких-либо сообщений о причинах отказа бота (crushed). Для этого необходимо немного изменить файл play_one_game_live.sh, добавив ключи для запуска скрипта (заменив So на SoeEIO):
./playgame.py -SoeEIO --player_seed 42 --end_wait=0.25 --verbose --log_dir game_logs .....
Теперь в консоль, и в логи в директорию game_logs будут выводиться все сведения о том, что происходит в процессе игры (в том числе и ошибки действий бота, вроде двойного хода для одного муравья). Этой информации должно быть достаточно, чтобы провести анализ бота.
Чтобы лучше разобраться в технической стороне (спецификациях), лучше всего «покопать» start-pack'и для интересного вам языка. В целом, для начала их вполне достаточно.
В качестве заключения
Предложенное «поле боя» ботов получилось очень интересным для любителей попрактиковаться в алгоритмах. Хотелось бы конечно увидеть больше наших игроков в топе данного состязания, собственно почему данная статья и была написана. Удачи вам в деле создания собственного искусственного муравейника.