Описание Google AI challenge (Ants)

image
На хабре уже имеется много информации по этому состязанию, однако вся она освещает отдельные моменты реализации, но не картину в целом. Постараюсь исправить это положение как можно более кратко, но в целом.
Данное описание предназначено для тех, кто что-то слышал о данном мероприятии, но всё желание что-то сделать отбила необходимость разбираться в тонкостях реализации. Пост состоит частично из перевода материалов с официального сайта, частично из анализа стратегий других ботов и чистой логики. Также в конце поста будет ссылочка на 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 логах. Так что имеет смысл хранить информацию об обнаруженных муравейниках, однако если в очередном логе они не были найдены, но находятся в зоне видимости, то помечать их как разрушенные.
Соответственно, это позволяет направлять муравьев на вражеский муравейник, даже если он изчез из области видимости.
В большинстве ботов не реализована защита муравейника, по-этому не редки случаи, когда «залетный» муравей по сути приводит к поражению просто уничтожив беззащитный муравейник и тем самым оставив бота без подкрепления.

Фазы хода (шага)

Все расчеты производятся в следующем порядке:
  1. Движение (move)
  2. Атака (attack)
  3. Разрушение муравейников (raze)
  4. Сбор еды (gather)
  5. Появление новых муравьев и еды (spawn)


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

С каждом ходом в бот передается следующая информация (вода, муравьи, муравейники, мертвые муравьи, еда, номер хода). Всё это вы можете найти во входных логах бота.

Область видимости и отслеживание ситуации

Сам муравейник не имеет области видимости, то есть если рядом с ним нет не одного вашего муравья, то появление врага над вашим муравейником будет для вас неприятным сюрпризом.
При старте бота передается конфигурация текущей карты, где также указаны область видимости, атаки и spawn'a. Она представляет из себя квадрат гиппотенузы между двумя клетками (квадрат выбран с целью сохранения целого значения).
Стандартные параметры:
видимость — 55 (радиус примерно 7 клеток),
атака — 5 (радиус примерно 2 клетки).
spawn — 1 (текущая клетка).
Так как поступающие данные отображают только ситуацию (изменения) на данный ход, то за практику взят следующий подход:
  • Изначально вся карта заполняется землей, а при появлении в логах «воды», карта корректируется.
  • Все остальные данные считаются динамическими, однако и их можно контролировать. Про подход к контролю муравейников и вражеских муравьев было описано выше.
  • Своих муравьев отслеживать значительно проще:
  • Следить за тем, чтобы муравей не ходил в с другим своим же муравьем в одну и ту же клетку (это приводит к смерти обоих).
  • С каждым ходом обновлять список своих муравьев на основе лога «мертвых муравьев».
  • Обновление объектов муравьев (их координат) легко реализуется на основе хранения в объекте координат клетки, куда было приказано идти муравью, соответственно он или там умер, или двинулся в эту клетку.
  • Учитывать, чтобы не был отдан ход в блокированную клетку (с едой или водой).
  • Карта является циклически замкнутой по сторонам, что важно учитывать при расчете координат и областей видимости.
  • Если во входном списке своих муравьев найден тот, кто не был «обновлен» с предыдущего хода, значит это новый муравей.


Условия поражения

  1. Все муравьи бота мертвы.
  2. Бот «вылетел» (crashed).
  3. Бот завис (timeout).
  4. Бот пытается выполнить код, который запрещен правилами проведения состязания.

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

Расчет очков за игру

Каждый бот начинает с 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'и для интересного вам языка. В целом, для начала их вполне достаточно.

В качестве заключения

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

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 33

    0
    Спасибо за разяснения, я сам вчера с этим конкурсом познакомился
    Объясните пожалуйста, вот вы пишете что радиус атака 5, что приблизительно 2 клетки, от чего это зависит? Может быть не 2 клетки, а 3 или 1?
      0
      Проще всего это понять просмотрев «в живую».
      Откройте любую игру, хотя бы и эту к примеру. Увеличьте зумом на любом муравье и наведите мышкой на самого муравья или клетку рядом с ним.
      Если увидите что появился круг вокруг муравья, значит эта клетка в пределах его радиуса атаки.
      А зону видимости можно посмотреть включив туман войны, это меню в левой колонке плеера (для каждого игрока свой «туман войны»).
        0
        Вообщем выходит 2 по ортогоналям, и 1 по диагоналям для атаки
        0
        Чуть раньше в этом блоге были описаны правила боев вместе с правилами видимости.
        0
        >> В большинстве ботов не реализована защита муравейника
        Подозреваю, это потому, что в первую очередь все реализуют поиск пути и распределение муравьёв на сбор еды.

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

        Т.к. серверов не очень много, а ботов — в избытке, то игры проводятся относительно медленно, и чтобы отыграть одну игру, надо 4-6 часа простоять в очереди. Т.е. если старая версия бота и так более-менее справляется и не сдаёт откровенно позиции, имеет смысл аплоадить следующую версию только при значительных изменениях.

        Текующую же версию очень удобно тренировать на TCP-серверах. В этом случае код исполняется на вашей машине, вы только обмениваетесь ходами с сервером.
        Во-первых, это позволяет играть практически без пауз, во-вторых, там по-настоящему сильные и развивающиеся противники, и в-третьих — очень удобно дебажить бота, т.к. весь вывод можно делать в файл у себя — тайминги и т.п.

        Вот самый вроде активный сервер.
          0
          >> Хватает чтобы держаться в рейтинге примерно в 50-60 позициях (max skill 49).
          Сейчас у сотой позиции скилл 63.39 :)

          >> Бот почти переписан с нуля в ООП формат.
          Не опасаетесь, что потеряете в быстродействии? Для такого большого числа итераций, которые необходимы, это может быть существенно.

          >> блокирование для хода клеток, у которых с 3-х сторон вода
          Смысл в них есть — если, например, куча своих муравьёв столпится рядом, может оказаться, что одному из муравьёв нужно будет туда спрятаться, чтобы его не убило своим же муравьём. (Кстати, я мог пропустить, но, кажется, в статье не упомянуто, что свои муравьи, походившие на одну и ту же клетку, погибают.)

          Интересные факты:
          Изначально организаторы рассчитывали использовать 2 сервера, но их уже 5.
          Боту доступно как минимум 1.5 GB памяти.
          Процессоры, используемые на серверах, уровня примерно i7.
            0
            Спасибо за сведения.
            Статья писалась примерно неделю назад (пока шла через песочницу, потом через топики и тд.), так что актуальность потерялась. Тот бот скатился на 160 место уже.
            С тех пор не заходил на сайт соревнований.

            То что не реализуют защиту муравейника — это большой стратегический минус, на этом многие пролетают.
            А алгоритмы поиска пути и сбора еды — один из самый простых аспектов, вот только нагрузка у поиска пути довольно большая. Пробовал на PHP прикрутить A*. Работает отлично, но на 200+ муравьев и сложных траекториях часто давал timeout, не успевал за ход. Можно было конечно и по-оптимизировать, но уже было не до этого.

            Своим муравьем можно убить, только если двух в одну клетку послать, а это бот контролирует (об этом в «Область видимости и отслеживание ситуации» было написано). Хранит клетки, куда уже были отданы приказы.

            Касательно самого бота это только forFun, чтобы можно было «человеко-читаемо» писать логику поведения. Меня не столько интересовала фактическая победа и реализация, сколько стратегическая логика игры. Просматривал логи, поведение, механику, алгоритмы и т.п.
            Обо всем этом и написал.
              0
              >> То что не реализуют защиту муравейника
              Её реализуют, конечно, просто не первым делом.

              >> Пробовал на PHP прикрутить A*
              Мне, кроме стратегии, очень интересно как раз оптимизация быстродейтсвия — т.е. получится ли PHP боту соревноваться с быстрыми языками?
              Сейчас мой бот при управление 300 муравьями (пути найдены с помощью A*) тратит на ход около 0.05..0.1 секунды, при таймауте в 0.5, что вполне приемлемо.
              И ещё есть хороший резерв по оптимизации.

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

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

              В этом случае в следующей ситуации муравьи могут погибнуть:

              клетка c окружена водой, оттуда можно походить только на b.

              муравей B стоит на клетке b, и ходит на клетку c (туда ещё никто не походил), приказ ушёл серверу.
              муравей A стоит на клетке а, и ходит на клетку b (туда ещё никто не походил), приказ ушёл серверу.
              муравей C стоит на клетке c, и единственное место, куда он может пойти — клетка b (остальное — вода).
              Но теперь он хоть пойдёт туда, хоть нет — он столкнётся с другим муравьём.

              Такие ситуации возникают достаточно часто при большом скоплении муравьёв. Проще всего это решить кэшированием ходов, чтобы их можно было поменять (не отправлять сразу серверу).
                +2
                Я реализовывал это немного по-другому. Сразу уточню, что в этом алгоритме не отработан момент сложного поведения в случае нападения толпой. Это упрощенный вариант:
                1. На вход метода $ant->move() поэлементно подается массив направлений, расставленный в порядке приоритета. Например (n,e,w,s), то есть сперва попробовать на север, потом восток и т.д.
                Цикл заканчивается когда хотя бы одно их направлений будет подтверждено.

                2. Если в «ходить в эту клетку» уже был приказ, или там еда или вода, то отказать.
                3. Если на этой клетке муравей и он не двигался (!$ant->isMoved()), тогда приказать ему
                двигаться и снова попробовать сходить в этом направлении.
                4. Если клетка является тупиком — то отказать в направлении.
                5. Если сила вражеских муравьев в клетке равносильна смерти муравья, то отказать в направлении.

                Там же «зашит» алгоритм, помнящий к какой цели шел муравей и как долго он уже к ней идет. Чтобы муравьи не «зависали» над одной и той же целью слишком долго.

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

                Такой механизм в принципе не требует кеширования команд. Но вот для сложных баталий конечно кешировать уже будет удобнее.
                  0
                  >> Если на этой клетке муравей и он не двигался (!$ant->isMoved()), тогда приказать ему двигаться

                  Понял. Да, такой подход позволяет решить большую часть коллизий, если нет толпы.
            0
            Раскажите как обстоят дела с сохранением статуса между ходами, я так понял каждый раз все по новому пересоздаеться, и старые установки стираются
              0
              Настройки игры передаются при инициализации бота в начале игры.
              А с каждым ходом в бот передается следующая информация:
              о новой увиденной воде (а не вообще видимой воде),
              о всех видимых муравьях (с указанием номера бота-владельца),
              о всех видимых муравейниках (с указанием номера бота-владельца),
              о мертвых муравьях по результатам прошлого хода (с указанием номера бота-владельца),
              о всей видимой еде,
              текущий номер хода.
              Соответственно эту информацию нужно обрабатывать (корректировать) каждый ход.
                0
                тоесть запомнить свой предыдущий ход определенным муровьем нельзя?
                  0
                  Можно. В статье я описал, что нужно учитывать, чтобы можно было контролировать каждого своего муравья из хода в ход. Посмотрите раздел «Область видимости и отслеживание ситуации». Можете также код бота посмотреть, там есть этот механизм.
                    0
                    Можно сохранять любую промежуточную информацию в любом месте (памяти своего процесса). Но прикол в том, что это не сильно помогает. Мой бот на 20-й позиции и я могу перечислить недостатки:
                    1. Нет нормальной защиты муравейника. Она есть, но должна быть гораздо более сильной. На это надо тратить немало времени, чтобы сделать достойную защиту.
                    2. Нет нормальной атаки чужих муравейников. Опять же, она есть, но надо это делать гораздо более целеустремленно. Этот фактор имеет крайне важное значение в самом начале игры, когда противник слаб и можно быстренько его захватить.
                    3. Атака/защита должна максимально следовать правилам чтобы правильно расчитывать шансы. У меня алгоритм использует свой анализ и иногда сливает.
                    4. Сбор еды должен идти постоянно. Чем больше котролируемая территория, тем лучше. Т.е. муравьи должны увеличивать видимую часть территории. Это тоже очень важно. При правильном развитии можно других легко задавить числом.
                +1
                > Если два враждующих муравья пытаются взять еду одновременно, то она исчезает (не достается никому).
                Как это возможно, если радиус атаки 5, а к еде оба муравья должны подойти вплотную?
                  0
                  > соответственно, муравьев, защищающих муравейник лучше всего располагать в диагональных клетках.
                  Это очень полезное замечание!

                  > Муравейник считается разрушенным, если на его клетку успешно сходит один из вражеских муравьев.
                  То есть радиус атаки действует только на муравьев, а на муравейник надо именно сходить? Неожиданно.
                    +1
                    > Изначально вся карта заполняется землей, а при появлении в логах «воды», карта корректируется.
                    Это кстати не удобно, сложно контролировать какая часть рельефа карты уже известна, а какая нет. Сделал, чтобы изначально карта заполнялась неизвестными ячейками, а походу игры раскрывалась б.
                    0
                    Вы кстати не думали, что для фиксированного радиуса атаки должно быть оптимально построение n муравьев?
                      0
                      Отвечу сразу на все 4-ре комментария:

                      1. Радиус атаки 5 это не радиус в 5 клеток (посмотрите описание расчета радиуса), это радиус примерно 2 клетки, к тому же еда появляется на карте случайным образом. Так что возможна ситуация, когда еда появится в клетке, которая будет равноудалена для двух муравьев, которые сходили навстречу друг другу.

                      2. На муравейник надо именно «наступить».

                      3. Тут само собой на ваше усмотрение, это лишь классический подход. Он выбран таким в связи с тем, что для расчета пути выгоднее предполагать, что неизвестная область проходима, нежели обратное. Иначе бот будет пытаться прокладывать маршрут только по открытым областям, и, как следствие, алгоритм поиска пути не всегда будет находить путь, если например вы «открыли» часть суши на другом берегу от воды. В результате любая попытка расчета пути до такой точки будет заставлять бота запускать анализ пути, в который попадут все ячейки открытой карты, но путь так и не будет найден.

                      4. Все радиусы задаются при старте игры. Соответственно логично предположить, что универсальный алгоритм должен основываться на настройках, переданных при старте. На случай если они изменятся.
                      Однако можно и использовать конечно подход фиксированного радиуса. Тогда получается несколько проще (я просто тоже продумывал этот алгоритм).
                      В частности тогда можно создавать набор шаблонов расположения муравьев (где стоят свои, где враги и сколько их), их делить на шаблоны наличия заблокированных клеток, а дальше уже применять соответствующий алгоритм хода для всех муравьев, удовлетворяющих шаблону. Соответственно шаблоны должны вращаться. Для них даже можно вводить хеши для более быстрого поиска.
                      Но это лишь для самых стандартных ситуаций, для динамического радиуса это не подойдет. Гораздо более эффективным будет как раз описанный в статье механизм расчета «карты сил».
                        0
                        >> Иначе бот будет пытаться прокладывать маршрут только по открытым областям
                        Ничто не мешает сделать UNSEEN клетку по умолчанию проходимой. Я сделал именно так )
                          0
                          Тогда какая разница между не-открытой клеткой и землей?
                          Просто не могу найти пример, когда это принципиально важно для какого-либо алгоритма.
                            0
                            Ну, занть, какая часть карты ещё не открыта — важно, т.к. надо открыть всё, чтобы найти все вражеские муравейники.
                            Другое дело, что хранить UNSEEN именно в основной карте — непринципиально, и я этим пока не пользуюсь.
                            Возможно, буду этим пользоваться, чтобы UNSEEN точки были более приоритетные при поиске пути, чтобы поскорее их открыть.
                              +1
                              Тут вы правы. Именно при поиске других муравейников имеет смысл использовать.

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

                              Кстати из этого тогда вытекает идея использования симметрии карт, потому что симметричны не только вода, но расположение самих муравейников. Таким образом можно даже находить паттерны на карте и на их основе рассчитывать симметрию, и как следствие расположение вражеских муравейников и не открытую карту.
                                0
                                Хм, неплохая идея. Идею построить всю карту зная, что она зеркальная, я сразу отбросил — нудно и неинтересно реализовавть. А вот муравейники попробовать поискать — вполне можно.
                                  0
                                  На самом деле это не так сложно реализовать. Даже без сложного поиска паттернов карты.

                                  Как только находим любой вражеский муравейник, то запускаем цикл с учетом зеркальной замкнутости карты, в котором собираем набор из координат с одинаковым смещением по осям между своим и вражеским муравейником.
                                  Проще говоря:
                                  свой муравейник 0,0
                                  вражеский 7,10
                                  значит еще один вражеский будет в 14,20 и так далее по циклу зеркальных координат, пока снова не встретится клетка своего же муравейника.

                                  Это конечно не всегда с первого раза найдет абсолютно все муравейники, но найдет те, которые лежат на одной оси симметрии. А если это был вообще ближайший муравейник, тогда скорее всего сразу все, потому что ось симметрии скорее всего опишет по спирали всю карту и вернется к своему же муравейнику.
                                    0
                                    Всё не так просто, как мне кажется :)

                                    Вот наглядный пример:
                                    ants.fluxid.pl/replay.8935
                                    Пусть мы знаем о муравейнике 143,2 и 113,32. Вашим способом мы узнаем только о муравейниках на этой линии.

                                    Кроме того, в картах допускается зеркальная симметрия.

                                      0
                                      А, забыл.
                                      Если мы будем знать, например, 81,9 и 58,141 — то тогда вообще ничего больше узнать не получится.
                                        0
                                        Ваше утверждение верно только если у каждого по одному муравейнику. Но если это было так, карта была бы совершенно по-другому сгенерирована.
                                        0
                                        Посмотрите внимательно на карту из примера.
                                        Там у каждого бота по 5 муравейников. Следовательно если будет обнаружен муравейник 113,32 для бота, который владеет муравейником 143,2 тогда он как минимум получает 5 осей для расчетов примерного местоположения других муравейников.

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

                                        Конечно нужно учитывать размерность карты и количество муравейников и каждого бота (это легко посчитать по своим муравейникам). Соответственно и паттерн смещать надо также.

                                        В вашем примере это легко увидеть, что обнаружив указанный вами муравейник, нужно сделать аналогичное смещение для каждого своего муравейника, и тем самым получить еще 4-ре предположительные точки, где есть вражеские муравейники.
                                      0
                                      В догонку (не ради стратегии, а просто как возможный алгоритм):
                                      Этот же параметр можно использовать в качестве маркера размерности паттернов карты.
                                      Проще говоря:
                                      карту «воды» вокруг своего муравейника (размером половины расстояния между муравейниками) накладывать на каждый найденный вражеский муравейник. Но тут еще надо будет учесть зеркальное наложение (и по каким осям зеркальное) или прямое.
                          0
                          ламерский вопрос: я вот не понял если я загрузил бота, потом кое что исправил и снова загрузил на сайт, моя статистика с момента загрузки первого бота пропадёт?
                            +1
                            Увы, да.

                          Only users with full accounts can post comments. Log in, please.