AI Challange 2011

Я не вижу смысла в отдельной записи для начала блога. Перейду сразу к делу. С 20 Октября по 18 декабря 2011г. проходил AI challenge. Мне интересен вопрос создания AI, потому я решил участвовать.
Подводя итоги, я...

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

Моего имени нет в рейтинге (я не стал  даже посылать бота) по объективным причинам:
за неделю до дедлайна у меня был готово то, что я считал ядром бота - алгоритм разбиения карты. Мне казалось, что имея такую штуку, остальное - мелочи. Главное то, что мой бот сможет анализировать глобальную ситуацию, принимать  стратегически верные решения и эффективно рассылать муравьев по всей карте с минимальными затратами на поиск пути! Имея инструмент для такого анализа, создавать множество целей, и отправлять муравьев на их выполнение мне казалось совсем несложной задачей.

На практике же, единственное чего я добился - более эффективного поиска пути, который было не к чему применить. За 4 дня я написал примитивнейший алгоритм, который справлялся с разведкой и сбором еды... И получил бота, уровня которого лидеры достигли на первой же неделе соревнований. Далее гнаться не было смысла - ошибка была в самой основе проекта, его концепции. Лидер рейтинга Xathis (тут можно прочитать разбор бота самим автором) прекрасно обошелся простым breadth-first search, сразу перейдя к более важным вещам и заслуженно получил первое место.

Пару слов о том, что же я собственно делал эти 2 месяца.
Алгоритм разбиения карты
Задачей алгоритма является разбиение карты на связный граф секторов. Пример работы (screenshot оригинального визуализатора, и моего собственного, показывающего карту секторов; выбран один и тот же момент игры):

Впервые о таком подходе я задумался после игры Dwarf Fortress. Игра великолепна, но имеет свои недостатки (это отдельная тема, позже вероятно еще напишу отдельный пост о  Dwarf Fortress). Одним из них является поиск пути, который на большой карте (местность которой постоянно меняется благодаря усилиям игрока) ложит процессор на обе лопатки, провешивая FPS до невыносимо низких значений.
Как способ решения этой проблемы я прорабатывал алгоритм разбиения карты на секторы. Это позволило бы на порядок уменьшить сложность проблеммы - поиск в ширину на 100 клеток несравнимо дольше двух поисков на 10 (один - по графу секторов 10х10, второй - внутри сектора).
Но муравьям этот алгоритм помог мало. Причина - в специфике проблемм, стоящих перед каждой игрой. В DF часто нужно выполнять поиск пути с большой глубиной (до 100-200 клеток), и главной проблеммой является как дойти; выбор исполнителя прост - ближайший свободный гном, спосоный выполнить задание. В Ants же все муравьи абсолютно равнозначны, и нужно решать тактические задачи, организовывать взаимодестйвие; случаи, когда нужно найти дорогу через всю карту бывают очень нечасто. Кроме того в DF практически всегда вся карта, куда можно дойти полностью видна. В Ants разведка - одна из основных действий в первую половину игры, и местность неизвестна, что значительно осложняет построение карты секторов и делает менее эффективным ее использование.
Итого: я сумел сделал инструмент, но он не оказался серебрянной пулей, способной решить все проблеммы.