@webkumo21 окт 2011 в 15:17

Ants AI Challenge. Учебник начинающего ботовода

6 мин

Спортивное программирование *

Перевод

+20

Комментарии 29

@Goder 21 окт 2011 в 15:56

!!!

Google AI Challenge 2011 уже доступен в Beta-версии
Старт в Google AI Challenge на Java
Пишем своего бота для Google AI Challenge. Быстрый старт

@webkumo 21 окт 2011 в 17:03

Позвольте спросить, а что вы этим хотите сказать?
У меня немного другое — перевод официального учебника. Статью я написал немного до Старт в Google AI Challenge на Java, просто она была в песочнице.

В общем в чём претензия?
В изобилии? Зато каждый найдёт то, что ему интересно.
В том что «повторяю»? Тогда извините, но вы промазали.

@mixrin 21 окт 2011 в 17:21

Его понять можно. Уже целых 3 вводных разного качества имеется.

Да и если человек не сможет понять что от него хотят в туториале — продолжать смысла немного.

PS Сам тоже участвую :p

@webkumo 21 окт 2011 в 17:25

Его понять можно, но и другим тоже много чего хочется…
И среди комментов к каждому туториалу — «лучше бы перевели»…

PS я сам ещё не участвую :)
Пилю потихоньку код под ролевое управление :)

@IgorKamenev 21 окт 2011 в 21:21

Увидев данный контест тут же бросился кодить.
«инструкцию не читал» (я же самый умный).
В итоге после 4-6 боев, сделал вывод, что побеждает тот, у кого больше муравьев.
Заточился на этом и…

В общем на всякий случай, если есть еще такие же идиоты как и я — очки начисляются за захват вражеского муравейника. (+2) и списываются за захват своего (-1).

Не повторяйте моих ошибок! :)

@RomanL 22 окт 2011 в 04:39

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

@IgorKamenev 24 окт 2011 в 21:09

Против этого я написал защиту — меряю время и если близко к 0.8 — скипаю еще не ходивших муравьёв.

@sic 25 окт 2011 в 12:33

только таймаут на реальном сервере теперь не 1.0с, а 0.5с! вообще корректнее считывать таймаут из параметра turntime.

@Mixailo 22 окт 2011 в 13:02

То есть простой выигрыш по количеству не считается? Да вроде дают какой-то опыт, вот у меня версия, которая холмы вообще не трогает:
aichallenge.org/profile_games.php?submission=1392
Доросла до скилла 52.42, потом черт меня дернул залить обновление, и как раз сервер игры сдох)

@mixrin 24 окт 2011 в 17:59

Очень нравится ваш защитный контур у базы ;)

@Mixailo 25 окт 2011 в 06:07

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

@sic 25 окт 2011 в 12:37

я писал нахождение пути через волновой алгоритм + кеширование результатов (по сути для каждой пары клеток куда-откуда записывается направление для кратчайшего пути).
в этой версии правда вообще никак не сделана battle resolution и защита hill, но на какой-то момент она была в десятке лучших, aichallenge.org/visualizer.php?game=11045&user=682

@Mixailo 26 окт 2011 в 00:26

У меня существенные проблемы с производительностью, уж не знаю в пхп ли дело и в моей криворукости. Думаю, и то и другое. Поэтому и A* (кстати, у него другая проблема — не могу толком определить, когда прекращать вычисления, если путь долго не находится).
Кстати, о «Дийкстре» (который, оказывается, Дейкстра).
Правильно ли я понимаю, что в данном случае волновой алгоритм от него отличается только тем, что волновой алгоритм не перепроверяет вершины, для которых уже есть число?

@mixrin 26 окт 2011 в 11:09

Ух, а я всё сражаюсь с чистотой функций и Хаскеллем в целом :)

Думаю к выходным отрефакторить весь код и сделать BFS.

@Mixailo 26 окт 2011 в 22:55

Да, рефакторить надо, конечно. У меня секс со starter package занял довольно много времени, пока я не обнаружил, что он по умолчанию считает все клетки проходимыми, а UNSEEN в списке констант только для красоты %)

@sic 26 окт 2011 в 14:16

Вообще волновой алгоритм это и есть частный случай Дейкстры для графа представляющего собой сетку вершин. Волновой алгоритм перепроверяет вершины, только если число, стоящее в ней больше, чем число вершины из которой мы пришли, но это соответствует маркировке «вычеркнутых вершин» Дейкстры. Проблемы с производительностью, думаю на PHP будут. На плюсах достаточно тупой вариант обхода без каких-либо кеширований отрабатывает едва ли за секунду для 100 муравьев. А на кеширование нужно до (200x200)^4 байт памяти (для каждой точки «откуда» идти, сохраняем всю карту расстояний от нее == результат одного прогона волнового алгоритма). Но это как раз влезает в отведенные 1.5Гб памяти.

@Mixailo 26 окт 2011 в 21:54

А как правильно кешировать с учетом не увиденных клеток? Ведь, теоретически, если не вся карта открыта, то оптимальный маршрут может меняться по мере исследования.

@ideas4ru 27 окт 2011 в 11:48

На счет кэширования результатов для каждой клетки это здравая идея! Но ведь карта в начале мало известна (все землей заполнено), могут вылезать косяки. Вы как это разрулили?

@RomanL 22 окт 2011 в 04:38

+ Стоит запустить playgame.py без параметров чтобы посмотреть список режимов — очень полезно для отладки
+ Если вы загружаете следующую версию бота, то, как я понял, он начинает набор очков с нуля.

@Funcraft 22 окт 2011 в 11:23

Нет:
«You can upload your code as often as you want. The rankings are not cumulative, so you're not at a disadvantage by re-uploading your code.»

Общая суть: можете обновлять бота сколько хотите, Ваш ранг при этом не изменится.