В этой заметке я расскажу как написать довольно неплохого бота для Google AI Challenge. Примечательно, что сложные технологии связанные с ИИ не понадобятся, а базовая реализация умещается в тысячу строчек кода на языке C++. Сами методы в совокупности могут быть рассмотрены как некоторый Generic алгоритм, и на базе них можно построить бота, учитывающего некоторые стратегические особенности, который возможно будет играть еще лучше. В любом случае — хороший «быстрый старт» для тех, у кого пока ничего не получилось.1. Некоторый опыт участия в AI Challenge
Судя по комментариям к другим темам про AI Challenge у многих возникли вопросы относительно «здешней» системы рейтингов. Собственно комментарии.
1. Рейтинг бота оценивается относительно его успешности в играх против других ботов, т.е. цифра Skill является относительной величиной, и после каждой загрузки версии на сервер сбрасывается в ноль (т.к. не известно, будет ли новая версия лучше предыдущей).
2. Каждая успешная игра добавляет к Skill некоторую величину, зависящую от места (напомню — цель игры не собирать «еду», вырастив огромную «колонию», а захватывать вражеские муравейники) и от skill других игроков — и чем больше номер игры, тем меньше это приращение; таким образом, случайный проигрыш (сначала) слабому игроку надолго замедлит увеличение Skill.
3. Для примерной стабилизации рейтинга в текущей ситуации требуется около 5-7 дней («матчи» проводятся довольно редко).
Из вышесказанного следует, что уже поздно пытаться «итеративно» подгонять алгоритм под других игроков, поэтому крайне желательно протестировать бота локально, и тем более не тратить время на аплоад Starter Package.
Ограничение времени исполнения алгоритма на один ход: 500 мс, и может варьироваться параметром turntime. Однако крайне желательно завершить выполнение алгоритма быстрее этого порога хотя бы на 50 мс, иначе велика вероятность получить timeout из-за буферизации ввода-вывода (вся передача игровых данных ведется через pipes), а то иногда получаются забавные штуки:
Ограничение по памяти — 2Гб (ограничение 32битной платформы), гарантируется (скорее читается как «обещают») порядка 1.5Гб памяти, которая не окажется размазанной по файлу подкачки. Это достаточно большое количество (для карт 200 на 200 клеток — то), которое прямо-таки побуждает кешировать промежуточные результаты, чем мы и займемся для получения неплохого алгоритма нахождения путей к объектам.
2. Алгоритм нахождения пути
Сложно рассуждать о том, насколько хороша была бы «такая или другая» стратегия, пока муравьи не умеют «самостоятельно» ходить по лабиринту. По опыту — качественная реализация нахождения пути всегда лучше хорошей стратегии, если использовать «исключающее ИЛИ»; лучше конечно «и то, и то».
Предположим, что мы уже знаем куда идти (это мы обсудим чуть позже), и каким муравьем следует это делать. Остается вычислить начальное направление движения (N, E, S, W) и скомандовать системе. Для этого необходимо просчитать кратчайший путь к объекту-цели (мы можем конечно и «случайными движениями» покрыть всю карту, в теории, но противник к тому моменту давно нас уничтожит, на практике).
Если бы карта не содержала непроходимых участков «воды» (темно-синие клетки), то задача была бы тривиальна; рассмотрим красную линию, соединяющую «муравья» и «воду». Т.к. муравей умеет ходить только на одну клетку по четырем направлениям, то расстояние до объекта (без учета препятствий) совпадает с Манхэттенским расстоянием. Путь до объекта всегда будет занимать одинаковое количество клеток, если мы будем использовать приращения в нужную сторону. Вычитаем из координат цели (x1,y1) координаты муравья (x0,y0) и получаем количество шагов (|x1-x0|) с приращением по X: sign(x1-x0) и количество (|y1-y0|) по Y: sign(y1-y0) ведущим к цели. 
Вот наглядная иллюстрация того, что длина пути в любом случае будет одинаковой (количество клеток пути для всех трех линий одинаковое). Таким образом, подобную эвристику мы запишем в «полезные» и первым делом не побрезгаем проверить, нельзя ли дойти до объекта-цели двигаясь с правильным приращением (можно назвать такую функцию getSimplePath(), например). Зачем? Иногда она экономит время (и довольно существенное). Но, разумеется, она не справится с ситуациями, когда на пути будут лежать клетки воды, или тем более, начальное направление движения не соответствует конечному из-за препятствий (случай с зеленоватой линией на первой картинке).
Как же быть с препятствиями? Здесь нам поможет волновой алгоритм: берем матрицу размером с исходное поле, фиксируем клетку-цель (записывая туда 0) и рекурсивно заполняем матрицу значениями в соответствии с изображением справа (обходим только те клетки, в которых нет (или пока не обнаружено) «воды»). Смысл этих значений в количестве ходов, необходимых для достижения клетки цели. Правильно, как только мы дойдем рекурсивно до клетки в которой находится наш муравей мы сможем найти путь к цели — двигаясь по клеткам, для которых значения количества шагов уменьшаются. Алгоритм работает за время O(cols*rows). Много это или мало? В нашем случае |cols|,|rows| <= 200, всего нужно проложить маршруты для до 1000 муравьев (в реальных играх их никогда не бывает больше), и у каждого может быть до сотни потенциальных целей. Итого 200^2*1000*100, это 4 миллиарда итераций, по большей части записи в память. Здравый смысл подсказывает, что в 500мс это не уложится.
Почему тогда вообще выбран такой алгоритм? Для начала надо заметить, что теоретически за меньшее число действий без какой-либо промежуточной информации путь и не проложить, по крайней мере можно сконструировать пример, обходящийся за O(cols*rows) шагов («спираль» во все поле). Поэтому наша задача — сконструировать метод хорошо работающий при учете наличия промежуточной информации (состояние поля при переходе от одного хода к другому меняется незначительно). Кроме того, нет смысла переживать, что на первых ходах он работает медленно, у нас-то и муравьев всего-ничего.
Что мы будем запоминать? Всю матрицу шагов волнового алгоритма для каждой клетки цели:
char* WaveMaps[MAX_X][MAX_Y]; // указатели на карты волнового алгоритма
WaveMaps[x][y] = new char[MAX_X*MAX_Y]; // инициализация конкретной картыНапомню, что WaveMaps[x][y] считаются для объекта-цели с координатами (x,y); фактически это все возможные маршруты до этого объекта. Таким образом ясно, что целями не окажутся клетки с водой (в них нет смысла, да и просто нельзя идти), и бОльшая часть не заполненных ничем (едой, муравьями, муравейниками) клеток нам не интересны — они и не будут инициализированы.
Таким образом, за один ход мы без дополнительных накладных расходов можем просчитать пути от каждого муравья до заданной точки, определив, который из них дойдет быстрее (первый раз считаем карту — потом смотрим в кеш).
Что будет на следующем ходе? В процессе игры муравьи блуждают по полю, «открывая» новые клетки — изначально мы знаем о заполнении только небольшой части лабиринта, но по мере движения обнаруживаем еду, воду, вражеских муравьев, муравейники. В данном случае нас будет интересовать, что делать с картами, при обнаружении новой клетки «воды».
Для начала выясним, как обнаружить «воду». Для этого достаточно хранить локальную копию состояния поля, и на каждом новом ходе проверять нет ли отличий получаемого игрового состояния от сохраненного. Хорошо, обнаружили воду на позиции (x1, y1). Тогда нужно пересчитать все карты, в которых значение на позиции (x1, y1) заполнено номером шага (а не дефолтным значением).
С учетом того, что все карты доступны в tools package можно оценить, какой процент переинициализации (вычисления заново) матриц для волнового алгоритма нам следует ожидать. Итог: 100%. Совсем не здорово, а все потому что мы строили карты, охватывающие все игровое поле, однако в этом нет смысла, ведь все маршруты можно разделить на «длинные» и «короткие». Короткие требуют точного определения клеток маршрута, а длинные составляются из блоков коротких.
Таким образом, разумной идеей будет хранить иерархическую карту достижимости объектов. В случае моей реализации достаточно было всего двух уровней (100мс на планирование всех маршрутов для всех муравьев в худшем разумном случае).
Тогда вышеописанный алгоритм модифицируется следующим образом:
1. При заполнении каждой карты волнового алгоритма проверяем, не больше ли расстояние от начальной до текущей точки, чем MAP_RANGE (если больше — выходим);
2. Строим полную волновую карту для поля с низким разрешением (MAX_X/SCALE,MAX_Y/SCALE). Такая карта поможет для нахождения пути между точками с расстоянием большим MAP_RANGE.
При запросе пути для достаточно далеких точек (x1,y1) и (x0,y0) мы сначала смотрим карту низкого разрешения, получаем промежуточную точку (x2,y2) и объединяем пути (x1,y1)->(x2,y2) и (x2,y2)->(x0,y0), рекурсия, ага.
Введенный параметр MAP_RANGE с одной стороны определяет, насколько часто будут полностью пересчитываться карты волнового алгоритма, с другой — итоговую точность очень длинных путей. При MAP_RANGE > 2*viewRadius ошибок практически нет, а время (маршруты для всех муравьев) едва ли выходит за 100мс.
Напомню, эта хитрость с MAP_RANGE и картой низкого разрешения понадобилась нам для того, чтобы успешно пользоваться кешированием результатов, по возможности редко обновляя кеш (когда клетка будет исследована в радиусе MAP_RANGE, ее обновление и вовсе прекратится).
Что касается памяти: в худшем случае заполнение будет составлять: 200^2*(200/2)^2 (полные карты) + (200/SCALE)^4 (низкое разрешение) байт, что не превысит порог в 500Мбайт при разумном значении SCALE (больше 5).
3. Цели
Хороший способ выиграть — не делать бессмысленных ходов, и не пропускать осмысленные возможности. Попробуем проанализировать, что именно это значит.
Целями могут являться:
1. Вражеские муравейники
2. Еда (только если есть свои муравейники)
3. Свои муравейники (для защиты)
4. Свои муравьи (для защиты или улучшения атаки) — поддержка
5. Вражеские муравьи
6. Неисследованные клетки
В игре больше нет объектов, соответственно и других целей нет.
Я выписал цели в порядке их приоритета (назовем их programList), от самых важных до наименее важных (но все равно нужных). Захватывать муравейники — смысл игры, поэтому при прочих равных возможностях, лучше попытаться захватить муравейник (кроме некоторых оговорок которые последуют дальше), чем гоняться за едой. Не хотелось бы терять свои муравейники, и своих муравьев. При возможности просто так «убить» (без потерь со своей стороны) вражеских муравьев — лучше это сделать. Ну и если совсем нечем заняться, можно побродить по полю.
Для того чтобы найти объекты-цели необходимо обойти все полученное поле, проверив удовлетворяют ли они критериям цели:
foreach int program in |ProgramList|
foreach Location loc in map
if (MatchingProgram(loc, program))
ProgramList[program].push_back(loc);Где MatchingProgram определяет подходит ли заданная клетка под программу:
1. если программа == вражеские муравейники, то клетка должна содержать вражеский муравейник;
2. еда, клетка содержит еду;
3. свои муравейники, клетка содержит свой муравейник и есть косвенная угроза ему (наличие вражеского муравья ближе, чем нашего);
4. свои муравьи, клетка содержит своего муравья и есть косвенная угроза ему (наличие вражеских муравьев в viewRadius);
5. наличие вражеского муравья, и его врагов больше-равно, чем «союзников»;
6. неисследованные клетки (клетки в которых мы еще не были, об этом подробнее ниже).
Далее необходимо назначить каждой цели муравья, который займется ее реализацией. Для каждой цели просматриваем список муравьев; выбираем ближайшего, для которого предыдущая цель (установленная на прошлом ходу) хуже текущей (т.е. идет под бОльшим номером в списке), или не хуже && расстояние до предыдущей цели больше (с запасом на 1 шаг). Это с одной стороны исключает «дерганье» муравья туда-сюда между равнозначными целями (частая ошибка у участников), с другой позволяет использовать обновленную информацию (в поисках еды добрели до вражеского муравейника).
4. Блокировки
Как известно, два или более муравья, попавшие на одну клетку умирают. Мы хотим предотвратить бессмысленные потери «состава».
Тривиальнейшим способом было бы проверять, не занята ли клетка-назначение другим муравьем, так работает большинство простейших ботов. Но в таком случае не исключены блокировки, когда муравьи мешают друг другу пройти до своих целей, и, как оно часто бывает, бессмысленно толпятся у базы и не исключается ситуация, когда у некоторых муравьев вообще нет никакого хода.Поэтому следует разделять тех муравьев, которые уже переместились за ход, и тех, которые еще не двигались. При попытке встать на уже занятую клетку возникает два варианта:
1. Выбрать другое направление для текущего муравья;
2. Передвинуть того, кто мешает (blocker) на другую клетку.
programAnt(MyAnt *ant):
if (ant->alreadyMoved) return;
repeat:
direction = getDirectionByProgramList(program)
if (moveResult(ant, direction) == mrBlockerNotMoved)
{
programAnt(blocker);
program++;
goto repeat;
}Важно, что «мешающие» муравьи передвигаются не абы как, а в соответствии с лучшей из возможных программ. Таким образом, функция «программирования» муравья в результате может сдвинуть аж несколько соседних муравьев за вызов — надо только избегать взаимной рекурсии с одинаковыми параметрами.
Еще одной причиной для бесполезной смерти муравья является попытка забрести в области, с превышающим количеством противников. Для обнаружения таких ситуаций придется потрудиться и написать battleResolution.
В этом нет проблемы, однако если вы будете пользоваться C++ starter package, то придется использовать state.grid, а не enemyAnts, т.к. в списке они не различимы по типу (если это не поправили уже, конечно). Да и вообще…
5. Почему starter package не так хорош
1. Получаемые в myAnts объекты-муравьи не хранят свои параметры. Я уже упоминал о том, что неплохо хранить для каждого муравья его последнюю программу и путь, однако средствами State.h этого не сделать — вектор myAnts создается на каждом ходе. Поэтому корректным способом хранить параметры муравьев будет создание карты вида MyAnt* antMap[MAX_X][MAX_Y], которую вы будете обновлять вручную (это не так сложно сделать в функции makeMove для конкретного муравья).
2. Функция updateVisibility работает неприемлемо долго. Для тысячи муравьев пожалуй даже дольше, чем прокладка путей, т.к. для каждого муравья проверяется уйма клеток на неравенство, определяющее расстояние. Гораздо быстрее было бы (что я и сделал) сохранить для каждой клетки список непосредственно видимых (viewRadius) и атакуемых (attackRadius), инициализируемый при первом рассмотрении клетки. Тогда updateVisibility может помечать видимые для каждого муравья клетки используя готовый список, а не перебором.
3. std::vector<std::vector> grid. Здесь мы теряем и в скорости, и в ряде случаев увеличиваем использование памяти даже против Square grid[MAX_X][MAX_Y]. Потеря скорости не шуточная, так как объект очень плохо кешируется, будучи разбросанным по разным адресам памяти.
6. Исследование и контроль территорий
Поскольку теперь мы знаем, как дойти до конкретного объекта, как неявно предотвращать потери муравьев и неявно организовывать атаки на вражеских муравьев (кроме явных попыток собрать еду, захватить муравейник), осталось научиться осваивать территорию.
Исследование подразумевает обнаружение статических объектов в тех местах, где мы еще не были (муравейники, вода).
Контроль — проверка не появилось ли что-нибудь полезное (еда) или вредное (вражеские муравьи).
И то и другое, суть одно и то же — клетки, в которых мы давно не были. И это понятие достаточно легко формализуется.
После того как мы назначим цели (программы с первой по пятую) ряду муравьев, остается некоторое количество муравьев, которые пока не знают, куда идти, их и нужно направить погулять. Так вот идти им следует в те клетки, которые никто не видит (visibility == 0). Из тех «невидимых» клеток приоритет имеют те, что не были видимыми никогда (lastSeen == NEVER) — исследование. Из оставшихся — те, которые были видимыми на самых ранних ходах (max lastSeen) — контроль. Среди равных по параметру lastSeen клеток следует выбирать ближайшие.
Такой алгоритм достаточно быстро обойдет все поле, и при этом не позволит надолго терять из видимости территории, где возможно появится еда.
7. Повод поразмыслить
Теперь наши муравьи вполне жизнеспособны и знают «что делать», однако вышеописанный алгоритм не гарантирует победы.
Во-первых потому, что в игре невозможно сконструировать всегда выигрышный алгоритм. Простой пример возможной ситуации — на первых ходах все противники атакуют именно вас, с разных сторон, и так, чтобы не атаковать друг друга. Никакая расстановка даже большого количества муравьев вокруг базы не позволит ее защитить.
Во-вторых, порядок целей, которые я определил сам по себе корректен (скажем так, имеет смысл), но никак не учитывает стратегические особенности оппонентов. В ряде случаев достаточно быстро добежать до вражеского муравейника и захватить его (т.к. он не охраняется), а иногда это верный способ самоубийства. Приоритет целей будет зависеть от уровня противника. Со слабым противником даже полезно «размениваться» муравьями, а от сильных иногда лучше «бегать» и дожидаться момента почти полного «размена» других игроков. На первых ходах мы вообще ничего не знаем о противниках, а дожить до середины игры при равных по уровню — везение (ну или отсутствие «невезения»). Таким образом, сам приоритет целей неявным образом содержит в себе понятие о стратегии (например, я ничего не говорил про групповую атаку, однако она осуществляется благодаря цели 4 — поддержка), над которым можно здорово поработать.
Надеюсь, вышеизложенное поможет кому-нибудь решить некоторые вопросы, или хотя бы покажет, что в целом предмет соревнования не такой и сложный. Удачи!
