Google AI Challenge Ants - Страница 2

xkor · 21.10.2011, 21:57

Вчера началось интересное соревнование по программированию - AI Challenge, в этом году написанным игроками ботам предстоит играть в Ants.
Участникам соревнования предстоит реализовать алгоритм, который будет руководить колонией муравьев. На симметричной карте, состоящей из земли и воды (препятствия), каждому боту будут выделены один или несколько муравейников — места, в которых рождаются новые муравьи. Целью игры является захват и уничтожение муравейников противников при этом сохранение и защита своих. За уничтожение чужих муравейников начисляются очки, а за сдачу своего очки вычитаются.

Сайт соревнования http://aichallenge.org

Перевод на русский правил и спецификации игры:
http://habrahabr.ru/blogs/sport_programming/130979/
Хорошее описание игры:
http://habrahabr.ru/blogs/sport_programming/131262/

На русском много чего полезного можно почитать тут:
http://habrahabr.ru/blogs/sport_programming/130457/
http://habrahabr.ru/blogs/sport_programming/130946/
http://habrahabr.ru/blogs/sport_programming/130722/

ЗЫ ну и как же не похвастаться своим ботом:
http://ai-contest.com/profile.php?user=1234

SeregaZ · 22.10.2011, 13:50

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

скоро засяду.

Nickers · 22.10.2011, 20:00

Ахренеть, готов просто смотреть на смышленых муравьишек...
На каком языке делал?
Лично мне интересно придумать какой-нибудь прикольный алгоритм, который действовал бы против общей логики и всех нагибал, но я ленивый и, полагаю, нужно уметь программировать лучше, чем я.

Добавлено через 5 минут
http://ai-contest.com/visualizer.php?game=1404

Цитата:

иначе если поблизости враг держимся от него на безопасном расстоянии

Не сходится. Я ясно вижу как один муровейчик несется по прямой и всех по пути убивает!

Добавлено через 3 минуты
Ток что видел как твой муравей бегал от чужого, а тот не обращал на твоего внимания, возможно тот был исключением.

Добавлено через 6 минут
О, нашел ошибку. Может ты её и пофиксил уже...
http://ai-contest.com/visualizer.php...1001&user=1234
Твои муравьи все ломятся за одним куском еды. Много времени тратят, ведь тот, кто ближе все равно первый хапнет и им обратно идти...

Добавлено через 3 минуты
+ Часто двигаются на месте... Надо им сказать, чтоб они поворачивали в одну сторону с интервалом в 2-3 шага. (при рандоме) А то туда-сюда бегають. Видно, как 1 муровей не мог найти выход из комнаты 2х1 (Туда-сюда ходил)
Простите за флуд.

xkor · 22.10.2011, 21:00

Цитата:

Сообщение от Nickers

Не сходится. Я ясно вижу как один муровейчик несется по прямой и всех по пути убивает!

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

Цитата:

Сообщение от Nickers

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

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

Цитата:

Сообщение от Nickers

+ Часто двигаются на месте... Надо им сказать, чтоб они поворачивали в одну сторону с интервалом в 2-3 шага. (при рандоме) А то туда-сюда бегають. Видно, как 1 муровей не мог найти выход из комнаты 2х1 (Туда-сюда ходил)

это да, алгоритм перемещений когда вокруг всё спокойно я уже пересмотрел, в новой версии муравей будет двигаться по прямой пока не врежется или вблизи не появится враг/друг/муравейник/еда.

Сильно усложнить алгоритм не даёт ограничение по времени на ход (0,25 секунды вроде). И так в одной из первых моих игр можно видеть что я вылетел по таймауту ( http://ai-contest.com/visualizer.php?game=989&user=1234 ), я там хоть и выиграл но при большом количестве муравъёв в лабиринте очень много времени тратиться на просчёты расстояний...

Nickers · 22.10.2011, 22:42

xkor, А на каком все же языке?

Цитата:

Сильно усложнить алгоритм не даёт ограничение по времени на ход (0,25 секунды вроде)

И это очень печально, ведь тогда можно было бы сделать базу еды, которая существует и определять на неё ближайшего муравья, если "Занята"=0, но они все портят.
Думаю как-то все же можно облегчить скрипт. (КАК-ТО! =) )

Цитата:

при большом количестве муравъёв в лабиринте очень много времени тратиться на просчёты расстояний

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

Тогда правильнее будет направить умственные силы на добычу еды и минимум инстинктов на ориентирование. Просто, чтобы они тупо при врезании во что-то меняли направление. И при стене и при другом муравье. Чтобы думали только о поиске, а шли, куда попало.

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

Добавлено через 6 минут
http://aichallenge.org/visualizer.ph...2496&user=1234
114/262 (Противоположный тунель от твоего муравейника)
Порадовало, когда 3 муравья потянулись за 1й едой, её подобрал враг и они убежали от туда в ужасе))

Еще в тунелях при перемотке видно, как муравьи туда-сюда скачут (хотя у них есть 2 выхода на обоих концах, некоторые все же предпочитают туда-сюда)

xkor · 22.10.2011, 22:46

Цитата:

Сообщение от xkor

при большом количестве муравъёв в лабиринте очень много времени тратиться на просчёты расстояний...

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

Nickers · 22.10.2011, 22:48

При том, что алгоритм один на всех у муравьев с коллективным разумом не очень (Может опять ограничения сделали своё дело). Если муравей замечает муравейник - он бежит и там умирает, но всем остальным - пофиг)
(Ну а что они сделают, но есть же те, кто достаточно близко к этому месту, а муравейник не видит.)

Добавлено через 1 минуту
xkor, ясно тогда почему ухоят в таймаут.

xkor · 22.10.2011, 22:51

Цитата:

Сообщение от Nickers

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

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

Nickers · 22.10.2011, 22:57

xkor, А как это работает? Я бы сделал так, чтобы он шел в сторону, где свободно. Если там не свободно, то доходит на расстояние 2-3 клетки от объякта и проверяет другую сторону. Если расстояние после второго похода крайне мало ищет третью сторону (То есть отличную от первой, ведь он почти не сдвинулся).
Проблема еще в ямках 1-2 пикселя, но можно попробывать заставить их проверять не 1пиксель впереди себя, а 3...
А там есть Тест площадка, чтобы проверять замыслы алгоритмов?

Добавлено через 3 минуты
xkor, Да, это идеал. Вряд ли о таком нужно думать, есть более продуктивные пути растраты памяти, но можно подтягивать тех у кого весьма маленький радиус дальности и свободен путь до этого муровья.
(То есть все ближние и свободные сразу разворачиваются и помогают, ведь обычно их всегда толпа, просто у них у всех свои рандомы в голове и им, как бы насрать)

xkor · 22.10.2011, 23:03

Цитата:

Сообщение от Nickers

А там есть Тест площадка, чтобы проверять замыслы алгоритмов?

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

Цитата:

Сообщение от Nickers

А как это работает?

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

Nickers · 22.10.2011, 23:20

http://aichallenge.org/visualizer.ph...=1408&user=765
MomoBot. Можно видеть на 128/289, как толпа его ботов прет по одной траектории, а потом (наверное под натиском рандома) разделяется.

Добавлено через 4 минуты
xkor, Тогда идея сама по себе не очень... Можно про охоту забыть и только менять траекторию при появлении врага или просто напрямик ломить. Если направить силы на кормление (Ну там маршруты чертить и распределять силы по карте), то нужда в охоте отпадает, а если это слабый соперник то смерть муравья вообще ему все порушит. А тебе будет без особой разницы. (Твои к тому времени еще 5 таких соберут)

Добавлено через 1 минуту

Цитата:

толпа его ботов прет по одной траектории

При этом атакует врагов 3х1 и отступает. Делая упор на охоту. Я в замешательстве Т_Т

Добавлено через 2 минуты
Пвп муравьишки не хилые мутят...

Добавлено через 4 минуты
http://aichallenge.org/visualizer.php?game=580&user=765
У красных явно установка на защиту, но позиция проигрышная.
Армии муравьев, АААААААААА