Пишем своего бота для Google AI Challenge. Быстрый старт

[sdevalex]

Одна вода… лучше бы перевел пару уроков с офф сайта.

[Dehumanizer]

Ждем перевода от вас.

[Dehumanizer]

Лучше бы!

[hazg]

Не тот случай, когда можно язык не знать.

… человек пару часов заинтересованным сэкономил, а вы его синим гоблином обзываете

[Wo1f]

На самом деле очень полезно… Когда увидел анонс загорелся, но что-то не поехало… А вот после этой статьи уже клепаю своего бота ;) Спасибо огромное, автор!!!

[ideas4ru]

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

[sova]

а до какого периода это соревнование идет?
граничные сроки?

[mixrin]

примерно пара месяцев. В районе декабря заканчивается.

[sova]

круто!
спасибо

[Kirhgoff]

Да, большое спасибо, в прошлый раз коллег на работе подбил на другой АИ-челлендж, про планеты. Забавно было. Надо посмотреть, че-то кажется сложным придумать какой-то простой и эффективный алгоритм. Тут какие-то хитрые алгоритмы нужны. И чтобы самообучались еще :)

[Wo1f]

Ну если сделать такой алгоритм, то можно научную работу сделать… А я и думаю многие просто побалуютcя if'ами и все ;)

[Kirhgoff]

Ну вот да, с планетами было просто и, я думаю, много серьезных айтишников попробовало. Знакомый мой вообще строил дерево возможных событий (я думаю, уже можно спойлерить) и пытался оценивать, какое наиболее выгодное. Попал во вторую сотню, вроде.

А тут подумать надо, может еще и нейронные сети на каждой карте в каждой позиции обучить :). Вряд ли высокооплачиваемые сотрудники Айти отделов каких-нибудь банков возьмутся за такое.

[Wo1f]

А можно глянуть что за планеты то? Я думаю что здесь не прокатит дерево все возможных ходов… слишком много… Кстати уже давно подумывал сделать игру для программистов на подобие… Только вот у гугла все легче и изящней)

[Kirhgoff]

вот тут, оно правда уже закончилось, если что, пишите, расскажу правила
ai-contest.com/

[kokoc]

Вот мой прошлый профайл — ai-contest.com/profile.php?user_id=9430. Обошелся простым алгоритмом по позиционированию своих войск в правильных, как я думал, местах. Оказалось есть как минимум 156 более правильных…

[Kirhgoff]

Круто. А что, с муравьями как? Хочется не играть в природу, а описать все какой то большой формулой.

[kokoc]

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

[Kirhgoff]

Я тоже склонен так думать, но вдруг человеческая изощренность сможет перепрыгнуть наработки эволюции. Вот у муравьев и спирали смерти есть, тоже бага, вроде как:
www.youtube.com/watch?v=_N8gQzTPNBk
Интересно ж.

[Bonart]

С планетами было сложно — априори нужен был полноценный не-скриптовый AI.

[kokoc]

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

[ApmeM]

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

Хотя место занял и не высокое (291), но внутри нашей компании бои шли за каждую планету :)

[Progrik]

А групповые решения будут рассматриваться? И можно ли регаться не как один участник, а как команда?

[ideas4ru]

Думаю, что официально это не одобряется, но в принципе вам никто мешать не будет, если вы командой будуте думать и кодом обмениваться.

[fenrirgray]

Тут кстати имеет смысл использовать С/C++. Много тяжелых вычислений будет, постоянно просчитывать путь для каждого муровья, если не мудрствуя лукаво взять для этого какой нибудь А* — скриптовые языки могут очень сильно просесть по производительности.

[Aspeed]

А можно поступить так как это делают муравьи в природе. Один нашел — все остальные идут по его стопам.

[xXxVano]

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

[fenrirgray]

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

[Aspeed]

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

[fenrirgray]

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

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

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

Но к природным алгоритмам это всё имеет крайне слабое отношение.

[webhamster]

Но каковы правила игры?

Как муравей ест? Что он получает, съедая еду?

Как муравей воюет? У него учитывается сила или еще что-то?

В английском не силен, поэтому и спрашиваю.

[amidart]

Все что нужно делать — это ходить.
Если вы оказались рядом с едой — вы ее автоматически съедаете — и благодаря этому из муравейника выползает новый муравей.
Если вы оказались в радиусе атаки с соперником — вы автоматически вступаете в бой. Кто из вас умрет — система решает сама. Если вы и соперник вступаете один на один в бой — умрете оба. Если двое вас против одного соперника, умрет соперник.
В общем же случае — вся внимание каждого отдельного муравья распределяется по всем соперникам в радиусе атаки этого муравья. Также и на этого муравья смотрят сразу несколько муравьев соперника. Если же среди муравьев соперника есть хотя бы один муравей, кому надо меньше отвлекаться или столько же, то ваш муравей умрет. Сложно объяснить словами, проще посмотреть примеры: aichallenge.org/specification_battle.php

Есть еще некоторые моменты: например нельзя направлять ваших муравьев в одну и ту же клетку одновременно, оба умрут. Еда пропадает, если вы и соперник одновременно к ней приблизились. И т.д. Все таки одним комментарием все правила не объяснить. Надо делать отдельный пост.

[ideas4ru]

В кратце тут: habrahabr.ru/blogs/sport_programming/130457/

[webhamster]

> Если вы оказались рядом с едой — вы ее автоматически съедаете

На соседней клетке, или нужно переместиться на клетку с едой?

[amidart]

В соседней клетке (но не угловой).
А вот чтобы разрушить чужой муравейник, нужно на него встать.

[webhamster]

Бегло пробежался по документации, не понял, на какое расстояние «видят» муравьи? Там есть формулы, но нет конкретных цифр. Сколько в клеточках составляет поле обзора (если муравей в центре)?

[amidart]

При запуске игры можно указывать ключи: --viewradius2, --attackradius2, --spawnradius2
По умолчанию viewradius2 равен 55. Корень из 55 приблизительно равен 7,4. Вот такой ответ.
Какой радиус поставят на соревнованиях — неизвестно, нигде пока не видел информации.

[leviathan]

aichallenge.org/game_settings.php

На сервере viewradius2 = 77.

[Maccimo]

Смотреть надо Game Specification > Bot Input:

At the start of a game, each bot is passed general parameters about the game
...
Here is the current list of parameters that will be passed to the bots:
...
"viewradius2"    # view radius squared
"attackradius2"  # battle radius squared
"spawnradius2"   # spawn radius squared

[webhamster]

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

Я правильно понял?

[Maccimo]

Скорее «Штаб Министерства Обороны» :)

Игра пошаговая и на каждом шаге программе передаётся всё, что видят пока ещё живые муравьи игрока.
Исключение — клетки с препятствиями («вода»). Информация о каждой клетке, занятой водой, передаётся только один раз за матч:

Information about a water square will only be sent the first turn in which it is visible by one of your live ants (to reduce the amount of data transferred).

[kokoc]

Я бы запрограммировал отдельно «муравьиного бога» — он бы осуществлял контроль карты и координировал действия муравьёв в общем, и дал бы отдельным муравьям некую автономность (отклониться от курса за едой, скооперироваться с ближайшим союзником для битвы)

[Stranger]

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

[amidart]

На локальной машине можно использовать ключ при запуске --turntime={Время в миллисекундах}
По умолчанию равно 1000 мс = 1 секунда. Можно поэкспериментировать.

[leviathan]

На сервере по умолчанию 500мс: aichallenge.org/game_settings.phп

[leviathan]

Блин, транслитератор покоцал ссылку: aichallenge.org/game_settings.php

[mixrin]

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

[SLY_G]

Что-то у меня в браузере (ffox 3.6) не работает визуализатор. яваскрипт выдает ошибку NS_ERROR_DOM_SYNTAX_ERR

[Stranger]

Возможно по какой-то причине подгружается какой-то другой яваскрипт конфликтующий с визуализатором. Например, если переводить сайт через гугл-транслейт, то тоже визуализатор не работает.

[SLY_G]

Обновил браузер до 7 версии, заработало, спасибо за ответ.