Комментарии 33
Спасибо за разяснения, я сам вчера с этим конкурсом познакомился
Объясните пожалуйста, вот вы пишете что радиус атака 5, что приблизительно 2 клетки, от чего это зависит? Может быть не 2 клетки, а 3 или 1?
Объясните пожалуйста, вот вы пишете что радиус атака 5, что приблизительно 2 клетки, от чего это зависит? Может быть не 2 клетки, а 3 или 1?
Проще всего это понять просмотрев «в живую».
Откройте любую игру, хотя бы и эту к примеру. Увеличьте зумом на любом муравье и наведите мышкой на самого муравья или клетку рядом с ним.
Если увидите что появился круг вокруг муравья, значит эта клетка в пределах его радиуса атаки.
А зону видимости можно посмотреть включив туман войны, это меню в левой колонке плеера (для каждого игрока свой «туман войны»).
Откройте любую игру, хотя бы и эту к примеру. Увеличьте зумом на любом муравье и наведите мышкой на самого муравья или клетку рядом с ним.
Если увидите что появился круг вокруг муравья, значит эта клетка в пределах его радиуса атаки.
А зону видимости можно посмотреть включив туман войны, это меню в левой колонке плеера (для каждого игрока свой «туман войны»).
Чуть раньше в этом блоге были описаны правила боев вместе с правилами видимости.
>> В большинстве ботов не реализована защита муравейника
Подозреваю, это потому, что в первую очередь все реализуют поиск пути и распределение муравьёв на сбор еды.
При этом боты в топе — совершенно не показатель, потому что это — как правило сильно устаревшие версии.
Дело в том, что после загрузки новой версии бота на сервер его рейтинг сбрасывается, и ему нужно сыграть 10-15 игр, чтобы вернуться на предыдущую (хотя бы) позицию.
Т.к. серверов не очень много, а ботов — в избытке, то игры проводятся относительно медленно, и чтобы отыграть одну игру, надо 4-6 часа простоять в очереди. Т.е. если старая версия бота и так более-менее справляется и не сдаёт откровенно позиции, имеет смысл аплоадить следующую версию только при значительных изменениях.
Текующую же версию очень удобно тренировать на TCP-серверах. В этом случае код исполняется на вашей машине, вы только обмениваетесь ходами с сервером.
Во-первых, это позволяет играть практически без пауз, во-вторых, там по-настоящему сильные и развивающиеся противники, и в-третьих — очень удобно дебажить бота, т.к. весь вывод можно делать в файл у себя — тайминги и т.п.
Вот самый вроде активный сервер.
Подозреваю, это потому, что в первую очередь все реализуют поиск пути и распределение муравьёв на сбор еды.
При этом боты в топе — совершенно не показатель, потому что это — как правило сильно устаревшие версии.
Дело в том, что после загрузки новой версии бота на сервер его рейтинг сбрасывается, и ему нужно сыграть 10-15 игр, чтобы вернуться на предыдущую (хотя бы) позицию.
Т.к. серверов не очень много, а ботов — в избытке, то игры проводятся относительно медленно, и чтобы отыграть одну игру, надо 4-6 часа простоять в очереди. Т.е. если старая версия бота и так более-менее справляется и не сдаёт откровенно позиции, имеет смысл аплоадить следующую версию только при значительных изменениях.
Текующую же версию очень удобно тренировать на TCP-серверах. В этом случае код исполняется на вашей машине, вы только обмениваетесь ходами с сервером.
Во-первых, это позволяет играть практически без пауз, во-вторых, там по-настоящему сильные и развивающиеся противники, и в-третьих — очень удобно дебажить бота, т.к. весь вывод можно делать в файл у себя — тайминги и т.п.
Вот самый вроде активный сервер.
>> Хватает чтобы держаться в рейтинге примерно в 50-60 позициях (max skill 49).
Сейчас у сотой позиции скилл 63.39 :)
>> Бот почти переписан с нуля в ООП формат.
Не опасаетесь, что потеряете в быстродействии? Для такого большого числа итераций, которые необходимы, это может быть существенно.
>> блокирование для хода клеток, у которых с 3-х сторон вода
Смысл в них есть — если, например, куча своих муравьёв столпится рядом, может оказаться, что одному из муравьёв нужно будет туда спрятаться, чтобы его не убило своим же муравьём. (Кстати, я мог пропустить, но, кажется, в статье не упомянуто, что свои муравьи, походившие на одну и ту же клетку, погибают.)
Интересные факты:
Изначально организаторы рассчитывали использовать 2 сервера, но их уже 5.
Боту доступно как минимум 1.5 GB памяти.
Процессоры, используемые на серверах, уровня примерно i7.
Сейчас у сотой позиции скилл 63.39 :)
>> Бот почти переписан с нуля в ООП формат.
Не опасаетесь, что потеряете в быстродействии? Для такого большого числа итераций, которые необходимы, это может быть существенно.
>> блокирование для хода клеток, у которых с 3-х сторон вода
Смысл в них есть — если, например, куча своих муравьёв столпится рядом, может оказаться, что одному из муравьёв нужно будет туда спрятаться, чтобы его не убило своим же муравьём. (Кстати, я мог пропустить, но, кажется, в статье не упомянуто, что свои муравьи, походившие на одну и ту же клетку, погибают.)
Интересные факты:
Изначально организаторы рассчитывали использовать 2 сервера, но их уже 5.
Боту доступно как минимум 1.5 GB памяти.
Процессоры, используемые на серверах, уровня примерно i7.
Спасибо за сведения.
Статья писалась примерно неделю назад (пока шла через песочницу, потом через топики и тд.), так что актуальность потерялась. Тот бот скатился на 160 место уже.
С тех пор не заходил на сайт соревнований.
То что не реализуют защиту муравейника — это большой стратегический минус, на этом многие пролетают.
А алгоритмы поиска пути и сбора еды — один из самый простых аспектов, вот только нагрузка у поиска пути довольно большая. Пробовал на PHP прикрутить A*. Работает отлично, но на 200+ муравьев и сложных траекториях часто давал timeout, не успевал за ход. Можно было конечно и по-оптимизировать, но уже было не до этого.
Своим муравьем можно убить, только если двух в одну клетку послать, а это бот контролирует (об этом в «Область видимости и отслеживание ситуации» было написано). Хранит клетки, куда уже были отданы приказы.
Касательно самого бота это только forFun, чтобы можно было «человеко-читаемо» писать логику поведения. Меня не столько интересовала фактическая победа и реализация, сколько стратегическая логика игры. Просматривал логи, поведение, механику, алгоритмы и т.п.
Обо всем этом и написал.
Статья писалась примерно неделю назад (пока шла через песочницу, потом через топики и тд.), так что актуальность потерялась. Тот бот скатился на 160 место уже.
С тех пор не заходил на сайт соревнований.
То что не реализуют защиту муравейника — это большой стратегический минус, на этом многие пролетают.
А алгоритмы поиска пути и сбора еды — один из самый простых аспектов, вот только нагрузка у поиска пути довольно большая. Пробовал на PHP прикрутить A*. Работает отлично, но на 200+ муравьев и сложных траекториях часто давал timeout, не успевал за ход. Можно было конечно и по-оптимизировать, но уже было не до этого.
Своим муравьем можно убить, только если двух в одну клетку послать, а это бот контролирует (об этом в «Область видимости и отслеживание ситуации» было написано). Хранит клетки, куда уже были отданы приказы.
Касательно самого бота это только forFun, чтобы можно было «человеко-читаемо» писать логику поведения. Меня не столько интересовала фактическая победа и реализация, сколько стратегическая логика игры. Просматривал логи, поведение, механику, алгоритмы и т.п.
Обо всем этом и написал.
>> То что не реализуют защиту муравейника
Её реализуют, конечно, просто не первым делом.
>> Пробовал на PHP прикрутить A*
Мне, кроме стратегии, очень интересно как раз оптимизация быстродейтсвия — т.е. получится ли PHP боту соревноваться с быстрыми языками?
Сейчас мой бот при управление 300 муравьями (пути найдены с помощью A*) тратит на ход около 0.05..0.1 секунды, при таймауте в 0.5, что вполне приемлемо.
И ещё есть хороший резерв по оптимизации.
К сожалению, надо очень много времени (которого всегда нет) на реализацию сложного поведения — поэтому та же защита муравейника у меня только сейчас выбилась в неотложные задачи.
>> двух в одну клетку послать, а это бот контролирует
Насколько я вижу, команды муравьям не кэшируются перед отправкой, и возможность походить анализируется для каждого муравья непосредственно перед его ходом.
В этом случае в следующей ситуации муравьи могут погибнуть:
клетка c окружена водой, оттуда можно походить только на b.
муравей B стоит на клетке b, и ходит на клетку c (туда ещё никто не походил), приказ ушёл серверу.
муравей A стоит на клетке а, и ходит на клетку b (туда ещё никто не походил), приказ ушёл серверу.
муравей C стоит на клетке c, и единственное место, куда он может пойти — клетка b (остальное — вода).
Но теперь он хоть пойдёт туда, хоть нет — он столкнётся с другим муравьём.
Такие ситуации возникают достаточно часто при большом скоплении муравьёв. Проще всего это решить кэшированием ходов, чтобы их можно было поменять (не отправлять сразу серверу).
Её реализуют, конечно, просто не первым делом.
>> Пробовал на PHP прикрутить A*
Мне, кроме стратегии, очень интересно как раз оптимизация быстродейтсвия — т.е. получится ли PHP боту соревноваться с быстрыми языками?
Сейчас мой бот при управление 300 муравьями (пути найдены с помощью A*) тратит на ход около 0.05..0.1 секунды, при таймауте в 0.5, что вполне приемлемо.
И ещё есть хороший резерв по оптимизации.
К сожалению, надо очень много времени (которого всегда нет) на реализацию сложного поведения — поэтому та же защита муравейника у меня только сейчас выбилась в неотложные задачи.
>> двух в одну клетку послать, а это бот контролирует
Насколько я вижу, команды муравьям не кэшируются перед отправкой, и возможность походить анализируется для каждого муравья непосредственно перед его ходом.
В этом случае в следующей ситуации муравьи могут погибнуть:
клетка c окружена водой, оттуда можно походить только на b.
муравей B стоит на клетке b, и ходит на клетку c (туда ещё никто не походил), приказ ушёл серверу.
муравей A стоит на клетке а, и ходит на клетку b (туда ещё никто не походил), приказ ушёл серверу.
муравей C стоит на клетке c, и единственное место, куда он может пойти — клетка b (остальное — вода).
Но теперь он хоть пойдёт туда, хоть нет — он столкнётся с другим муравьём.
Такие ситуации возникают достаточно часто при большом скоплении муравьёв. Проще всего это решить кэшированием ходов, чтобы их можно было поменять (не отправлять сразу серверу).
Я реализовывал это немного по-другому. Сразу уточню, что в этом алгоритме не отработан момент сложного поведения в случае нападения толпой. Это упрощенный вариант:
1. На вход метода $ant->move() поэлементно подается массив направлений, расставленный в порядке приоритета. Например (n,e,w,s), то есть сперва попробовать на север, потом восток и т.д.
Цикл заканчивается когда хотя бы одно их направлений будет подтверждено.
2. Если в «ходить в эту клетку» уже был приказ, или там еда или вода, то отказать.
3. Если на этой клетке муравей и он не двигался (!$ant->isMoved()), тогда приказать ему
двигаться и снова попробовать сходить в этом направлении.
4. Если клетка является тупиком — то отказать в направлении.
5. Если сила вражеских муравьев в клетке равносильна смерти муравья, то отказать в направлении.
Там же «зашит» алгоритм, помнящий к какой цели шел муравей и как долго он уже к ней идет. Чтобы муравьи не «зависали» над одной и той же целью слишком долго.
А дальше уже сохраняем куда именно пошел муравей, обновляем «карту сил», какое направление было выбрано (для расчета последних приоритетных направлений) и собственно отдаем сам приказ о движении.
Такой механизм в принципе не требует кеширования команд. Но вот для сложных баталий конечно кешировать уже будет удобнее.
1. На вход метода $ant->move() поэлементно подается массив направлений, расставленный в порядке приоритета. Например (n,e,w,s), то есть сперва попробовать на север, потом восток и т.д.
Цикл заканчивается когда хотя бы одно их направлений будет подтверждено.
2. Если в «ходить в эту клетку» уже был приказ, или там еда или вода, то отказать.
3. Если на этой клетке муравей и он не двигался (!$ant->isMoved()), тогда приказать ему
двигаться и снова попробовать сходить в этом направлении.
4. Если клетка является тупиком — то отказать в направлении.
5. Если сила вражеских муравьев в клетке равносильна смерти муравья, то отказать в направлении.
Там же «зашит» алгоритм, помнящий к какой цели шел муравей и как долго он уже к ней идет. Чтобы муравьи не «зависали» над одной и той же целью слишком долго.
А дальше уже сохраняем куда именно пошел муравей, обновляем «карту сил», какое направление было выбрано (для расчета последних приоритетных направлений) и собственно отдаем сам приказ о движении.
Такой механизм в принципе не требует кеширования команд. Но вот для сложных баталий конечно кешировать уже будет удобнее.
Раскажите как обстоят дела с сохранением статуса между ходами, я так понял каждый раз все по новому пересоздаеться, и старые установки стираются
Настройки игры передаются при инициализации бота в начале игры.
А с каждым ходом в бот передается следующая информация:
о новой увиденной воде (а не вообще видимой воде),
о всех видимых муравьях (с указанием номера бота-владельца),
о всех видимых муравейниках (с указанием номера бота-владельца),
о мертвых муравьях по результатам прошлого хода (с указанием номера бота-владельца),
о всей видимой еде,
текущий номер хода.
Соответственно эту информацию нужно обрабатывать (корректировать) каждый ход.
А с каждым ходом в бот передается следующая информация:
о новой увиденной воде (а не вообще видимой воде),
о всех видимых муравьях (с указанием номера бота-владельца),
о всех видимых муравейниках (с указанием номера бота-владельца),
о мертвых муравьях по результатам прошлого хода (с указанием номера бота-владельца),
о всей видимой еде,
текущий номер хода.
Соответственно эту информацию нужно обрабатывать (корректировать) каждый ход.
тоесть запомнить свой предыдущий ход определенным муровьем нельзя?
Можно. В статье я описал, что нужно учитывать, чтобы можно было контролировать каждого своего муравья из хода в ход. Посмотрите раздел «Область видимости и отслеживание ситуации». Можете также код бота посмотреть, там есть этот механизм.
Можно сохранять любую промежуточную информацию в любом месте (памяти своего процесса). Но прикол в том, что это не сильно помогает. Мой бот на 20-й позиции и я могу перечислить недостатки:
1. Нет нормальной защиты муравейника. Она есть, но должна быть гораздо более сильной. На это надо тратить немало времени, чтобы сделать достойную защиту.
2. Нет нормальной атаки чужих муравейников. Опять же, она есть, но надо это делать гораздо более целеустремленно. Этот фактор имеет крайне важное значение в самом начале игры, когда противник слаб и можно быстренько его захватить.
3. Атака/защита должна максимально следовать правилам чтобы правильно расчитывать шансы. У меня алгоритм использует свой анализ и иногда сливает.
4. Сбор еды должен идти постоянно. Чем больше котролируемая территория, тем лучше. Т.е. муравьи должны увеличивать видимую часть территории. Это тоже очень важно. При правильном развитии можно других легко задавить числом.
1. Нет нормальной защиты муравейника. Она есть, но должна быть гораздо более сильной. На это надо тратить немало времени, чтобы сделать достойную защиту.
2. Нет нормальной атаки чужих муравейников. Опять же, она есть, но надо это делать гораздо более целеустремленно. Этот фактор имеет крайне важное значение в самом начале игры, когда противник слаб и можно быстренько его захватить.
3. Атака/защита должна максимально следовать правилам чтобы правильно расчитывать шансы. У меня алгоритм использует свой анализ и иногда сливает.
4. Сбор еды должен идти постоянно. Чем больше котролируемая территория, тем лучше. Т.е. муравьи должны увеличивать видимую часть территории. Это тоже очень важно. При правильном развитии можно других легко задавить числом.
> Если два враждующих муравья пытаются взять еду одновременно, то она исчезает (не достается никому).
Как это возможно, если радиус атаки 5, а к еде оба муравья должны подойти вплотную?
Как это возможно, если радиус атаки 5, а к еде оба муравья должны подойти вплотную?
> соответственно, муравьев, защищающих муравейник лучше всего располагать в диагональных клетках.
Это очень полезное замечание!
> Муравейник считается разрушенным, если на его клетку успешно сходит один из вражеских муравьев.
То есть радиус атаки действует только на муравьев, а на муравейник надо именно сходить? Неожиданно.
Это очень полезное замечание!
> Муравейник считается разрушенным, если на его клетку успешно сходит один из вражеских муравьев.
То есть радиус атаки действует только на муравьев, а на муравейник надо именно сходить? Неожиданно.
Вы кстати не думали, что для фиксированного радиуса атаки должно быть оптимально построение n муравьев?
Отвечу сразу на все 4-ре комментария:
1. Радиус атаки 5 это не радиус в 5 клеток (посмотрите описание расчета радиуса), это радиус примерно 2 клетки, к тому же еда появляется на карте случайным образом. Так что возможна ситуация, когда еда появится в клетке, которая будет равноудалена для двух муравьев, которые сходили навстречу друг другу.
2. На муравейник надо именно «наступить».
3. Тут само собой на ваше усмотрение, это лишь классический подход. Он выбран таким в связи с тем, что для расчета пути выгоднее предполагать, что неизвестная область проходима, нежели обратное. Иначе бот будет пытаться прокладывать маршрут только по открытым областям, и, как следствие, алгоритм поиска пути не всегда будет находить путь, если например вы «открыли» часть суши на другом берегу от воды. В результате любая попытка расчета пути до такой точки будет заставлять бота запускать анализ пути, в который попадут все ячейки открытой карты, но путь так и не будет найден.
4. Все радиусы задаются при старте игры. Соответственно логично предположить, что универсальный алгоритм должен основываться на настройках, переданных при старте. На случай если они изменятся.
Однако можно и использовать конечно подход фиксированного радиуса. Тогда получается несколько проще (я просто тоже продумывал этот алгоритм).
В частности тогда можно создавать набор шаблонов расположения муравьев (где стоят свои, где враги и сколько их), их делить на шаблоны наличия заблокированных клеток, а дальше уже применять соответствующий алгоритм хода для всех муравьев, удовлетворяющих шаблону. Соответственно шаблоны должны вращаться. Для них даже можно вводить хеши для более быстрого поиска.
Но это лишь для самых стандартных ситуаций, для динамического радиуса это не подойдет. Гораздо более эффективным будет как раз описанный в статье механизм расчета «карты сил».
1. Радиус атаки 5 это не радиус в 5 клеток (посмотрите описание расчета радиуса), это радиус примерно 2 клетки, к тому же еда появляется на карте случайным образом. Так что возможна ситуация, когда еда появится в клетке, которая будет равноудалена для двух муравьев, которые сходили навстречу друг другу.
2. На муравейник надо именно «наступить».
3. Тут само собой на ваше усмотрение, это лишь классический подход. Он выбран таким в связи с тем, что для расчета пути выгоднее предполагать, что неизвестная область проходима, нежели обратное. Иначе бот будет пытаться прокладывать маршрут только по открытым областям, и, как следствие, алгоритм поиска пути не всегда будет находить путь, если например вы «открыли» часть суши на другом берегу от воды. В результате любая попытка расчета пути до такой точки будет заставлять бота запускать анализ пути, в который попадут все ячейки открытой карты, но путь так и не будет найден.
4. Все радиусы задаются при старте игры. Соответственно логично предположить, что универсальный алгоритм должен основываться на настройках, переданных при старте. На случай если они изменятся.
Однако можно и использовать конечно подход фиксированного радиуса. Тогда получается несколько проще (я просто тоже продумывал этот алгоритм).
В частности тогда можно создавать набор шаблонов расположения муравьев (где стоят свои, где враги и сколько их), их делить на шаблоны наличия заблокированных клеток, а дальше уже применять соответствующий алгоритм хода для всех муравьев, удовлетворяющих шаблону. Соответственно шаблоны должны вращаться. Для них даже можно вводить хеши для более быстрого поиска.
Но это лишь для самых стандартных ситуаций, для динамического радиуса это не подойдет. Гораздо более эффективным будет как раз описанный в статье механизм расчета «карты сил».
>> Иначе бот будет пытаться прокладывать маршрут только по открытым областям
Ничто не мешает сделать UNSEEN клетку по умолчанию проходимой. Я сделал именно так )
Ничто не мешает сделать UNSEEN клетку по умолчанию проходимой. Я сделал именно так )
Тогда какая разница между не-открытой клеткой и землей?
Просто не могу найти пример, когда это принципиально важно для какого-либо алгоритма.
Просто не могу найти пример, когда это принципиально важно для какого-либо алгоритма.
Ну, занть, какая часть карты ещё не открыта — важно, т.к. надо открыть всё, чтобы найти все вражеские муравейники.
Другое дело, что хранить UNSEEN именно в основной карте — непринципиально, и я этим пока не пользуюсь.
Возможно, буду этим пользоваться, чтобы UNSEEN точки были более приоритетные при поиске пути, чтобы поскорее их открыть.
Другое дело, что хранить UNSEEN именно в основной карте — непринципиально, и я этим пока не пользуюсь.
Возможно, буду этим пользоваться, чтобы UNSEEN точки были более приоритетные при поиске пути, чтобы поскорее их открыть.
Тут вы правы. Именно при поиске других муравейников имеет смысл использовать.
Насчет простого открытия карты не столь важно, потому что важно не открыть всё, и иметь открытым как можно больше, чтобы быстрее собирать появляющуюся еду.
Кстати из этого тогда вытекает идея использования симметрии карт, потому что симметричны не только вода, но расположение самих муравейников. Таким образом можно даже находить паттерны на карте и на их основе рассчитывать симметрию, и как следствие расположение вражеских муравейников и не открытую карту.
Насчет простого открытия карты не столь важно, потому что важно не открыть всё, и иметь открытым как можно больше, чтобы быстрее собирать появляющуюся еду.
Кстати из этого тогда вытекает идея использования симметрии карт, потому что симметричны не только вода, но расположение самих муравейников. Таким образом можно даже находить паттерны на карте и на их основе рассчитывать симметрию, и как следствие расположение вражеских муравейников и не открытую карту.
Хм, неплохая идея. Идею построить всю карту зная, что она зеркальная, я сразу отбросил — нудно и неинтересно реализовавть. А вот муравейники попробовать поискать — вполне можно.
На самом деле это не так сложно реализовать. Даже без сложного поиска паттернов карты.
Как только находим любой вражеский муравейник, то запускаем цикл с учетом зеркальной замкнутости карты, в котором собираем набор из координат с одинаковым смещением по осям между своим и вражеским муравейником.
Проще говоря:
свой муравейник 0,0
вражеский 7,10
значит еще один вражеский будет в 14,20 и так далее по циклу зеркальных координат, пока снова не встретится клетка своего же муравейника.
Это конечно не всегда с первого раза найдет абсолютно все муравейники, но найдет те, которые лежат на одной оси симметрии. А если это был вообще ближайший муравейник, тогда скорее всего сразу все, потому что ось симметрии скорее всего опишет по спирали всю карту и вернется к своему же муравейнику.
Как только находим любой вражеский муравейник, то запускаем цикл с учетом зеркальной замкнутости карты, в котором собираем набор из координат с одинаковым смещением по осям между своим и вражеским муравейником.
Проще говоря:
свой муравейник 0,0
вражеский 7,10
значит еще один вражеский будет в 14,20 и так далее по циклу зеркальных координат, пока снова не встретится клетка своего же муравейника.
Это конечно не всегда с первого раза найдет абсолютно все муравейники, но найдет те, которые лежат на одной оси симметрии. А если это был вообще ближайший муравейник, тогда скорее всего сразу все, потому что ось симметрии скорее всего опишет по спирали всю карту и вернется к своему же муравейнику.
Всё не так просто, как мне кажется :)
Вот наглядный пример:
ants.fluxid.pl/replay.8935
Пусть мы знаем о муравейнике 143,2 и 113,32. Вашим способом мы узнаем только о муравейниках на этой линии.
Кроме того, в картах допускается зеркальная симметрия.
Вот наглядный пример:
ants.fluxid.pl/replay.8935
Пусть мы знаем о муравейнике 143,2 и 113,32. Вашим способом мы узнаем только о муравейниках на этой линии.
Кроме того, в картах допускается зеркальная симметрия.
А, забыл.
Если мы будем знать, например, 81,9 и 58,141 — то тогда вообще ничего больше узнать не получится.
Если мы будем знать, например, 81,9 и 58,141 — то тогда вообще ничего больше узнать не получится.
Посмотрите внимательно на карту из примера.
Там у каждого бота по 5 муравейников. Следовательно если будет обнаружен муравейник 113,32 для бота, который владеет муравейником 143,2 тогда он как минимум получает 5 осей для расчетов примерного местоположения других муравейников.
Я не говорю что этот метод панацея, скорее это один из способов предположительного местоположения вражеских муравейников, который можно эффективно использовать.
Конечно нужно учитывать размерность карты и количество муравейников и каждого бота (это легко посчитать по своим муравейникам). Соответственно и паттерн смещать надо также.
В вашем примере это легко увидеть, что обнаружив указанный вами муравейник, нужно сделать аналогичное смещение для каждого своего муравейника, и тем самым получить еще 4-ре предположительные точки, где есть вражеские муравейники.
Там у каждого бота по 5 муравейников. Следовательно если будет обнаружен муравейник 113,32 для бота, который владеет муравейником 143,2 тогда он как минимум получает 5 осей для расчетов примерного местоположения других муравейников.
Я не говорю что этот метод панацея, скорее это один из способов предположительного местоположения вражеских муравейников, который можно эффективно использовать.
Конечно нужно учитывать размерность карты и количество муравейников и каждого бота (это легко посчитать по своим муравейникам). Соответственно и паттерн смещать надо также.
В вашем примере это легко увидеть, что обнаружив указанный вами муравейник, нужно сделать аналогичное смещение для каждого своего муравейника, и тем самым получить еще 4-ре предположительные точки, где есть вражеские муравейники.
В догонку (не ради стратегии, а просто как возможный алгоритм):
Этот же параметр можно использовать в качестве маркера размерности паттернов карты.
Проще говоря:
карту «воды» вокруг своего муравейника (размером половины расстояния между муравейниками) накладывать на каждый найденный вражеский муравейник. Но тут еще надо будет учесть зеркальное наложение (и по каким осям зеркальное) или прямое.
Этот же параметр можно использовать в качестве маркера размерности паттернов карты.
Проще говоря:
карту «воды» вокруг своего муравейника (размером половины расстояния между муравейниками) накладывать на каждый найденный вражеский муравейник. Но тут еще надо будет учесть зеркальное наложение (и по каким осям зеркальное) или прямое.
ламерский вопрос: я вот не понял если я загрузил бота, потом кое что исправил и снова загрузил на сайт, моя статистика с момента загрузки первого бота пропадёт?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Описание Google AI challenge (Ants)